Navigation Route based Stable Connected Dominating Set for Vehicular Ad Hoc Networks

Navigation Route based Stable Connected Dominating Set for Vehicular Ad Hoc Networks

Yishun Chen (Sun Yat-sen University, Guangzhou, China & SYSU-CMU Shunde International Joint Research Institute, Shunde, China), Weigang Wu (Sun Yat-sen University, Guangzhou, China & SYSU-CMU Shunde International Joint Research Institute, Shunde, China) and Hui Cao (Sun Yat-sen University, Guangzhou, China & SYSU-CMU Shunde International Joint Research Institute, Shunde, China)
Copyright: © 2015 |Pages: 15
DOI: 10.4018/IJWSR.2015010102


Forming a virtual backbone has been always a significant technique for ad hoc networks to achieve high efficiency in various applications, including mobility management, broadcast based information dissemination, etc. This is especially true for Vehicular Ad Hoc Network (VANET), because most of VANET applications rely on broadcasting messages. Among others, constructing the Connected Dominating Set (CDS) is a popular approach to forming virtual backbone in ad hoc networks, including VANETs. Although quite a lot of work has been done on CDS algorithms for ad hoc networks, almost all existing algorithms focus on minimizing the size of CDS, i.e. the number of nodes in CDS. In this paper, the authors consider to improve the stability of CDS, i.e. to reduce the changes of CDS during the runtime of a VANET. By making use of vehicle navigation route, the authors propose a new metric to selecting CDS node with high stability. Then, based on the new metric the authors design a CDS algorithm, which can construct a CDS with higher stability than the CDS by existing algorithms. Such advantage is validated via extensive simulations.
Article Preview

1. Introduction

Vehicular Ad hoc NETwork (VANET) (Hartenstein & Laberteaux, 2008) enables vehicles to communicate with other vehicles (V2V) or infrastructures (V2I) via wireless communications. VANETs can help drivers to acquire real-time information about road conditions, which is important for drivers to react on time. VANETs are attracting more and more attention all over the world. Applications of VANET range from driving support services, e.g. warning messages dissemination (Xu, Mark, Ko & Sengupta, 2007; Pandey, Garg & Gore, 2012) and route selection (Nadeem, Dashtinezhad, Liao & Iftode, 2004), to Internet access (Willke, Tientrakool & Maxemchuk, 2009; Wang, Fan C, Hsu, Sun & Yang 2014).

Due to the characteristics of VANET applications, broadcasting is the predominating communication mode in VANETs (Li, Wang, 2007; Willke, Tientrakool & Maxemchuk, 2009; Tseng, Ni, Chen & Sheu, 2002). To achieve high scalability and low communication cost, a virtual backbone is usually adopted in VANETs for broadcasting or other scenarios, including medium access control (Yvonne, Bernhard & Peter, 2007; Su & Zhang, 2007), packet routing (Li & Wang, 2007), broadcasting (Bononi & Felice, 2007), and other network services (Wu, Wang, Ben, Wang & Mohsen, 2012). Due to the challenge of high topology dynamicity (Yousefi, Mousavi & Fathy, 2006), how to construct a virtual backbone has been a hot topic in the research of VANETs for many years.

Among others, establishing a Connected Dominating Set (CDS) (Pricilla Rajakumari & Bhuvaneswari, 2013; Meghanathan & Terrell, 2012; Cha, Ryu, Kim & Jeon, 2013) has been widely used to cope with topology dynamicity in establishing backbone.

On the other hand, CDS formation in VANETs is not a trivial task due to the high dynamics of vehicle mobility. Although quite a number of CDS algorithms (Meghanathan & Terrell,2012; Sheu, Tsai, Lee & Cheng, 2009; R. Ramalakshmi & S. Radhakrishnan, 2012; Ramalakshmi & Radhakrishnan, 2012) have been proposed for general ad hoc networks, CDS in VANETs is rarely studied (Meghanathan & Dasari, 2013). More importantly, almost all existing CDS algorithms focus on how to reduce the number of nodes in the CDS set. This is because the size of CDS will significantly affect the efficiency of upper layer broadcasting or other application protocols. Roughly, a smaller CDS set will save communication cost more than a larger one.

Differently, in this paper, we consider how to construct a stable CDS in VANETs. Due to topology changes or other dynamicity factors, the CDS of a VANET may need to be changed from time to time. A stable CDS may keep unchanged for a longer time than an unstable one, so that less cost is consumed for constructing and maintaining CDS.

To construct a stable CDS, we propose a new algorithm to select CDS nodes according to the navigation route information of vehicles. Nowadays, navigation systems based on GPS or alternative techniques have been very popular in vehicles. The driving route of a vehicle is usually planned by the navigation system when a vehicle starts. The rout may also been changed during driving. Such a route obviously indicates the future movement path of the corresponding vehicle. Then, CDS can be determined based on such navigation route.

Complete Article List

Search this Journal:
Open Access Articles
Volume 17: 4 Issues (2020): Forthcoming, Available for Pre-Order
Volume 16: 4 Issues (2019): 2 Released, 2 Forthcoming
Volume 15: 4 Issues (2018)
Volume 14: 4 Issues (2017)
Volume 13: 4 Issues (2016)
Volume 12: 4 Issues (2015)
Volume 11: 4 Issues (2014)
Volume 10: 4 Issues (2013)
Volume 9: 4 Issues (2012)
Volume 8: 4 Issues (2011)
Volume 7: 4 Issues (2010)
Volume 6: 4 Issues (2009)
Volume 5: 4 Issues (2008)
Volume 4: 4 Issues (2007)
Volume 3: 4 Issues (2006)
Volume 2: 4 Issues (2005)
Volume 1: 4 Issues (2004)
View Complete Journal Contents Listing