Deploying sensor networks with guaranteed capacity and fault tolerance

ABSTRACT

We consider the problem of deploying or repairing a sensor network to guarantee a specified level of multi-path connectivity (k-connectivity) between all nodes. Such a guarantee simultaneously provides fault tolerance against node failures and high capacity through multi-path routing. We design and analyze the first algorithms that place an almost-minimum number of additional sensors to augment an existing network into a k-connected network, for any desired parameter k. Our algorithms have provable guarantees on the quality of the solution. Specifically, we prove that the number of additional sensors is within a constant factor of the absolute minimum, for any fixed k. We have implemented greedy and distributed versions of this algorithm, and demonstrate in simulation that they produce high-quality placements for the additional sensors. We are also in the process of using our algorithms to deploy nodes in a physical sensor network using a mobile robot.

References

1. P. Corke, S. Hrabar, R. Peterson, D. Rus, S. Saripalli, and G. Sukhatme, "Autonomous deployment of a sensor network using an unmanned aerial vehicle," in Proceedings of the 2004 International Conference on Robotics and Automation, New Orleans, USA, 2004.]]
2. P. Corke, S. Hrabar, R. Peterson, D. Rus, S. Saripalli, and G. Sukhatme, "Deployment and connectivity repair of a sensor net with a .ying robot," in Proceedings of the 9th International Symposium on Experimental Robotics, Singapore, 2004.]]
3. G. H. Lin and G. Xue, "Steiner tree problem with minimum number of Steiner points and bounded edge-length," Inform. Process. Lett., vol. 69, no. 2, pp. 53--57, 1999.]]
4. R. Ramanathan and R. Rosales-Hain, "Topology control of multihop radio networks using transmit power adjustment," in Proceedings of Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pp. 404--413. March 2000.]]
5. M.Bahramgiri,M.Hajiaghayi,and V.S.Mirrokni, "Fault-tolerant and 3-dimensional distributed topology control algorithms wireless multi-hop networks," in Proceedings of the 11th IEEE International Conference on Computer Communications and Networks (ICCCN), pp. 392--398. 2002.]]
6. R. Wattenhofer, L. Li, V. Bahl, and Y. M. Wang, "Distributed topology control for power efficient operation in multihop wireless ad hoc networks," in Proceedings of twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pp. 1388--1397. 2001.]]
7. L. Li, J. Halpern, V. Bahl, Y. M. Wang, and R. Wattenhofer ,"Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks," in Proceedings of ACM Symposium on Principle of Distributed Computing (PODC), pp. 264--273. 2001.]]
8. M. Hajiaghayi, N. Immorlica, and V. S. Mirrokni, "Power optimization in fault-tolerant topology control algorithms for w ireless multi-hop networks," in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking 2003, pp. 300--312, ACM Press.]]
9. E. Lloyd, R. Liu, M. Marathe, R. Ramanathan, and S. Ravi, "Algorithmic aspects of topology control problems for ad hoc networks," Proceedings of the Third ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2002.]]
10. D. Blough, M. Leoncini, G. Resta, and P. Santi, "The K-neigh protocol for symmetric topology control in ad hoc networks," in ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). June 2003.]]
11. X. Y. Li, W. Z. Song, and Y. Wang, "Efficient topology control for wireless ad hoc networks with non-uniform transmission ranges," ACM Wireless Networks, in press.]]
12. X. Y. Li, Y. Wang, P. J. Wan, and C. W. Yi, "Robust deployment and fault tolerant topology control for wireless ad hoc networks," in ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). June 2003.]]
13. Ning Li and Jennifer C. Hou, "FLSS: a fault-tolerant topology control algorithm for wireless networks," in Proceedings of the 10th Annual International Conference on Mobile Computing and Networking 2004, pp. 275--286, ACM Press.]]
14. D. Chen, D. Z. Du, X. D. Hu, G. H. Lin, L. Wang, and G. Xue, "Approximations for Steiner trees with minimum number of Steiner points,"J. Global Optim., vol. 18, no. 1, pp.17--33, 2000.]]
15. D. Du, L. Wang, and B. Xu, "The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points," in Computing and Combinatorics (Guilin, 2001), vol. 2108 of Lecture Notes in Comput. Sci., pp. 509--518. Springer, Berlin, 2001.]]
16. D. M. Blough, M. Leoncini, G. Resta, and P. Santi, "On the symmetric range assignment problem in wireless ad hoc networks.," Proceedings of the 2nd IFIP International Conference on Theoretical Computre Science (TCS), pp. 71--82, 2002.]]
17. G. Calinescu, I. L. Mandoiu, and A. Zelikovsky, "Symmetric connectivity with minimum power consumption in radio networks," in Proceedings of 17th IFIP World Computer Congress, pp. 119--130. 2002.]]
18. Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, and Andrzej Pelc, "Power consumption in packet radio networks," Theoret. Comput. Sci., vol. 243, no. 1-2, pp. 289--305, 2000.]]
19. A. Frank and E. Tardos, "An application of submodular flows," Linear Algebra Appl., vol. 114/115, pp. 329--348, 1989.]]
20. S. Khuller and B. Raghavachari, "Improved approximation algorithms for uniform connectivity problems," J. Algorithms, vol. 21, no. 2, pp. 434--450, 1996.]]
21. G. Kortsarz and Z. Nutov, "Approximating node connectivity problems via set covers," in Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pp.194--205. 2000.]]
22. Harold N. Gabow, "A representation for crossing set families with applications to submodular flow problems," in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Austin, TX, 1993), New York, 1993, pp. 202--211, ACM.]]
23. J. Cheriyan, S. Vempala, and A. Vetta, "An approximation algorithm for the minimum-cost k -vertex connected subgraph," SIAM J. Comput., vol. 32, no. 4, pp. 1050--1055 (electronic), 2003.]]
24. Dimitri Bertsekas, Network Optimization: Continuous and Discrete Models, Athena Scientific, Nashua, NH, 1998.]]
25. Volkan Isler, Sampath Kannan, and Kostas Daniilidis, "Sampling ased sensor-network deployment," in Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Sendai, Japan, Sept. 2004, pp. 172--177.]]
26. G. Kortsarz, R. Kraughgamer, and J. L. Lee, "Hardness of approximation for vertex-connectivity network-design problems," in Proceedings of 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pp. 185--199. 2002.]]
27. S. Arora, "Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems," J. ACM, vol. 45, no. 5, pp. 753--782, 1998.]]
28. J. S. B. Mitchell, "Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, k -MST, and related problems," SIAM J. Comput., vol. 28, no. 4, pp. 1298--1309 (electronic), 1999.]]
29. A. Czumaj and A. Lingas, "A polynomial time approximation scheme for Euclidean minimum cost k-connectivity," in Automata, languages and programming (Aalborg, 1998), vol. 1443 of Lecture Notes in Comput. Sci., pp. 682--694. Springer, Berlin, 1998.]]

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

• Theory of computation

  • Design and analysis of algorithms