On Calculating Stable Connected Dominating Sets Based on Link Stability for Mobile Ad Hoc Networks

Pi-Rong  Sheu; Hung-Yuan Tsai; Ying-Po Lee; Jyun-Yan  Cheng

doi:10.6180/jase.2009.12.4.06

On Calculating Stable Connected Dominating Sets Based on Link Stability for Mobile Ad Hoc Networks

Pi-Rong Sheu This email address is being protected from spambots. You need JavaScript enabled to view it.¹, Hung-Yuan Tsai¹, Ying-Po Lee¹ and Jyun-Yan Cheng¹

¹Department of Electrical Engineering, National Yunlin University of Science and Technology, Yunlin, Taiwan 640, R.O.C.

Received: October 27, 2006
Accepted: May 1, 2008
Publication Date: December 1, 2009

Download Citation: ||https://doi.org/10.6180/jase.2009.12.4.06

ABSTRACT

In a mobile ad hoc network (MANET), routing based on a connected dominating set (CDS) has been recognized as a promising approach. This is because as long as topological changes in a MANET do not affect its CDS, there is no need to reconfigure its CDS, which makes the routing tables in its CDS still valid. Due to the dynamic nature and the limited battery power of the mobile nodes, communication links between two nodes may break frequently. Such a phenomenon may destroy the structure of CDS, thus making reconfiguration of CDS unavoidable. Reconfiguring a CDS will result in high overheads caused by its re-computation and heavy information exchanges among the participating nodes. Therefore, a more stable CDS will directly lead to the performance improvement of the whole MANET. In this study, an efficient distributed algorithm is proposed that can establish a stable CDS by keeping a node with many weak links from being selected as a member of CDS. Computer simulations show that the CDSs generated by the proposed CDS-forming algorithm are more stable than those generated by other CDS-forming algorithms.

Keywords: Connected Dominating Set, Distributed Algorithm, Mobile Ad Hoc Network, Stability

REFERENCES

[1] Agarwal, S., Ahuja, A., Singh, J. P. and Shorey, R., “Route-Lifetime Assessment Based Routing (RABR) Protocol for Mobile Ad-Hoc Networks,” Proceedings of the 2000 IEEE International Conference on Communications(ICC 2000), Vol. 3, pp. 16971701 (2000).
[2] Alzoubi, K. M., Wan, P. J. and Frieder, O., “New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks,” Proceedings of the 35th Hawaii International Conference on System Sciences (HICSS 2002), pp. 38493855 (2002).
[3] Dai, F. and Wu, J., “An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 15, pp. 908920 (2004).
[4] Gerla, M. and Tsai, J. T. C., “Multicluster, Mobile, Multimedia Radio Network,” ACM/Baltzer Journal of Wireless Networks, Vol. 1, pp. 255265 (1995).
[5] Iwata, A., Chiang, C. C., Pei, G., Gerla, M. and Chen, T. W., “Scalable Routing Strategies for Ad Hoc Wireless Networks,” IEEE Journal on Selected Areas in Communications, Vol. 17, pp. 13691379 (1999).
[6] Ramanathan, R. and Steenstrup, M., “HierarchicallyOrganized, Multihop Mobile Wireless Networks for Quality-of-Service Support,” ACM/Baltzer Mobile Networks and Applications, Vol. 3, pp. 101119 (1998).
[7] Wu, J., “Extended Dominating-Set-Based Routing in Ad Hoc Wireless Networks with Unidirectional Links,” IEEE Transactions on Parallel and Distributed Systems, Vol. 13, pp. 866881 (2002).
[8] Wu, J., Dai, F., Gao, M. and Stojmenovic, I., “On Calculating Power-Aware Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks,” Journal of Communications and Networks, Vol. 4, pp. 5970 (2002).
[9] Wu, J. and Li, H., “A Dominating-Set-Based Routing Scheme in Ad Hoc Wireless Networks,” Telecommunication Systems, Vol. 18, pp. 1336 (2001).
[10] Dube, R., Rais, C. D., Wang, K. Y. and Tripathi, S. K., “Signal Stability-Based Adaptive Routing (SSA) for Ad Hoc Mobile Networks,” IEEE Personal Communications, Vol. 4, pp. 3645 (1997).
[11] Paul, K., Bandyopadhyay, S., Mukherjee, A. and Saha, D., “Communication-Aware Mobile Hosts in Ad-Hoc Wireless Network,” Proceedings of the 1999 IEEE International Conference on Personal Wireless Communication, pp. 8387 (1999).
[12] Tien, T. C. and Upadhyaya, S. J., “A Local/Global Strategy Based on Signal Strength for Message Routing in Wireless Mobile Ad-Hoc Networks,” Proceedings of the Academia/Industry Working Conference on Research Challenges, pp. 227232 (2000).
[13] Rappaport, T. S., Wireless Communications: Principles and Practice, Englewood Cliffs, NJ: PrenticeHall (1996).
[14] Chiang, C. C., Wireless Network Multicasting, Ph.D. dissertation, Department of Computer Science, University of California, Los Angeles (1998).
[15] Sheu, P. R., Tsai, H. Y., Lee, Y. P. and Cheng, J. Y., On Calculating Stable Connected Dominating Sets Based on Link Stability for Mobile Ad Hoc Networks, Technical Report, Department of Electrical Engineering, National Yunlin University of Science and Technology, Douliou, Yunlin 640, Taiwan, R.O.C. (2008).