Title: Construction and maintenance of k-hop CDS in MANET with two classes of mobile terminals

Authors: Eiichiro Kodama; Bhed Bahadur Bista; Jiahong Wang; Toyoo Takata

Addresses: Faculty of Software and Information Science, Iwate Prefectural University, 152-52 Sugo, Takizawa, Iwate 020-0693, Japan ' Faculty of Software and Information Science, Iwate Prefectural University, 152-52 Sugo, Takizawa, Iwate 020-0693, Japan ' Faculty of Software and Information Science, Iwate Prefectural University, 152-52 Sugo, Takizawa, Iwate 020-0693, Japan ' Faculty of Software and Information Science, Iwate Prefectural University, 152-52 Sugo, Takizawa, Iwate 020-0693, Japan

Abstract: Since mobile ad hoc networks (MANETs) do not have fixed or predefined infrastructures, nodes need to frequently flood control messages to discovery and maintain routes, which causes performance problems in traffic and energy consumption, contention, and collision. A general solution is to construct a virtual backbone as the basis of routing and broadcasting, and the connected dominating set (CDS) has been widely used. This paper presents a distributed approach to constructing and maintaining a k-hop CDS in the MANET with two classes of nodes. A unique characteristic that differentiates the proposed approach from existing ones is that, any value can be specified for k, and a larger k contributes to a smaller CDS. If k is large enough, the resulting CDS will contain only a single node. Especially, the constructed CDS will be more robust, and will be little affected by the topology change of a MANET.

Keywords: mobile ad hoc networks; MANETs; virtual backbone; k-hop connected dominating set; distributed algorithms; routing.

DOI: 10.1504/IJSSC.2018.094464

International Journal of Space-Based and Situated Computing, 2018 Vol.8 No.2, pp.70 - 79

Received: 29 Dec 2017
Accepted: 19 Feb 2018

Published online: 03 Sep 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article