Abstract: Broadcasting is a key operation in on-demand route discovery for mobile ad hoc networks. A simple approach to broadcasting is flooding. To transmit a packet of data, a host (source) node firstly broadcasts a route request (RREQ) packet to its neighbors. All neighboring nodes that receive this packet in turn rebroadcast the RREQ until it reaches the destination node. Due to this, flooding often results in large overhead, poor network performance and undesirable power consumption. A solution to overcome the broadcast storm problem is to use Connected Dominating Set (CDS), where the searching space for a route is reduced to nodes present in the set. In this study, an algorithm is designed for finding Minimum Connected Dominating Set (MCDS) using a dominator node based on weight value and which is more stable and stronger. The weight value is calculated based on the signal strength and the rate of change of displacement. It predicts the new distance using the current position and current velocity of the node. However, the predicted distance should be less than the predefined threshold or greater than zero. Moreover, the newly constructed MCDS is expected to adapt to topology changes due to link failure. Here, link failure is taken care of by a local repair algorithm that reconstructs the MCDS using only neighborhood information. Extensive simulations showed that the proposed algorithm, as compared to MaxD_CDS, has a significantly long lifetime and requires less number of control packets for route discovery.
INTRODUCTION
A wireless network could be one of two types: infrastructure network and ad hoc network. A mobile ad hoc network (MANET) consists of a set of mobile hosts that communicate with each other using multi-hop wireless links and requires no stationary infrastructure, such as a base station. Each node in the network can act both as a host and a router, forwarding data packets to other nodes.
Conventionally, most on-demand route discovery methods employ the flooding technique, where a mobile node blindly rebroadcasts a route request (RREQ) packet until a route to the destination is established. However, this approach often results in serious redundancy, contention and collisions in the network, as well as attracting large overhead, a problem widely referred to as the “broadcast storm”. To overcome this problem, several new broadcasting techniques have been proposed such as, among others, the probability-based method, area-based method and neighbor knowledge-based method.
In this study, an algorithm is proposed that looks for a more stable route by selecting dominator nodes (Connected Dominating Set) based on weighted value and which is stronger. In the weighted value algorithm, a node having minimum velocity and maximum signal strength is selected as a dominator node. The algorithm also reconstructs the Minimum Connected Dominating Set (MCDS) using the neighborhood information on account of link failure.
In the MST algorithm proposed by Leu and Chang (2012), the weight value of each node is calculated and a node with the highest weight value is selected as a dominator node; then, the shortest paths between the dominators are established. All nodes in the MST form the CDS. This algorithm has been found suitable for both static and dynamic environments.
Meghanathan (2010) proposed a minimum velocity-based CDS (MinV_CDS) algorithm to determine slow-moving nodes. They compare their algorithm MinV_CDS with the maximum density-based MaxD_CDS algorithm. Their algorithm having a longer life time compared to the MaxD_CDS algorithm. Fly and Meghanathan (2010) proposed an algorithm to construct stable CDS based on the Link Expiration Time (LET) and it gives longer life time than MaxD_CDS. Recently, Meghanathan and Terrell (2012) proposed another algorithm to construct a stable CDS using the Strong Neighborhood (SN). In this algorithm also, they compared it with the maximum density-based CDS MaxD_CDS and it gives a longer lifetime than MaxD_CDS.
Ramalakshmi and Radhakrishnan (2012) proposed an energy-efficient, stable MPR-based CDS construction by considering the energy and velocity of the nodes. Also, they implemented the route discovery process of AODV using CDS nodes.
Vijayakumar and Poongkuzhali (2012) introduced the Efficient Power Aware broadcasts, which is expected to establish an optimal path with suitable bandwidth and battery capacity. Chizari et al. (2012) developed a new greedy algorithm named Energy efficient MPREF_MPR and also few optimization techniques such as genetic algorithm, simulated annealing and Tabu search and the methods are compared.
Previously, a secure route optimization mechanism is proposed, namely Secure Dynamic Route Shortening (SDRS) (Revathi and Rangaswamy, 2012a) and Dynamic Route Shortening and Repairing Mechanism (DRSR) (Revathi and Rangaswamy, 2012b), for route shortening coupled with local repair. In these, route optimization takes place during the route maintenance and not during the route discovery phase. Revathi and Rangaswamy (2012c) proposed an algorithm named Efficient Route Discovery using Stable Connected Dominating Set for MANET, which selects as a dominator node the one with the minimum rate of change of displacement and maximum signal strength.
In this study, an algorithm is proposed that is an extension of the previous algorithm to handle link failure also. The link failure is taken care of by the local repair algorithm that reconstructs the MCDS.
PROPOSED ALGORITHM
An algorithm is proposed for stable MCDS construction based on displacement and radio signal strength. It is assumed that each node has the same antenna and power level to deliver the radio signal and also has the same transmission range R.
Route discovery: The working of the proposed algorithm has three stages. In the first stage, the dominating set of wireless graph is determined by identifying the minimum rate of change of displacement and maximum radio signal strength iteratively to discover the highest cover nodes. The second stage connects the dominating set through a Steiner tree. The third stage prunes this tree to form the MCDS.
| • | Stage 1: dominating set construction: The following steps are performed to construct the dominating set: |
| • | Initially each node is assigned a white color |
| • | The node i with the minimum rate of change of displacement and maximum radio signal strength is taken from the graph G(V,E) and assigned color black. This node is the dominator node |
Radio signal strength estimation: The two-ray ground reflection model is used to predict the received signal power of each packet. Each node keeps a record of the received signal strength of neighboring nodes. When a node receives a packet from a neighbor it measures the received signal strength, Pr:
where, Pt is the transmitted signal power; Gt and Gr are the antenna gains of the tramsitter and the receiver, respectively; and ht and hr are the heights of the transmitter and receiver antennas, respectively. L is the system loss. It is common to assume Gt and Gr to be 1 d is the distance from the transmitter and L = 1 in Ns-2 simulation (Fall and Varadhan, 2000) (http://nsnam.isi.edu/nsnam/index.php/User_Information).
Rate of change of displacement calculation: Each node sends its current position and velocity information to all its neighboring nodes with the help of “hello packets” after a fixed duration T (Beacon interval). Then it calculates the predicted new distance from its neighbors after the end of the beacon interval, based on the current velocities of the neighbors. It then checks whether the probability of predicted distance along any axis exceeds a predefined threshold distance, Rth1. If the probability of predicted distance remains greater than zero and less than Rth1, then that node will be considered into the dominating set.
For a particular node, say A its neighbor is either in front of it (say B) or behind it (say C). Let VA and VB be the current velocity of nodes A and B. The current distance between the nodes A and B is found as dAB = dA - dB. Rth1 and Rth2 are the threshold distances whose values are assumed based on the maximum range of communication, ie, Rth1 <Rmax/V2-X and Rth2 <Rth1+ X. Let T be the beacon interval. The new distance between nodes A and B is calculated after time T, as given below:
If dAB (new) < 0 or if dAB (new) > Rth1, the distance between A and B is not stable.
Unfavorable communication range: If dAB (new)>0 or dAB (new) >Rth1, the nodes are not come under the safe region it is not in the good communication range.
The nodes A and B are moving very fast and moves out of the communication range. Hence it is considered as an unfavorable communication range.
Favorable communication range: If dAB (new)>0 or dAB (new) <Rth1>, the nodes are in the good communication range. The nodes A and B are moving in such a way that the nodes are not moving out of the communication range. They are inside the communication range after a beacon time interval T. Hence it is considered as a favorable communication range.
Medium communication range: if dAB (new)>Rth1 and dAB (new)< Rth2 the nodes are in the medium communication range. The nodes are moving in the boundary region and it is considered as a medium communication range.
If the new probability of predicted distance between the nodes is greater than zero and less than Rth1, then the node keeps its velocity intact. In this way, a node calculates the velocity for all its neighbors for the next beacon interval. The final velocity for the next beacon interval is chosen as follows.
The weight value, Wi, to the velocity is calculated on the basis of information received from the ith node as:
where, prob(dew(predicted)) is the probability of predicted new distance between the nodes after time T.
Now, the node calculates its velocity for the next interval as:
where, Vi is the velocity calculated for the ith neighbor and Wi is its corresponding weight:
| • | All the neighbor nodes of the node i are assigned color gray |
| • | Repeat steps 2 to 4 until all the nodes in the graph G(V,E) are colored either as black or gray. |
| • | Stage 2: CDS formation: In this stage, a set of connectors, C, is found such that all the nodes in the dominating set, D, get connected using Steiner tree. The following steps are used for CDS formation: |
| • | A gray node that is connected to the maximum (k) number of black nodes is selected; it is assigned dark gray color |
| • | It is checked whether there exists a node that is connected to the adjacent black nodes in the dominating set, D |
| • | If D gets connected, the process is concluded. Else go to step 1 with k-1 number of black nodes. |
| • | Stage 3: MCDS construction: In this stage, the redundant nodes are deleted from the CDS. This involves the following steps: |
| • | A minimum degree node u is selected from the CDS graph |
| • | It is checked whether N[u] is a subset of N[1], N[2],....,N[n] |
| • | If step 2 returns true, then node u is removed |
| • | Otherwise the process is continued from step 1 |
Route maintenance: Topology changes due to node mobility can cause link failure. An alternative route can be constructed with a local repair algorithm, thereby avoiding to send RRER(Route Error) message to the source node to initiate the route discovery process again. To handle topology changes, a new MCDS that may be computationally stable should be constructed. The proposed algorithm takes care of link failure based on neighboring information. The main two issues to be considered in designing the local repair algorithm are that deletion of a non-MCDS node will not result in change of MCDS and that deletion of a MCDS node may result in new MCDS for the network:
| • | Let G (V,E) be the graph and assume node v to move from the communication range during data transfer |
| • | In the proposed algorithm, a MCDS is constructed using a set of nodes, say V’, with minimum rate of change of displacement and maximum radio signal strength and previous MCDS nodes, i.e. those present before deletion of node v, remain intact. Then, both MCDS are combined to give a complete MCDS. Nodes taken into consideration for local repair, i.e. set V’, include N(v) (open neighboring node of node v) and neighboring nodes of MCDS node present in N(v) |
| • | A pruning algorithm may be applied to remove unnecessary nodes from the MCDS |
RESULTS AND ANALYSIS
Simulation setup: The performance of the proposed method is evaluated in terms of CDS node size, CDS life time and hop count per path. The proposed algorithm MaxS_CDS is compared with the maximum density- based CDS MaxD_CDS and minimum velocity based CDS MinV_CDS.
The Ns2 simulation results are reported and analyzed here. Consider a network topology of 1000x1000 m, in which n nodes are randomly placed. Each node has a uniform transmission range of 250 m. With a fixed transmission range and network area, the network density is varied from low to high by altering the number of nodes. According to the Random Waypoint mobility model, each node starts moving from an arbitrary location to a randomly selected destination at a randomly chosen speed in the range of Vmin to Vmax. Each simulation is run for 600 s and repeated 8 to 10 times. The parameters used in simulations are listed in Table 1.
| Table 1: | Simulation parameters |
The performance of the MaxS_CDS is measured in terms of:
| • | CDS node size: This is the time-averaged value of the number of nodes that are part of the CDS, calculated using MaxD_CDS, MinV_CDS and MaxS_CDS algorithms. The MaxD_CDS algorithm is fully density-based and is expected to minimize the number of constituent nodes of the CDS. Although the MaxS_CDS algorithm gives preference to include (into the CDS) nodes with a relatively larger number of uncovered neighbors, the neighborhood of a node is decided based on the signal strength and rate of change of displacement. Thus, MaxS_CDS is more stability-oriented and minimizing the number of constituent nodes of the CDS is only a secondary objective. The MaxD_CDS tries to minimize the number of nodes in CDS, but MinV_CDS and MaxS_CDS do not give much importance to the number of nodes in the CDS. The results show that the CDS generated by our algorithm is larger or closer to MaxD_CDS and MinV_CDS. The CDS size increases with network density (Fig. 1a,b) |
| • | CDS life time: This is time elapsed between the discovery of a CDS and its disconnection, averaged over the entire duration of simulation. From Fig. 2 it is understood that the effective lifetime of MaxS_CDS is always significantly larger than that of MaxD_CDS, especially with increase in network density as well as node mobility. In the case of MinV_CDS and MaxS_CDS, the relatively large CDS node size greatly contributes to the life time of the CDS. As the basic nodes of MinV_CDS are selected based on the minimum velocity metric, the nodes of MaxS_CDS are selected based on the rate of change of displacement and signal strength. The proposed algorithm performs better than the other two algorithms, because the nodes generated in the CDS by our algorithm has minimum rate of change of displacement and maximum signal strength (Fig. 2a,b). |
| • | Hop count per path: This is the time-averaged hop count of individual source-destination (s-d) paths involving the CDS nodes as source, intermediate and destination nodes, averaged across all the s-d paths over the entire simulation period. The average hop count per path between the source–destination pair in the MaxD_CDS is less than that with MaxS_CDS. The hop count per path with MaxS_CDS is almost the same as that with MaxD_CDS in low-density networks and the difference between the hop count per path incurred with both CDS increases with increase in network density. MaxS_CDS incurs a slightly larger average hop count per path between the source and destination nodes in the network. But the CDS lifetime of MaxS_CDS is high as compared to MaxD_CDS (Fig. 3a,b) |
| Fig. 1(a-b): | CDS node size: Average number of nodes in MaxD_CDS, MinV_CDS and MaxS_CDS (a) Vmax = 5 m sec-1 and (b) Vmax = 25 m sec-1 |
| Fig. 2(a-b): | Average lifetime for MaxD_CDS, MinV_CDS and MaxS_CDS, (a) Vmax = 5 m sec-1 and (b) Vmax = 25 m sec-1 |
| Fig. 3(a-b): | Hop count per path through CDS nodes for MaxD_CDS, MinV_CDS and MaxS_CDS, (a) Vmax = 5 m sec-1 and (b) Vmax = 25 m sec-1 |
CONCLUSION
In this study, a new algorithm is proposed to find the MCDS based on the rate of change of displacement and signal strength. A node with minimum velocity and maximum signal strength is selected as a dominator. Then, the dominator is connected using the Steiner tree and a MCDS is constructed after pruning the unwanted (repeated) nodes. The proposed algorithm is used to determine a stable CDS with a slight increase in CDS node size. The proposed algorithm also acts as a local repair algorithm when link breaks occur in the network. The local repair algorithm reconstructs the MCDS using neighborhood information. As far as node mobility is concerned, MaxD_CDS is quite unstable, but in our proposed algorithm, MaxS_CDS can have a lifetime as large as that of MaxD_CDS.