Low-energy fault-tolerant bounded-hop broadcast in wireless networks

ABSTRACT

This paper studies asymmetric power assignments in wireless ad hoc networks. The temporary, unfixed physical topology of wireless ad hoc networks is determined by the distribution of the wireless nodes as well as the transmission power (range) assignment of each node. We consider the problem of bounded-hop broadcast under k-fault resilience criterion for linear and planar layout of nodes. The topology that results from our power assignment allows a broadcast operation from a wireless node r to any other node in at most h hops and is k-fault resistant. We develop simple approximation algorithms for the two cases and obtain the following approximation ratios: linear case--O(k); planar case--we first prove a factor of O(k³), which is later decreased toO(k²) by a finer analysis. Finally, we show a trivial power assignment with a cost O(h) times the optimum. To the best of our knowledge, these are the first nontrivial results for this problem.

REFERENCES

• 1: Kaveh Pahlavan , Allen H. Levesque, Wireless information networks, Wiley-Interscience, New York, NY, 1995
• 2: Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, Power consumption in packet radio networks, Theoretical Computer Science, v.243 n.1-2, p.289-305, July 28, 2000 [doi>10.1016/S0304-3975(98)00223-0]
• 3: Andrea E. F. Clementi , Paolo Penna , Riccardo Silvestri, Hardness Results for the Power Range Assignmet Problem in Packet Radio Networks, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.197-208, August 08-11, 1999
• 4: C. Ambuhl, A. Clementi, P. Penna, G. Rossi, and R. Silvestri, "Energy consumption in radio networks: Selfish agents and rewarding mechanisms," Theor. Comput. Sci., vol. 343, no. 1-2, pp. 27-41, 2004.
• 5: C. Ambuhl, A. Clementi, M. D. Ianni, A. Monti, G. Rossi, and R. Silvestri, "The range assignment problem in non-homogeneous static ad-hoc networks," in Proc. IPDPS'04, Santa Fe, NM, Apr. 2004.
• 6: A. Clementi, G. Huiban, P. Penna, G. Rossi, and Y. Verhoeven, "Some recent theoretical advances and open questions on energy consumption in ad-hoc wireless networks," in Proc. ARACNE'02, 2002, pp. 23-38.
• 7: S. O. Krumke, R. Liu, E. L. Lloyd, M. V. Marathe, R. Ramanathan, and S. S. Ravi, "Topology control problems under symmetric and asymmetric power thresholds," in Proc. AdHoc-NOW'03, 2003, pp. 187-198.
• 8: Hanan Shpungin , Michael Segal, k-fault resistance in wireless ad-hoc networks, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080826]
• 9: Paz Carmi , Michael Segal , Matthew J. Katz , Hanan Shpungi, Fault-Tolerant Power Assignment and Backbone in Wireless Networks, Proceedings of the 4th annual IEEE international conference on Pervasive Computing and Communications Workshops, p.80, March 13-17, 2006 [doi>10.1109/PERCOMW.2006.55]
• 10: G. Calinescu and P.-J. Wan, "Range assignment for high connectivity in wireless ad hoc networks," in Proc. AdHoc-NOW'03, 2003, pp. 235-246.
• 11: MohammadTaghi Hajiaghayi , Nicole Immorlica , Vahab S. Mirrokni, Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939016]
• 12: X. Jia, D. Kim, S. Makki, P.-J. Wan, and C.-W. Yi, "Power assignment for k-connectivity in wireless ad hoc networks," in Proc. INFOCOM'05 , Miami, FL, Mar. 2005, pp. 2206-2211.
• 13: Michael Segal , Hanan Shpungin, On construction of minimum energy k-fault resistant topologies, Ad Hoc Networks, v.7 n.2, p.363-373, March, 2009 [doi>10.1016/j.adhoc.2008.03.008]
• 14: E. Althaus, G. Calinescu, I. Mandoiu, S. Prasad, N. Tchervenski, and A. Zelikovsky, "Power efficient range assignment in ad-hoc wireless networks," in Proc. WCNC'03, 2003, pp. 1889-1894.
• 15: Douglas M. Blough , Mauro Leoncini , Giovanni Resta , Paolo Santi, On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.71-82, August 25-30, 2002
• 16: Gruia Calinescu , Ion I. Mandoiu , Alexander Zelikovsky, Symmetric Connectivity with Minimum Power Consumption in Radio Networks, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.119-130, August 25-30, 2002
• 17: Joseph Cheriyan , Santosh Vempala , Adrian Vetta, Approximation algorithms for minimum-cost k-vertex connected subgraphs, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509955]
• 18: Andrea E. F. Clementi , Paolo Penna , Riccardo Silvestri, On the power assignment problem in radio networks, Mobile Networks and Applications, v.9 n.2, p.125-140, April 2004 [doi>10.1023/B:MONE.0000013624.32948.87]
• 19: M. T. Hajiaghayi, G. Kortsarz, V. S. Mirrokni, and Z. Nutov, "Power optimization for connectivity problems," in Proc. IPCO'05, Berlin, Germany, Jun. 2005, pp. 349-361.
• 20: Errol L. Lloyd , Rui Liu , Madhav V. Marathe , Ram Ramanathan , S. S. Ravi, Algorithmic aspects of topology control problems for ad hoc networks, Mobile Networks and Applications, v.10 n.1-2, p.19-34, February 2005 [doi>10.1145/1046430.1046433]
• 21: Anand Srinivas , Eytan Modiano, Minimum energy disjoint path routing in wireless ad-hoc networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938999]
• 22: J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, "On the construction of energy-efficient broadcast and multicast trees in wireless networks," in Proc. INFOCOM'00, Tel-Aviv, Israel, Mar. 2000, pp. 585-594.
• 23: Jeffrey E. Wieselthier , Gam D. Nguyen , Anthony Ephremides, Energy-efficient broadcast and multicast trees in wireless networks, Mobile Networks and Applications, v.7 n.6, p.481-492, December 2002 [doi>10.1023/A:1020716919751]
• 24: P.-J. Wan, G. Calinescu, X. Li, and O. Frieder, "Minimum-energy broadcast routing in static ad hoc wireless networks," in Proc. INFOCOM'01 , Anchorage, AK, Apr. 2001, pp. 1162-1171.
• 25: Mario Čagalj , Jean-Pierre Hubaux , Christian Enz, Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570667]
• 26: C. Ambuhl, "An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks," in Proc. ICALP'05, Lisbon, Portugal, Jul. 2005, vol. 3580, pp. 1139-1150.
• 27: Michele Flammini , Alfredo Navarra , Ralf Klasing , Stéphane Pérennes, Improved approximation results for the minimum energy broadcasting problem, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022644]
• 28: J. Cartigny, D. Simplot, and I. Stojmenovic, "Localized minimum-energy broadcasting in ad-hoc networks," in Proc. INFOCOM'03, San Francisco, CA, Mar.-Apr. 2003.
• 29: S. Banerjee, A. Misra, J. Yeo, and A. Agarwala, "Energy-efficient broadcast and multicast trees for reliable wireless communication," in Proc. WCNC'03, 2003, vol. 1, pp. 660-667.
• 30: F. Bian, A. Goel, C. S. Raghavendra, and X. Li, "Energy-efficient broadcasting in wireless ad hoc networks lower bounds and algorithms," J. Interconnect. Netw., vol. 3, no. 3-4, pp. 149-166, 2002.
• 31: René Beier , Peter Sanders , Naveen Sivadasan, Energy Optimal Routing in Radio Networks Using Geometric Data Structures, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.366-376, July 08-13, 2002
• 32: G. Calinescu , S. Kapoor , M. Sarwat, Bounded-hops power assignment in ad hoc wireless networks, Discrete Applied Mathematics, v.154 n.9, p.1358-1371, 1 June 2006 [doi>10.1016/j.dam.2005.05.034]
• 33: C. Ambühl, A. Clementi, M. D. Ianni, N. Lev-Tov, A. Monti, D. Peleg, G. Rossi, and R. Silvestri, "Efficient algorithms for low-energy bounded-hop broadcast in ad-hoc wireless networks," in Proc. STACS'04, Montpellier, France, Mar. 2004, vol. 2996, pp. 418-427.
• 34: S. Funke and S. S. Laue, "Bounded-hop energy-efficient broadcast in low-dimensional metrics via coresets," in Proc. STACS'07, Aachen, Germany, Feb. 2007, vol. 4393, pp. 272-283.
• 35: Andrea E. F. Clementi , Afonso Ferreira , Paolo Penna , Stephane Perennes , Riccardo Silvestri, The Minimum Range Assignment Problem on Linear Radio Networks, Proceedings of the 8th Annual European Symposium on Algorithms, p.143-154, September 05-08, 2000
• 36: Andrea E. F. Clementi , Paolo Penna , Riccardo Silvestri, The Power Range Assignment Problem in Radio Networks on the Plane, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, p.651-660, February 01, 2000
• 37: Budhaditya Deb , Badri Nath, On the node-scheduling approach to topology control in ad hoc networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062693]
• 38: T. A. ElBatt and A. Ephremides, "Joint scheduling and power control for wireless ad hoc networks," in Proc. INFOCOM, 2002, pp. 976-984.
• 39: Jeffrey E. Wieselthier , Gam D. Nguyen , Anthony Ephremides, Algorithms for energy-efficient multicasting in static ad hoc wireless networks, Mobile Networks and Applications, v.6 n.3, p.251-263, June 2001 [doi>10.1023/A:1011478717164]
• 40: C.-Y. Lin, S.-Y. Kuo, and D. S. L. Wei, "Reliable multicast based on k-connected graph," in Proc. IMSA'02, 2002, pp. 409-414.
• 41: Gang Lu , Bhaskar Krishnamachari, Minimum latency joint scheduling and routing in wireless sensor networks, Ad Hoc Networks, v.5 n.6, p.832-843, August, 2007 [doi>10.1016/j.adhoc.2007.03.002]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Fault tolerance

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
approximation methods, fault tolerance, minimum-energy control, radio broadcasting, wireless networks