標題: MINIMUM LOCAL DISK COVER SETS FOR BROADCASTING IN HETEROGENEOUS MULTIHOP WIRELESS NETWORKS
作者: Chen, Guaning
Yi, Chih-Wei
Sun, Min-Te
Liu, Fang-Chu
Lan, Wei-Chi
資訊工程學系
Department of Computer Science
關鍵字: Minimum disc cover;optimal algorithms;applications in multihop networks
公開日期: 1-八月-2012
摘要: The concept of forwarding sets is widely adopted in many broadcast protocols for wireless multihop networks to alleviate the broadcast storm problem. In these protocols, after receiving a broadcast message, each node that is requested to relay the message instructs a subset of its 1-hop neighbors, a.k.a. the forwarding set, to further relay it. In this paper, we propose to use the Minimum Local Disk Cover Set (MLDCS) as the forwarding set in heterogeneous multihop wireless networks, where nodes may have different transmission ranges. We show that the minimum local disk cover set of a node in heterogeneous networks is equivalent to its skyline set, and then we propose a divide-and-conquer algorithm with the optimal time complexity to compute the skyline set locally and statelessly. Moreover, unlike other forwarding heuristics, the proposed algorithm requires only 1-hop neighbor information. This helps to reduce the forwarding set formation latency and thus will be more suitable for environments with a frequently changed network topology, such as vehicular ad hoc networks.
URI: http://dx.doi.org/10.1142/S0129054112500165
http://hdl.handle.net/11536/20497
ISSN: 0129-0541
DOI: 10.1142/S0129054112500165
期刊: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Volume: 23
Issue: 5
起始頁: 1147
結束頁: 1172
顯示於類別:期刊論文


文件中的檔案:

  1. 000309470000012.pdf