Abstract: The invulnerability of mobile ad hoc network is very important to the routing protocol. This study presents a mathematically tractable model of node motion to derive a precise relationship between mobility and connection stability. We improve the first order energy consumption model with dynamic clustering first and then build an incidence matrix to depict the connectivity of the network nodes in a dynamic network model. Finally, this study simulates the network invulnerability related to time. As a result, it validates the high invulnerability of the dynamic clustering ad hoc networks.
INTRODUCTION
A multi-hop wireless ad hoc network is a collection of nodes that communicate with each other without any established infrastructure or centralized control. Each of these nodes is a wireless transceiver that transmits and receives at a single frequency band which is common with each other. However, they are limited by their transmitting and receiving capabilities. Therefore, they cannot directly reach all of the nodes in the network as most of the nodes are outside the direct rang. In such a situation, one of the possibilities for the information transmission between two nodes that are not in the range to have a direct communication is to use other nodes in the network (Johnson, 1994).
To investigate the impact of mobility on network operation, previous work has relied mainly on simulations with mobility models that describe the manner in which nodes move through space (Hill, 2003). These mobility models typically aim to provide an accurate description of the behavior of a network consisting of pedestrians or moving vehicles. It is unlikely that a single mobility model can be applied to all types of networks and for this reason, new mobility models are being continuously developed. It has proven to be very difficult to analyse the relationship between these mobility models and the network connectivity due to the many parameters affecting the network operation, such as node speed, pause time, node density and transmission range (Tillett et al., 2002).
The performance of mobile ad hoc networks is highly sensitive to changes in node-to-node connections (communication links) caused by node movement. The kind of link instability has proven very difficult to analyse mathematically, so previous work has relied heavily on simulation. In this study, we present a mathematically tractable model of node motion and node damage, the different rates of damaged nodes, the inconstant velocity model and uses it to derive a precise relationship between mobility and connection stability (Wadaa et al., 2003). We further investigate connection stability in multi-hop communication and discover some underlying properties of previously proposed mobility metrics. In particular, we demonstrate that link duration has a strong invariant relationship with the stability of multi-hop connections for a wide range of mobility models and thus is an excellent mobility metric (Krishnan and Starobinski, 2003).
We approach the problem as follows. Firstly, we set up a relatively simple and mathematically tractable mobility model. Then we develop an analytic expression for connective stability to depict the connectivity of the network nodes in a dynamic network model in multihop communication. Finally, this paper brings forward a determinant algorithm of the network connectivity and a calculate method (Heinzelman et al.,2000). We simulate the damage situation of the dynamic ad hoc network through random trials and quantification ally calculates the ratio of the network invulnerability, which related to time. As a result, it validates the high invulnerability of the mobile ad hoc network.
ENERGY CONSUMPTION MODEL
A sensor uses its energy to carry out three main actions: acquisition, communication and data processing. Although varying according to the monitoring type, the power consumption to perform the data acquisition is not very important. The communications consume model is shown in Fig. 1.
| Fig. 1: | Communication power consumption model in MANET |
The communications consume model is shown in Fig. 1, to transmit a message of l bits over a distance of d meters, the energy that transmitter consumes is given by:
| (1) |
where, Eelec, l, d and εamp denote energy of electronic signals; size of a message, distance between transmitter and receiver; and amplification factor, respectively. In addition, d0, M and dtoBS represent the limit distance over which the transmission factors change their value, the size of the area and the distance to the base station.
To receive a message of l bits, the receiver consumes:
| (2) |
When there are N nodes in MANET, the optimal number of the Cluster-Heads (CHs) (Jung et al., 2007):
| (3) |
Generally, we have Eelec = 50 nj/bit, εamp = 0.0013 pj/bit/ m4 and εfs = 10 pj/bit/m2.
DYNAMIC CLUSTERING ALGORITHMS
One of the most common clustering algorithms, the dynamic clustering technique, aims at assigning each pattern data set to the cluster having the nearest centroid. The basic steps of clustering are (Ali et al., 2009):
| Step 1: | All nodes are assigned a cluster number between 1 and k randomly, k is number of cluster desired which can be computed from Eq. 3 |
| Step 2: | Find the cluster center of each cluster |
| Step 3: | For each node, find the cluster center that is closest to the node. Assign the node to the cluster whose center is closest to it |
| Step 4: | Re-compute the cluster centers with the new assignment of nodes |
| Step 5: | Repeat Steps 3 and 4 till clusters do not change or within a fixed number of times |
Dynamic clustering algorithms employ an iterative approach to group the node into a predefined k number of clusters by minimizing a cost function (Ranjan and Khalil, 2007):
| (4) |
where, Cj is the center of j th cluster and is the center nearest to node object dj, n is the number of elements in node set, q is an integer which defines the nature of the distance function. For numeric valued nodes sets, a cluster center is represented by the mean value of each attribute and the mean value is computed over all objects belonging to the cluster.
ALGORITHM FOR INVULNERABILITY ANALYZE
To simulate the movement of the nodes in the mobile ad hoc network, we set up a ad hoc network scenario. There are N nodes in this scenario. Let (xi (t), yi (t)), vi (t) θi (t) be the coordinate, the velocity and the moving direction of mobile node i at time t. In our approach, these initial parameters are set with random. We assume a free space propagation model, where the received signal strength solely depends on its distance to the transmitter. These nodes are limited by their transmitting and receiving capabilities. Therefore, they cannot directly reach all of the nodes in the network as most of the nodes are outside the direct rang (Heinzelman et al., 2002). In such a scenario, if two nodes can communicate with each other, the distance between these two nodes cannot exceed R. At arbitrary time t, the coordinate of the node i can be represented by Eq. 5 and the distance between node i and node j can be represented by Eq. 6.
| (5) |
| (6) |
The algorithm for invulnerability analyze has very important senses to the research on mobile ad hoc network. But it has proven to be difficult to analyze mathematically. In this section, we can use graphic to represent the link and nodes in the networks. Thus we change the stability problem to the graphic problem. In the graphic problem, we can use the connective matrix to depict the connectivity of the network nodes in a dynamic network model (Camp et al., 2002). We defined connective matrix as D (t) = (dij (t))NxN, the element in this matrix should satisfied in Eq. 7.
| (7) |
We denoted D(i) (t) as the ith power of the matrix D (t). Therefore, the connective matrix can be represented by Eq. 8.
| (8) |
Where, D(m) (t) = (dit(m) (t))NxN if dit(m) = 0 in this matrix, it means that node I cannot reach node j within m hops (i ≠ j, m≥1). The graphic is not connectively if and only if there exist element d'ij (t) = 0, I ≠j in matrix D' (t).
Therefore, we denote X (t) as the number of nonzero elements in the D' (t) and it can be used as a new index to estimate network invulnerability (Bianchi, 2000; Michierdi and Molva, 2003).
In mobile ad hoc network, we randomly choose r% nodes and damaged their communication ability to other nodes in the network to research the invulnerability in the scenario. Once the node which labeled i is damaged, the elements in the connective matrix will be changed, they should stratify Eq. 9.
| (9) |
It shows the node i can not communicate with other nodes in the
network. It forms a new matrix
| (10) |
The algorithm diagram is shown in Fig. 2.
| Fig. 2: | Algorithm diagram for invulnerability analyze |
SIMULATIONS
We use MATLAB to simulate the Energy Consumption Model. When the number of the nodes in sensor filed is growing, more CHs are needed. In dynamic clustering model our simulation models a network of 926 mobile nods placed randomly within a 1000x1000 M area. From Eq. 3, we find that when there are 45 CHs in the sensor filed, the cost of energy consumption is the least. Using dynamic clustering model, we assign all the nodes in sensor filed into 45 classes, there are 45 classes shown in Fig. 3.
In ad hoc network, nodes are moving with time. In our simulation, we assume that the velocity of the nodes is in the interval (0.2 m sec-1) with a normal distribution and the angle of the move is in the interval (0.2 m sec-1) with a normal distribution. When the rate of damaged nodes is 10%, the result is given by Fig. 4.
| Fig. 3: | Simulation of the dynamic clustering model |
| Fig. 4: | The invulnerability index changed with the time when r = 10% |
From Fig. 4, it validates the high invulnerability of the mobile ad hoc network. The mobility has little impact on invulnerability index. When the rate of the damaged nodes is 10%, the invulnerability index fluctuations at interval 0.8±0.01.
When the rate of damaged nodes is 20%, the result is given by Fig. 5. When the rate of the damaged nodes is 20%, the invulnerability index fluctuations at interval 0.66±0.02.
In this mobile ad hoc network, we assume the maximum distance between two nodes which they can communicate with each other is 100 M. It’s just one tenth of the length of the network area. Our simulation models different rates of damaged nodes in the network. We assume that if two nodes can communicate with each other they cannot exceed 2 hops. The damage rate vary from 0~100%, the invulnerability index is presented by Fig. 6.
From Fig. 6, we can find that if 10% nodes are damaged in the ad hoc network, the invulnerability index will be reduced by 20%; if 20% nodes are damaged, the invulnerability index will be reduced by 38.75%, many communication requests will be denied.
| Fig. 5: | The invulnerability index changed with the time when r = 20% |
| Fig. 6: | The relationship between the rate of the damage nodes and the invulnerability index |
In further, we discuss the maximum hops is not a constant to research the relationship between invulnerability index with maximum hop and rate of the damaged nodes in the network. The hops which two nodes can communicate with each other they cannot exceed is varied from 2 to 6 hops and the damage rate vary from 0-100%, the invulnerability index is shown in Fig. 7.
From Fig. 7, we can find that both the maximum hops and the rate of the damaged nodes in the network will have an effect on invulnerability index. The rate of the damaged nodes has a great effect on invulnerability index, while the maximum has a little effect.
For performance evaluations, this paper simulation our method and other methods that have been proposed in literature with the rate of the damaged nodes is 10%, it is shown in Fig. 8.
| Fig. 7: | The relationship between invulnerability indexes with maximum
hop and rate of the damaged nodes in the network |
| Fig. 8: | The simulation of our method and other methods |
From Fig. 8, we can find that our method is better than other methods that have been proposed in literature.
CONCLUSIONS
We have proposed an energy-aware routing algorithm for MANET which can also run efficiently under best-effort traffic. We have improved the first order energy consumption model with dynamic clustering; based on the clustering, we resent a mathematically tractable model of node motion and nodes damage, the different rates of damaged nodes, the inconstant velocity model and use it to derive a precise relationship between mobility and connection stability. We present a new index to estimate network invulnerability and then build an incidence matrix to depict the connectivity of the network nodes in a dynamic network model. Finally, we simulate the damage situation of the dynamic ad hoc network through random trials and quantification ally calculates the ratio of the network invulnerability, which related to time. As a result, it validates the high invulnerability of the mobile ad hoc network.
ACKNOWLEDGMENT
The study is supported by the National Natural Science Foundation of China (60872020) and Zhejiang Provincial NSF undergrant No. Y1090645.