TY - GEN
T1 - An approximation algorithm for conflict-aware broadcast scheduling in wireless ad hoc networks
AU - Mahjourian, Reza
AU - Thai, My
AU - Chen, Feng
AU - Zhai, Hongqiang
AU - Tiwari, Ravi
AU - Fang, Yuguang
N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
PY - 2008
Y1 - 2008
N2 - Broadcast scheduling is a fundamental problem in wireless ad hoc networks. The objective of a broadcast schedule is to deliver a message from a given source to all other nodes in a minimum amount of time. At the same time, in order for the broadcast to proceed as predicted in the schedule, it must not contain parallel transmissions which can be conflicting based on the collision and interference parameters in the wireless network. Most existing work on this problem use a limited network model which accounts only for conflicts occurring inside the transmission ranges of the nodes. The broadcast schedules produced by these algorithms are likely to experience unpredictable delays when deployed in the network. This is because they do not take into consideration other important sources of conflict in parallel transmissions, namely the interference range and the carrier sensing range. In this paper we develop a conflict-aware network model, which uses these parameters to increase the probability of scheduling conflict-free transmissions, and thereby improve the reliability of the broadcast schedule. We present and prove correctness of a constant approximation algorithm for minimum-latency broadcast scheduling under this network model. We also present a greedy heuristic algorithm for the same problem. Experimental results are provided to evaluate the performance of our algorithms. In addition, the algorithms are analyzed to justify their performance trends. Copyright 2008 ACM.
AB - Broadcast scheduling is a fundamental problem in wireless ad hoc networks. The objective of a broadcast schedule is to deliver a message from a given source to all other nodes in a minimum amount of time. At the same time, in order for the broadcast to proceed as predicted in the schedule, it must not contain parallel transmissions which can be conflicting based on the collision and interference parameters in the wireless network. Most existing work on this problem use a limited network model which accounts only for conflicts occurring inside the transmission ranges of the nodes. The broadcast schedules produced by these algorithms are likely to experience unpredictable delays when deployed in the network. This is because they do not take into consideration other important sources of conflict in parallel transmissions, namely the interference range and the carrier sensing range. In this paper we develop a conflict-aware network model, which uses these parameters to increase the probability of scheduling conflict-free transmissions, and thereby improve the reliability of the broadcast schedule. We present and prove correctness of a constant approximation algorithm for minimum-latency broadcast scheduling under this network model. We also present a greedy heuristic algorithm for the same problem. Experimental results are provided to evaluate the performance of our algorithms. In addition, the algorithms are analyzed to justify their performance trends. Copyright 2008 ACM.
KW - Approximation algorithm
KW - Broadcast scheduling
KW - Conflict-aware
KW - Wireless networks
UR - http://www.scopus.com/inward/record.url?scp=57349125628&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-57349125628&origin=recordpage
U2 - 10.1145/1374618.1374663
DO - 10.1145/1374618.1374663
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9781605580739
T3 - Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)
SP - 331
EP - 340
BT - Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing 2008, MobiHoc'08
T2 - 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing 2008, MobiHoc'08
Y2 - 26 May 2008 through 30 May 2008
ER -