TY - GEN
T1 - The Min-entropy of Distributed Wireless Link Scheduling Algorithms under Arbitrary Interference
AU - Kowalski, Dariusz R.
AU - Mosteiro, Miguel A.
N1 - Publisher Copyright:
© 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - We study the Distributed Wireless Link Scheduling (DWLS) problem: there is a set of n autonomous stations, called senders, each with a packet to be delivered to some other station, called receiver. The names and locations of all stations are arbitrarily selected and unknown to each other, to mirror an arbitrary scenario that may occur in mobile communication. Each pair sender-receiver and the message to be sent is called a request, and the event of successfully delivering the message is called the realization of the request.In the DWLS problem, the requests are realized through wireless communication links (which is a conceptual notion of two nodes being capable of direct wireless delivery of a message) between the stations. The decision to transmit a message is made locally by each station. We consider networks where communication links may interfere with each other, where the interference is an arbitrary input function of each pair of links, customarily called affectance; if the total affectance of other links whose senders are currently transmitting is above a given threshold, the considered transmission is not successful.In the above context, we study the impact of algorithms' min-entropy, measured as the number of truly random bits used by each link/sender, on the length of the transmission schedules. Specifically, for any set L of n requests with maximum average affectance A(L), we present a deterministic algorithm (i.e., 0 random bits) and a randomized algorithm using O(logA(L)logn) random bits per link. (In this abstract we present formulas in simplified forms, for brevity.) The lengths of their transmission schedules are O(A(L)2 log3 n) and O(A(L)logn), respectively. We then combine both approaches to get a randomized solution with min-entropy O(logW logn) per station that uses schedules of length O(A/L2W log n), for any W = A(L).To the best of our knowledge, our study is a first step towards understanding the trade-offs between randomness and time complexity of Link Scheduling under arbitrary interference. It is particularly important as currently used (in practise) wireless protocols are either deterministic or use a very small random seed of (truly) random bits.
AB - We study the Distributed Wireless Link Scheduling (DWLS) problem: there is a set of n autonomous stations, called senders, each with a packet to be delivered to some other station, called receiver. The names and locations of all stations are arbitrarily selected and unknown to each other, to mirror an arbitrary scenario that may occur in mobile communication. Each pair sender-receiver and the message to be sent is called a request, and the event of successfully delivering the message is called the realization of the request.In the DWLS problem, the requests are realized through wireless communication links (which is a conceptual notion of two nodes being capable of direct wireless delivery of a message) between the stations. The decision to transmit a message is made locally by each station. We consider networks where communication links may interfere with each other, where the interference is an arbitrary input function of each pair of links, customarily called affectance; if the total affectance of other links whose senders are currently transmitting is above a given threshold, the considered transmission is not successful.In the above context, we study the impact of algorithms' min-entropy, measured as the number of truly random bits used by each link/sender, on the length of the transmission schedules. Specifically, for any set L of n requests with maximum average affectance A(L), we present a deterministic algorithm (i.e., 0 random bits) and a randomized algorithm using O(logA(L)logn) random bits per link. (In this abstract we present formulas in simplified forms, for brevity.) The lengths of their transmission schedules are O(A(L)2 log3 n) and O(A(L)logn), respectively. We then combine both approaches to get a randomized solution with min-entropy O(logW logn) per station that uses schedules of length O(A/L2W log n), for any W = A(L).To the best of our knowledge, our study is a first step towards understanding the trade-offs between randomness and time complexity of Link Scheduling under arbitrary interference. It is particularly important as currently used (in practise) wireless protocols are either deterministic or use a very small random seed of (truly) random bits.
UR - http://www.scopus.com/inward/record.url?scp=85171446222&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85171446222&partnerID=8YFLogxK
U2 - 10.1109/ISIT54713.2023.10206605
DO - 10.1109/ISIT54713.2023.10206605
M3 - Conference contribution
AN - SCOPUS:85171446222
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 2685
EP - 2690
BT - 2023 IEEE International Symposium on Information Theory, ISIT 2023
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2023 IEEE International Symposium on Information Theory, ISIT 2023
Y2 - 25 June 2023 through 30 June 2023
ER -