Name
Abstract | ||
|---|---|---|
Relay node placement is an important issue because it greatly affects the performance of wireless ad hoc sensor networks. The pervious works mainly pay attention on placing the minimum number of relay nodes to connect all the sensor nodes. But we find that this placement scheme may result in QoS reduction of the network, such as transmission delay, energy cost, etc. Therefore, this work studies the minimum relay node placement problem to guarantee both the connectivity and geometric spanner properties. We first show that there is no algorithm with the performance O(opt) for this problem, where opt is the minimum number of relay nodes to connect the sensor nodes. Thus, this paper presents an efficient placement algorithm MSGP with O(max{opt, n}) relay nodes, where n is the number of sensor nodes. Specially, if any two sensor nodes cannot communicate directly, the algorithm obtains O(1)-approximation bound. Then, as data gathering is one of the most important operations in sensor networks, we also study the spanner-aware placement problem for this communication scheme. The simulation results show the efficiency of the proposed algorithm. For example, MSGP algorithm can reach the spanner factor 3 with the additional 30% relay nodes compared with MST-based placement algorithm. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/MSN.2009.14 | MSN |
Keywords | Field | DocType |
wireless sensor networks,wireless ad hoc sensor network,qos reduction,approximation bound,msgp algorithm,network performance,placement,mst-based placement algorithm,minimum relay node placement,quality of service,approximation,communication complexity,spanner,connectivity property,node placement,minimum number,data gathering,wireless ad hoc sensor,efficient placement algorithm msgp,proposed algorithm,geometric spanner property,algorithm obtains o,spanner-aware relay node placement,sensor node,ad hoc networks,node placement problem,placement scheme,wireless sensor network,sensor network | Key distribution in wireless sensor networks,Relay channel,Computer science,Geometric spanner,Transmission delay,Computer network,Wireless ad hoc network,Spanner,Wireless sensor network,Relay,Distributed computing | Conference |
ISBN | Citations | PageRank |
978-1-4244-5468-6 | 2 | 0.50 |
References | Authors | |
11 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hongli Xu | 1 | 502 | 85.92 |
| Liusheng Huang | 2 | 1082 | 123.52 |
| Gang Wang | 3 | 282 | 65.93 |
| Yindong Zhang | 4 | 64 | 6.91 |