Geometric spanners for wireless ad hoc networks
Proceedings - International Conference on Distributed Computing Systems - Trang 171-178 - 2002
Tóm tắt
We propose a new geometric spanner, for wireless ad hoc networks, which can be constructed efficiently in a distributed manner. It combines the connected dominating set and the local Delaunay graph to form the backbone of a wireless network. This new spanner has the following attractive properties: (1) the backbone is a planar graph; (2) the node degree of the backbone is bounded from above by a positive constant; (3) it is a spanner both for hops and length; moreover, we show that, given any two nodes u and /spl upsi/, there is a path connecting them in the backbone such that its length is no more than 6 times that of the shortest path and the number of links is no more than 3 times that of the shortest path; (4) it can be constructed locally and is easy to maintain when the nodes move around; and (5) we show that the computation cost of each node is at most O(d log d), where d is its l-hop neighbors in the original unit disk graph, and the communication cost of each node is bounded by a constant. Simulation results are also presented for studying its practical performance.
Từ khóa
#Ad hoc networks #Routing #Spine #Network topology #Mobile ad hoc networks #Floods #Information geometry #Clustering algorithms #Computer science #Wireless networksTài liệu tham khảo
li, 2002, Distributed construction of planar spanner and routing for ad hoc wireless networks, IEEE INFOCOM
li, 2001, Power efficient and sparse spanner for wireless ad hoc networks, International Conf on Comp Comm and Networks, 564
li, 2002, Sparse power efficient topology for wireless networks, Proc Hawaii International Conf System Sciences (HICSS)
10.1109/49.622910
10.1002/net.3230250205
10.1109/71.980024
wan, 2002, Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks, IEEE TNFOCOM
wattenhofer, 2001, Distributed topology control for wireless multihop ad-hoc networks, IEEE INFOCOM'01
wu, 2001, A dominating-set-based routing scheme in ad hoc wireless networks, The Special Issue on Wireless Networks in the Telecomm Systems J, 3, 63
10.1145/313239.313282
bose, 2001, On the spanning ratio of Gabriel graphs and beta-skeletons, Submitted to SIAM Journal on Discrete Mathematics
10.1109/ICC.1997.605303
chlamtac, 1999, A new approach to the design and analysis of peer-to-peer mobile networks
10.1145/501416.501424
10.1145/378583.378666
amis, 2000, Maxmin d-cluster formation in wireless ad hoc networks, Proc of IEEE INFOCOM'00, 1, 32
10.1109/HICSS.2002.994519
10.1145/345910.345953