Article Preview
Top1. 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.