DocumentCode :
1865984
Title :
Optimal local topology knowledge for energy efficient geographical routing in sensor networks
Author :
Melodia, Tommaso ; Pompili, Dario ; Akyildiz, Ian E.
Author_Institution :
Broadband & Wireless Networking Lab., Georgia Inst. of Technol., Atlanta, GA
Volume :
3
fYear :
2004
fDate :
7-11 March 2004
Firstpage :
1705
Abstract :
Since sensor networks can be composed of a very large number of nodes, the developed protocols for these networks must be scalable. Moreover, these protocols must be designed to prolong the battery lifetime of the nodes. Typical existing routing techniques for ad hoc networks are known not to scale well. On the other hand, the so-called geographical routing algorithms are known to be scalable but their energy efficiency has never been extensively and comparatively studied. For this reason, a novel analytical framework is introduced. In a geographical routing algorithm, the packets are forwarded by a node to its neighbor based on their respective positions. The proposed framework allows to analyze the relationship between the energy efficiency of the routing tasks and the extension of the range of the topology knowledge for each node. The leading forwarding rules for geographical routing are compared in this framework, and the energy efficiency of each of them is studied. Moreover partial topology knowledge forwarding, a new forwarding scheme, is introduced. A wider topology knowledge can improve the energy efficiency of the routing tasks but can increase the cost of topology information due to signaling packets that each node must transmit and receive to acquire this information, especially in networks with high mobility. The problem of determining the optimal knowledge range for each node to make energy efficient geographical routing decisions is tackled by integer linear programming. It is demonstrated that the problem is intrinsically localized, i.e., a limited knowledge of the topology is sufficient to take energy efficient forwarding decisions, and that the proposed forwarding scheme outperforms the others in typical application scenarios. For online solution of the problem, a probe-based distributed protocol which allows each node to efficiently select its topology knowledge, is introduced and shown to converge to a near-optimal solution very fast
Keywords :
ad hoc networks; integer programming; linear programming; protocols; telecommunication network routing; telecommunication network topology; wireless sensor networks; ad hoc network; energy efficient geographical routing; integer linear programming; near-optimal solution; optimal local topology control; partial topology knowledge forwarding; position based routing; probe-based distributed protocol; signaling packet; wireless sensor network; Ad hoc networks; Algorithm design and analysis; Computer networks; Energy efficiency; Intelligent networks; Network topology; Protocols; Routing; Scalability; Wireless sensor networks;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies
Conference_Location :
Hong Kong
ISSN :
0743-166X
Print_ISBN :
0-7803-8355-9
Type :
conf
DOI :
10.1109/INFCOM.2004.1354582
Filename :
1354582
Link To Document :
بازگشت