Broadcast routing based on new link cost model for ad-hoc networks

ABSTRACT

For many wireless applications such as group conference and digital audio/video broadcast, it is necessary to send data to all devices that form an ad-hoc network. In this paper, minimum cost broadcast routing (MCBR) and minimum cost broadcast routing with forbidden set (MCBRF) are proposed. We first formulate a new cost model for the underlying graph by considering the distance between nodes, the remaining battery energy, and battery discharge pattern at each node. A minimum cost broadcast routing (MCBR) based on minimum cost graph spanning is described. Then forbidden set is introduced into MCBR to obtain MCBRF. The performance of the algorithms is investigated through simulations and contrasted against several other routing methods. A set of performance metrics are defined. The results on a variety of topologies of different sizes indicate that the spanning tree constructed by MCBRF algorithm has more leaf nodes than BIP and MMLE. Although the broadcast trees constructed by MWIS and MCDS have more leaf nodes, they suffer serious drawbacks in terms of energy consumption. Also, MCBR and MCBRF generate spanning trees that select nodes with higher remaining battery capacity as relay nodes. Thus more robust broadcast routes are established.

REFERENCES

• 1: Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, Power Consumption in Packet Radio Networks (Extended Abstract), Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, p.363-374, February 27-March 01, 1997
• 2: J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, "On the construction of energy-efficient broadcast and multicast trees in wireless networks," Proc. IEEE INFOCOM, pp. 585--594, 2000.
• 3: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 4: X. Y. Cheng, J. H. Sun, M. K. Min, and D. Z. Du, "Energy-efficient broadcast and multicast routing in ad-hoc wireless networks," Proc. IEEE International Conf. on Performance, Computing, and Communications, pp. 87--94, 2003.
• 5: W. Wang and B. H. Soong, "Collision-free and low-latency scheduling algorithm for broadcast operation in wireless ad-hoc networks," IEEE Communications Letters, pp. 793--795, October 2007.
• 6: Shuichi Sakai , Mitsunori Togasaki , Koichi Yamazaki, A note on greedy algorithms for the maximum weighted independent set problem, Discrete Applied Mathematics, v.126 n.2-3, p.313-322, 15 March 2003 [doi>10.1016/S0166-218X(02)00205-6]
• 7: Shankar M Banik , Sridhar Radhakrishnan, Minimizing broadcast latency in ad hoc wireless networks, Proceedings of the 45th annual southeast regional conference, March 23-24, 2007, Winston-Salem, North Carolina [doi>10.1145/1233341.1233450]
• 8: Wei Lou , Jie Wu, On Reducing Broadcast Redundancy in Ad Hoc Wireless Networks, Proceedings of the 36th Annual Hawaii International Conference on System Sciences (HICSS'03) - Track 9, p.305.2, January 06-09, 2003
• 9: D. B. West, Introduction to Graph Theory, Prentice Hall, 2000.
• 10: J. L. Gross and J. Yellen, Handbook of Graph Theory, CRC, 2003.
• 11: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
• 12: L. Campelli, M. Cesana, and R. Fracchia, "Directional broadcast forwarding of alarm messages in VANETs," Fourth Annual Conf. on Wireless on Demand Network Systems and Services, pp. 72--79, Jan 24-26, 2007.
• 13: O. Tonguz, N. Wisitpongphan, F. Bait, P. Mudaliget, and V. Sadekart, "Broadcasting in VANET," 2007 Mobile Networking for Vehicular Environments, pp. 7--12, May 11-11, 2007.
• 14: S. Gold, "A PSPICE macromodel for lithiumion batteries," Proc. Twelfth Annual Battery Conf. on Applications and Advances, pp. 215--222, 1997.
• 15: H. C. Wang and W. H. Chen, "Maximum path lifetime routing for ad-hoc wireless networks," Proc. IFIP/IEEE MWCN2007, pp. 166--170, Cork, Ireland, September 19-21, 2007.
• 16: H. C. Wang and Y. H. Wang, "Energy-efficient routing algorithms for wireless ad-hoc networks", Proc. 18th IEEE PIMRC, Athens, Greece, Sept. 2-6, 2007.
• 17: C. K. Yen, "Restricted independent domination problems on graphs," International Journal of Computer Systems Science & Engineering, vol. 23, no. 4, pp. 23--29, 2008.
• 18: X. Z. Zhang, "Efficient broadcast scheduling based on fuzzy clustering and Hopfield network for ad-hoc networks," Proc. International Conf. on Machine Learning and Cybernetics, vol. 6, pp. 3255--3260, 2007.
• 19: G. Tan, S. A. Jarvis, J. W. J. Xue, and S. D. Hammond, "Distributed broadcast scheduling in mobile ad-hoc networks with unknown topologies," Proc. IEEE International Symp. on Parallel and Distributed Processing, pp. 1--7, 2007.
• 20: C. H. Yen, Broadcast Routing Algorithm Based on Minimum Cost Spanning Tree for Ad-Hoc Networks, Master Thesis, Dept. of Electronic Engineering, National Ilan University, July, 2008.
• 21: Jae-Hwan Chang , Leandros Tassiulas, Maximum lifetime routing in wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.12 n.4, p.609-619, August 2004 [doi>10.1109/TNET.2004.833122]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Performance

Keywords:
ad-hoc network, bottleneck lifetime, broadcast routing, cost model, forbidden set, minimum cost spanning tree