Distributed algorithm for efficient construction and maintenance of connected k-hop dominating sets in mobile ad hoc networks

被引:26
作者
Yang, Hong-Yen [1 ]
Lin, Chia-Hung [1 ]
Tsai, Ming-Jer [1 ]
机构
[1] Natl Tsing Hua Univ, Dept Comp Sci, Hsinchu 300, Taiwan
关键词
algorithm/protocol design and analysis; mobile ad hoc network; network topology; localized communication; routing protocols;
D O I
10.1109/TMC.2007.70736
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
A k-hop dominating set is a subset of nodes such that each node that is not in the set can be reached within k hops from at least one node in the set. A connected k-hop dominating set can be used for disseminating topology update packets or route request packets, in which the flooding search space is reduced to the set, resulting in significant flooding overhead reduction in broadcast-related applications. In mobile ad hoc networks, a connected k-hop dominating set may become disconnected due to node mobility or switch-off, which necessitates the reformation of the k-hop dominating set. In this paper, we identify a sufficient condition that guarantees the connectivity of the virtual backbone. The condition can be verified in a distributed manner by the node only having the link information of its neighbors. (Unless specified otherwise, the term "neighbor" denotes a "1-hop neighbor." The link information of neighbors can be obtained by 2-hop neighbor information or 1-hop neighbor positions [ 4], [ 16].) With the help of this condition, we propose a distributed algorithm for efficiently constructing and maintaining connected k-hop dominating sets in mobile ad hoc networks. Simulations show that our connected k-hop dominating set is small and stable and needs little maintenance overhead in the Random-Walk Mobility and Gauss-Markov Mobility Models.
引用
收藏
页码:444 / 457
页数:14
相关论文
共 28 条
[21]   Adaptive Distributed Power Management Algorithm for Interference-aware Topology Control in Mobile Ad Hoc Networks [J].
Pradhan, Nuraj ;
Saadawi, Tarek .
2010 IEEE GLOBAL TELECOMMUNICATIONS CONFERENCE GLOBECOM 2010, 2010,
[22]   Honey bee algorithm-based efficient cluster formation and optimization scheme in mobile ad hoc networks [J].
Ahmad, Masood ;
Ikram, Ataul Aziz ;
Lela, Rabo ;
Wahid, Ishtiaq ;
Ulla, Riaz .
INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORKS, 2017, 13 (06)
[23]   A novel DSR-based energy-efficient routing algorithm for mobile ad-hoc networks [J].
Garcia, JE ;
Kallel, A ;
Kyamakya, K ;
Jobmann, K ;
Cano, JC ;
Manzoni, P .
2003 IEEE 58TH VEHICULAR TECHNOLOGY CONFERENCE, VOLS1-5, PROCEEDINGS, 2003, :2849-2854
[24]   A distributed token based h-out of-k Mutual Exclusion protocol for mobile ad hoc networks [J].
Benchaiba, Mahfoud ;
Nacer, Mohamed Ahmed .
INTERNATIONAL JOURNAL OF AD HOC AND UBIQUITOUS COMPUTING, 2010, 5 (02) :117-135
[25]   Clustering overhead and convergence time analysis of the mobility-based multi-hop clustering algorithm for mobile ad hoc networks [J].
Er, Inn Inn ;
Seah, Winston K. G. .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2006, 72 (07) :1144-1155
[26]   A Coverage-Aware Distributed k-Connectivity Maintenance Algorithm for Arbitrarily Large k in Mobile Sensor Networks [J].
Akram, Vahid Khalilpour ;
Dagdeviren, Orhan ;
Tavli, Bulent .
IEEE-ACM TRANSACTIONS ON NETWORKING, 2022, 30 (01) :62-75
[27]   IMPROVING PERFORMANCE OF MOBILE AD HOC NETWORKS USING EFFICIENT TACTICAL ON DEMAND DISTANCE VECTOR (TAODV) ROUTING ALGORITHM [J].
Uddin, Mueen ;
Rahman, Azizah Abdul ;
Alarifi, Abdulrahman ;
Talha, Muhammad ;
Shah, Asadullah ;
Iftikhar, Mohsin ;
Zomaya, Albert .
INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL, 2012, 8 (06) :4375-4389
[28]   An Efficient Algorithm for Deriving Mobility Scenarios from New Mobility Model Representing Spatially and Temporally Biased Change of Node Mobility and Node Density for Mobile Ad Hoc Networks [J].
Shigeta, Takahiro ;
Kohno, Eitaro ;
Kakuda, Yoshiaki .
2014 IEEE 11TH INTL CONF ON UBIQUITOUS INTELLIGENCE AND COMPUTING AND 2014 IEEE 11TH INTL CONF ON AUTONOMIC AND TRUSTED COMPUTING AND 2014 IEEE 14TH INTL CONF ON SCALABLE COMPUTING AND COMMUNICATIONS AND ITS ASSOCIATED WORKSHOPS, 2014, :556-562