Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links
Tóm tắt
We extend dominating-set-based routing to networks with unidirectional links. Specifically, an efficient localized algorithm for determining a dominating and absorbant set of vertices (mobile hosts) is given and this set can be easily updated when the network topology changes dynamically. A host /spl nu/ is called a dominating neighbor (absorbant neighbor) of another host u if there is a directed edge from /spl nu/ to u (from u to /spl nu/). A subset of vertices is dominating and absorbant if every vertex not in the subset has one dominating neighbor and one absorbant neighbor in the subset. The derived dominating and absorbant set exhibits good locality properties; that is, the change of a node status (dominating/dominated) affects only the status of nodes in the neighborhood. The notion of dominating and absorbant set can also be applied iteratively on the dominating and absorbant set itself, forming a hierarchy of dominating and absorbant sets. The effectiveness of our approach is confirmed and the locality of node status update is verified through simulation.
Từ khóa
#Intelligent networks #Wireless networks #Routing protocols #Wireless sensor networks #Bandwidth #Network topology #Mobile radio mobility management #Base stations #Distributed computing #Military computingTài liệu tham khảo
wu, 2002, On Locality of Dominating Set in Ad Hoc Networks with Switch-On/Off Operations, Proc Int'l Symp Parallel Architetures Algorithms and Networks (I-SPAN '02), 85
10.1145/313451.313556
10.1023/A:1016783217662
10.1137/0211059
tanenbaum, 1996, Computer Networks
10.1016/0031-3203(80)90066-7
lin, 1996, Adaptive Clustering for Mobile Wireless Networks, IEEE J Selected Areas in Comm, 15, 1265, 10.1109/49.622910
steenstrup, 1995, Routing in Comm Networks
10.1023/A:1016735301732
10.1016/0020-0190(94)00159-6
hedrick, 1988, Routing Information Protocol, Internet Request for Comments (RFC) 1058
haas, 1997, The Zone Routing Protocol (ZRP) for Ad Hoc Networks, IETF Internet Draft
10.1007/PL00009201
10.2307/2412323
jacquet, 2000, Optimized Link State Routing Protocol (OLSR), IETF Internet Draft
10.1109/TCOM.1980.1094721
10.1016/0376-5075(77)90014-9
moy, 1991, "OSPF "
shepard, 1996, A Channel Access Scheme for Large Dense Packet Radio Networks, Proc ACM Speical Interest Group on Comm (SIGCOMM) Conf Comm Architectures Protocols and Applications
bertsekas, 1992, Data Networks
10.1109/98.760423
10.1109/TCOM.1981.1094909
amis, 2001, Max-Min -Cluster Formation in Wireless Ad Hoc Networks, Proc INFORCOM, 32
steenstrup, 2001, Cluster-Based Networks in Ad Hoc Networks
sivakumar, 1998, An Improved Spine-Based Infrastructure for Routing in Ad Hoc Networks, Proc Int'l Symp Computers and Comm (ISCC '98)
10.1109/HICSS.2002.994519
10.1109/INFCOM.1997.631180
10.1023/A:1013985610753
papadimitriou, 1988, Combinatorial Optimization Algorithms and Complexity
das, 1997, Routing in Ad Hoc Networks Using a Virtual Backbone, Proc Sixth Int'l Conf Computer Comm and Networks (IC3N '97), 1
10.1145/190809.190336
10.1109/WCNC.1999.796715
perkins, 1997, Mobile IP Design Principles and Practices
broch, 1998, The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks, IETF Internet Draft