Name
Title | ||
|---|---|---|
Fault-tolerant deployment with k-connectivity and partial k-connectivity in sensor networks |
Abstract | ||
|---|---|---|
Wireless sensor networks are prone to failure, so prolonging their lifetime and preventing loss of connectivity are significant. A simple but efficient strategy is to place redundant sensor nodes to establish multi-connectivity. This paper explores how to add as few as possible nodes (called Steiner nodes) to a sensor network such that the resulting network is k-connected or partially k-connected. k-connectivity means that each pair of the nodes, whether Steiner or original, is connected by at least k node-disjoint paths, while partial k-connectivity only requires such connectivity among original nodes. The contribution lies in two aspects. First, the approximation ratio of an existing k-connectivity repair algorithm is decreased from O(k4α) to O(k3α), where α is the approximation ratio of any algorithm that finds a minimum-weight k-connected spanning subgraph of a weighted complete graph. This is the best result ever obtained. Second, the first generic partial k-connectivity repair algorithm is proposed. It is proved that the approximation ratio of this algorithm is at most O(k3α). Copyright © 2008 John Wiley & Sons, Ltd. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1002/wcm.v9:7 | Wireless Communications and Mobile Computing |
Keywords | Field | DocType |
deployment,sensor network,sensor networks,fault tolerant | Complete graph,k-means clustering,Wireless network,Social connectedness,Detection theory,Computer science,Sensor array,Algorithm,Fault tolerance,Wireless sensor network | Journal |
Volume | Issue | Citations |
9 | 7 | 10 |
PageRank | References | Authors |
0.73 | 15 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Juhua Pu | 1 | 20 | 3.47 |
| Zhang Xiong | 2 | 13 | 1.85 |
| Xiaofeng Lu | 3 | 13 | 1.52 |