Abstract: In this research, we focus on network reliability in wireless communication networks. We introduce a stochastic reliability model based on combination of the free space and the two ray ground propagation models. The link reliability in static and dynamic networks is determined using real and approximate methods. Link reliability of different networks is determined using our approximate method and traditional methods based on Monte Carlo simulation for static and dynamic networks and the effects of using our approximate method are investigated. The results for two random distributions of agents based on Monte Carlo simulation are compared to the real connectivity method to show the superiority of our approach. In particular, we provide a new measure of network reliability as a function of the distance between mobile agents, quality of transmitters and receivers and a model of reliability degradation.
INTRODUCTION
Mobile ad hoc networks (MANET) are decentralized, self-organizing, rapidly deployable, wireless networks, providing connectivity for a wide array of electronic devices. In their purest form, MANETs consist of a collection of mobile nodes which are distributed over a geographical area, who communicate blocks of data via radio links according to a set of predefined protocols (Timo et al., 2005).
Reliability is widely used in engineering. In networks, connectivity reliability means the probability that there exists at least one feasible link between two nodes under predefined conditions. Reliability problems become more and more important as modern systems become more and more complex. This motivates the study of network reliability, a topic which has been extensively studied in the past few decades (Krivelevich et al., 2002).
Network connectivity is considered as a network reliability measure and there are various measures of connectivity. Two-terminal connectivity measures the ability of the network to satisfy the communication needs of a specific pair of nodes. Two-terminal reliability is defined as the probability that there exists at least one path in the network between a specific pair of nodes. All-terminal connectivity measures the ability of the network to satisfy the communication needs of all nodes in the network. All-terminal reliability is defined as the probability that for every pair of nodes in the network there exists at least one path between them.
The minimum overall two-terminal values can be interpreted as the reliability level guaranteed by the network to all users. The average overall two-terminal value provides a measure of the resilience of the network (Mendiratta, 2002).
In simulating large mobile networks, the high cost of storage requirements is a main problem. It may even be impossible to model such networks due to the huge extent of storage requirements. The key to modeling such networks to determine link reliability is to dynamically determine the connectivity graph. Therefore, the connectivity matrix must be computed over and over again. As the number of nodes in the network is increased, computational time required to determine the connectivity graph grows quadratically. Thus, for the simulation of large dynamic networks it is important to develop fast techniques to determine connectivity graph and link reliability with a reasonable degree of accuracy (Barrett et al., 2004; Peiravi and Kheibari, 2008).
The objective of this study is to present a fast technique to estimate the reliability of mobile networks considering both mobility and radio propagation models. We have presented an FS-TRG link reliability model which we used in our network reliability calculations. We used full and partial connectivity to provide a measure of network reliability (as done by Feng et al. (2002)), as a function of the distance between agents, quality of transmitters and receivers and model of reliability degradation.
REAL AND APPROXIMATE CONNECTIVITY GRAPHS
The most realistic model of connectivity of agents in an undirected network which (Barrett et al., 2004) label real connectivity is based on calculations using Euclidian distance between nodes and comparing the obtained results with radio distance dR. For two nodes ni(xi,yi) and nj(xj,yj), the Euclidian distance is as follows:
DE (ni ,nj
) = [( xi -xj )2 + ( yi
-yj )2]1/2 |
(1) |
In the remainder of the study we name this the real method and use it for comparison with our proposed algorithm.
Barrett et al. (2004) have investigated the performance of some approximate measures like Manhattan distance metric connectivity, k-means cluster connectivity and box connectivity for determining connectivity graphs. They have shown that the Manhattan distance is one of the best approximate measures for computing the connectivity graph of undirected networks. The Manhattan distance for two nodes ni and nj is simply the sum of component-wise distances:
dMij = |xi-xj|
+ |yi-yj| |
(2) |
We have used this metric and implemented a fast algorithm which reduces the computational time in static and dynamic networks.
Esteban Tlelo-Cuautle et al. (2004) have presented an interactive system for symbolic analysis in order to improve analog design automation of electronic circuits. There is a good analogy between analog circuit design and the problem under study in that there is a growing concern for the size of the network as more and more parts are added to the analog circuit as a result of which it becomes harder to compute the connectivity matrix. Guerra-Gómez et al. (2008) have presented a simulation-based optimization technique for the performance of Unity-Gain Cell based on Monte Carlo simulations in order to find the optimum size of the UGCs. Rubino (2005) used Monte Carlo simulations to analyze the computational sensitivity of network reliability. Mosaab and Qusay (2005, 2008) have estimated the reliability of mobile agent-based systems using Monte Carlo simulations. We have also used Monte Carlo simulations to carry out the research presented in this study. We used pseudo-random number generators to generate the various types of distribution of nodes in our domain of study. More details are reported in the sections on Monte Carlo simulations.
Peiravi and Kheibari (2008) showed that the time required to compute the connectivity matrix is reduced by 40% using Manhattan measure instead of Euclidian measure. This reduction of time can be appreciable when the number of nodes n is very large since the computational time is proportional to the square of n. Applying a modification factor to Manhattan measure would appreciably reduces rms error. We named this new method our modified Manhattan method in Peiravi and Kheibari (2008).
LINK AND NETWORK RELIABILITY
In network reliability analysis, a communication network with unreliable components can be modeled as an undirected network N (V, L) with node set V = {v1,...,vn} and link set L = {l1,...,lm} under the following assumptions (Konak et al., 2004):
| • | Nodes are perfectly reliable; however, links fail randomly |
| • | Each link li ∈ L, independently of other links, can be in either of two states, that is operative or failed, with respective probabilities pi and qi = 1-pi |
| • | No repair is allowed |
Let X = {x1,x2 ,..., xm} denote the state vector of N(V, L) such that xi = 1 if link li is in the operative state and xi = 0 if link li is in the failed state. Hence, the probability of observing a particular state X is given by:
(3) |
The main function of a wireless communication network is to provide connectivity service. Let U ⊆V be a set of some specified nodes of N(V, L) that is a subset of all the nodes in the network. Network reliability analysis is concerned with the probability that all nodes in U are connected to each other, directly or indirectly. With respect to connectivity, a network can be in either of two states: connected or not connected. Therefore, the structure function is defined as:
(4) |
In order to compute the network reliability, we must calculate the expected value of the structure function Φ (X), i.e.,
R = E [Φ(X)] = ∑x∈SΦ(X)Pr{X} |
(5) |
where, S is the state space of the all possible network states (Konak et al., 2004). If U = V, that is the network to be connected, then Eq. 5 refers to all-terminal reliability.
THE LINK RELIABILITY MODEL
Radio distance dR is defined as the connectivity range for every node and it compared with the calculated distance between a pair of nodes Ni and Nj, or their calculated range. If the calculated range between nodes is less than dR, the nodes are considered to be connected. Obviously the reliability of a fully connected link is 1, but in real ad hoc networks, radio range is not sharp and after a distance radio connection is deteriorated due to weather conditions, quality of transceivers, existence of highrise buildings or hills. Thus the reliability of a link is less than 1 and some how decreases as the distance between the two nodes increases. A model for link reliability is presented here to account for these effects.
We assume that for distances less than a fraction of region dimension (αD) there is no reliability degradation. For distances longer than dR, the link reliability is assumed to be zero since there is no connection. For distances between αD and dR the link reliability can be modeled using various methods based on the propagation model.
Free space propagation model: The free space model (FS) is the simplest propagation model. It only assumes that there is a direct path between transmitter t and receiver r. The path must be free of obstacles. The received power Pr depends on the transmitted power Pt, the gain of the receiver and transmitter antennas (Gt, Gr), the wavelength λ , the distance d between the node pair and a system loss coefficient L. Except the distance d between the nodes, the other factors are system-wide constant parameters. The received power Pr changes with the distance between the sender and the receiver (Gruber et al., 2004; Stepanov et al., 2005; Stepanov and Rothermel, 2008).
(6) |
Two ray ground propagation model: A single direct path between the communicating partners exists seldom at larger distances. The two ray ground propagation model (TRG) is an improved version of the free space model (FS). The TRG model not only assumes the direct path between transmitter t and receiver r, but also considers the ground reflection as shown in Fig. 1. Both nodes are assumed to be in line of sight (LOS).
(7) |
| Fig. 1: | Two ray ground propagation model showing its direct ray and the ground reflection |
where, ht and hr and denote antenna heights above ground which are considered to be constant during simulations.
FS-TRG propagation model: For a more realistic situation we can use a combination of the above two models. The free space model is used at small distances, while the TRG model is used at larger distances. Up to the crossover distance dTh = 4πhr ht/λ , the TRG model is equal to the FS model. Beyond this distance, the ground reflection destructively interferes with the direct ray and further reduces the field strength. The received signal strength is then inversely proportional to d4 as in Gruber et al. (2004) and Stepanov and Rothermel (2005, 2008).
(8) |
Given the relationship between received power and d, we can define link reliability as a function of distance. Based on FS-TRG propagation model, the reliability of links can be modeled as follow:
(9) |
where, 0 ≤ RL(d) ≤ 1, A, B, C and E are constants which depend on the quality of transmitter and receiver and D is the dimension of square region of simulation. This implies that the link reliability equals one for distances less than a fraction of typical radio range and for longer distances through crossover distance dth (βD), the reliability decreases based on the FS model; for distances equal to or larger than the βD through dR, the reliability decreases based on the TRG model and for distances larger than dR no connection exists and the reliability of connection equals zero.
The boundary conditions can be considered as follow:
| R (αD) | = | 1 |
| R (dR) | = | 0 |
| R (dth) | = | R (βD) = RTRG(dth) = RFS(dth) |
| R (dR) | = | RFS (dR) = RTRG(dR) = 0 |
Using boundary conditions, our FS-TRG based link reliability model can be introduced as:
RL = 1 for DE
(ni, nj) ≤ αD , 0<α1 =>
ni is connected to nj |
(10) |
RL(d) = (α2)(1-(dR2
/ DE2 (ni, nj)) / (α2
- 1) for αD ≤ DE (ni, nj)
≤ βD => ni is partially connected to nj |
(11) |
RL(d) = (α2
β2)(dR4 -1)/ DE4
(ni, nj)(1-α2)(1+ β2)
for βD ≤ DE (ni, nj) ≤
dR => ni is partially connected to nj |
(12) |
RL(d) = 0 for dR
≤ DE (ni, nj) => ni
and nj are disconnected |
(13) |
MONTE CARLO SIMULATION IN STATIC AND DYNAMIC CASES
Monte Carlo simulations were carried out in static and dynamic cases to estimate link reliability. In static case two spatial distributions were used for the nodes in the network-namely normal and uniform. However, in dynamic case only uniform distribution was simulated according to the mobility model used. The region occupied by the nodes is considered to be a square for uniform spatial distribution and a circle for normal spatial distribution. Normal and uniform distributions were used as representatives for uniformly and non-uniformly distributed networks. In each distribution, mean link reliability measure for the real and our proposed approximate methods was determined. The performance of the Manhattan and our modified Manhattan methods for determining connectivity graphs were experimented using Monte Carlo simulations and reported by Peiravi and Kheibari (2008). The mean reliability of network links is determined for different measures and different distribution of nodes. The acceptable performance of the Manhattan measure and our modified Manhattan measure for nodes which are distributed normally and uniformly is briefly reviewed. Monte Carlo simulations carried out in dynamic case using mobility models in networks distributed uniformly are presented.
Monte Carlo simulations in static case: In order to carry out the Monte Carlo simulations in static case two networks were constructed whose nodes had a spatially normal and uniform distribution, respectively. In each network, the reliability of network links for every dR was calculated. For calculations, we used three different methods: precise method using Euclidean distance, approximate method using Manhattan distance measure and Manhattan measure using modified connectivity range which we named modified Manhattan in Peiravi and Tolooei (2008).
We used a zero mean unity variance normal distribution in which more than 99% of nodes are located in a circle with a radius of 2.5. We calculated real and approximate measures for a range of dR from 0.01 to 1.4 (diagonal of unit square) for uniform and 5 for normal distribution with 0.01 increments. Circular and square regions are representatives for two different regions of nodes in two dimensional space. We used averaging of results of our Monte Carlo runs to minimize changes. For every dR, computations were repeated 10 times and averaged, yielding an rms error of less than 5%.
To determine the mean reliability of links in the static case, reliability of link connectivity was considered to be a combination of deterministic and stochastic factors. For distances equal to or less than αD, the reliability of connection was considered to be one. For longer distances, we considered a reliability model based on combination of FS and TRG propagation models up until dR and for distances longer than dR reliability is equal to zero.
For different α, β, different measures and different distribution of nodes the mean reliability of links of the network was determined. Figure 2 shows the variation of mean reliability of links versus dR using different methods for β = 0.5 and β = 0.05, 0.1 and uniform distribution of nodes. Obviously as α decreases the mean reliability of links decreases (a and b on the figures denote α and β).
Figure 3 shows the variation of mean reliability of links versus dR using different methods for β = 0.3 and α = 0.05, 0.1.
According to rms errors of two approximate methods, the performance of our modified Manhattan measure is very close to Euclidian measure and much better than Manhattan measure.
In Table 1, the results are summarized for different α, β and different distribution of nodes. The rms error of calculations using different methods are compared and the reduction of rms error using modified Manhattan method is introduced.
As shown in Table 1 by increasing α, the reliability increases for the same β. Using our modified Manhattan measure instead of traditional Manhattan, the rms error in calculations decreases between 49.5 to 140.88 times.
Monte Carlo simulations in dynamic case: Monte Carlo simulations were carried out to determine the link reliability in the dynamic case.
| Fig. 2: | Mean reliability of links using different measures for β = 0.5 and (a) α = 0.1 and (b) α = 0.05 and uniform spatial distribution of 200 nodes |
| Fig. 3: | Mean reliability of links using different measures for β = 0.3 and (a) α = 0.1 and (b) α = 0.05 and normal spatial distribution of nodes |
| Table 1: | Root mean square (rms) error for calculating mean reliability of links for different parameters and methods |
Node locations and their velocities were distributed uniformly. Simulation results for two different mobility models are introduced. Two different mobility models were used to simulate different dynamic conditions in the network in the dynamic case.
Mobility models: A number of different mobility models have been introduced in the literature. Here, we briefly discuss some of the mobility models such as random Direction, waypoint (Fitzek et al., 2003), attractor (Madsen et al., 2005), virtual world model (Konak et al., 2004) and mobility model with obstacles (Madsen et al., 2004; Yu and Li, 2003):
The Billiard model: The Billiard model is an especial case of a more general model called Random Direction (RD) model. In random direction model, nodes select a direction uniformly between 0 and 2πand a speed with which to move, based on a given distribution. Then motion starts. When nodes reach to the simulation boundary, they pause for a specified period of time, choose a new direction uniformly toward the inside of the simulation domain and the process continues. In the Billiard model a new direction is chosen such that the trajectory of movement forms equal angles with the boundary. When a node reaches the simulation area boundary, it is reflected back into the simulation area in the direction of either-θ, if it is on a vertical edge, or (π-θ), if it is on a horizontal edge. The velocity of the node is held constant. Madsen et al. (2005) refer to it as the Billiard model. This model was proposed to maintain a constant density of nodes throughout the simulation (Jardosh et al., 2003).
Random waypoint model: Another widely used model for protocol performance evaluation is the random waypoint model. A node chooses a random destination and a travelling speed and travels towards the destination along a straight line (Stepanov et al., 2008). When the node reaches its destination, it rests for some pause time. At the end of this pause time, it selects a new destination and speed and resumes movement. It is shown that, due to the characteristics of the model, the concentration of nodes follows a cyclic pattern during the lifetime of the network. The nodes tend to congregate in the center of the simulation area, resulting in a non-uniform network density (Jardosh et al., 2003).
Boundless simulation area mobility model: Boundless simulation area mobility model described by Jardosh et al. (2003) removes this limitation by allowing nodes to wrap around to the other side of the simulation area when they encounter a border. The effect of this change is to create a simulation area modeled as a torus, rather than a rectangular surface (Jardosh et al., 2003).
There are a variety of environments where the deployment of ad hoc networks is expected. Samples of these include cities, campuses, highways, conferences and battlefields. What most of these environments have in common is the presence of obstacles that block node movement and that hinder propagation of wireless signals. Examples of obstacles include buildings, foliage, mountains, hillsides, cars and people (Jardosh et al., 2003).
Attractor model: Madsen et al. (2004) introduced the Attractor model as a simple enhancement of any mobility model when regions of slow movements are incorporated in the simulation area. This leads to a non-homogeneous node distribution.
The virtual world model: This model is based on the mobility patterns obtained from the measurements of virtual world scenarios. The mobility measurements of a multi-player game, such as Quake II, can be used for investigation of the impact of mobility on the performance of multi-hop protocols (Madsen et al., 2005).
The mobility model with obstacles: The mobility model with obstacles incorporates rectangular shaped obstructions in the simulation region to make the simulation scenarios more realistic. It is more applicable when simulating indoor scenarios where the influence of walls and other objects cannot be ignored (Fitzek et al., 2003; Madsen et al., 2005, 2004).
Method used in Monte Carlo simulations in dynamic case: We examined the results using bounded random direction or the Billiard model (Madsen et al., 2005) and boundless simulation area mobility model for different dR and determined connectivity probability and link reliability using real and approximate methods.
In order to carry out the Monte Carlo simulations in dynamic case our
experiments were set up with nodes with specification (x, y, v, θ)
in which v is the velocity, Cv is coefficient of maximum velocity
and θ is the angle of movement. In every step, nodes move to a new
location based on their velocity and direction and their positions are
considered to be fixed during the calculations. Parameters v and θ
are determined based on uniform distribution. In order to generate θ,
the random number
Link reliability for boundless simulation area mobility model: Link reliability was calculated for mobile agents originally distributed uniformly in the unit square.
| Fig. 4: | Mean link reliability for uniform distribution and FS-TRG model (Cv = 0.03), for dR = 0.7, β = 0.5, (a) α = 0.05 and (b) α = 0.1 using different methods |
| Fig. 5: | Mean link reliability for uniform distribution and FS-TRG model (Cv = 0.03), for dR = 0.3, β = 0.5, (a) α = 0.05 and (b) α= 0.1 using different methods |
At t = 0 the agents start moving and their motion is not limited to boundaries of square region. Stochastic reliability model is FS-TRG based and mobility model is boundless simulation area mobility model. Maximum available link reliability depends on α, β and dR.
For α = 0.05, 0.1 and β = 0.3, 0.5 and dR = 0.3, 0.7 the link reliability for uniformly distributed network including 200 nodes was determined. The mean link reliability for α = 0.05, 0.1 and β = 0.5 and R = 0.7 was determined as shown in Fig. 4. FS-TRG model was used for simulation of 100 steps of motion.
Also the mean link reliability for α = 0.05, 0.1 and β = 0.5 and R = 0.3 was determined as shown in Fig. 5.
For constant dR and β, by increasing α the reliability increases for a given step. Using these plots, one can decide different conditions to provide desired reliability. The rms error of approximate methods and fractional reduction of rms error for different parameters are shown in Table 2.
Our modified Manhattan method improves the accuracy appreciably relative to traditional Manhattan method.
Link reliability for the random direction or the Billiard model: Link reliability for different α, β and radio range was determined using Billiard mobility model. The network nodes and their velocities had uniform distribution (Fig. 6).
As shown in Fig. 6, the link reliability is approximately constant during the movement because the distribution of nodes approximately remains uniform. As shown the radio range has the most effect on reliability of links. Also increasing α, increases the link reliability for a given β and radio range.
| Table 2: | Comparison of rms error for different methods |
| Table 3: | Comparison of rms error for different methods |
| Fig. 6: | Mean link reliability results for different α, β and radio range |
Modified Manhattan method improves the accuracy appreciably relative to traditional Manhattan method as shown in Table 3.
CONCLUSIONS
We used different measures to determine the link reliability to develop a fast algorithm to approximate the link reliability of static and dynamic networks. A stochastic reliability model based on propagation models was developed for reliability of links namely FS-TRG model and the effects of approximate methods were investigated. This model is more realistic than the deterministic case and based on accuracy of the model, one may obtain the desired accuracy. The link reliability can be used as a measure of reliability of the network. The minimum overall two-terminal values can be interpreted as the reliability level guaranteed by the network to all users. The average overall two-terminal value provides a measure of the resilience of the network. In static case the results for two random distributions of agents based on Monte Carlo simulation were obtained. As shown, increasing α and the radio range increases the reliability of link. In dynamic case, using boundless simulation area mobility model the reliability decreases with time. Using Billiard model, the link reliability is approximately constant during the movements and increasing α and the radio range increases the reliability of link. We have shown that using our modified Manhattan measure instead of traditional Manhattan, rms error will decrease appreciably while the speed of calculations is much faster than the Euclidian measure. The computational time for 100,000 nodes was 65.809 μsec using Euclidian measure, 14.292 μsec using Manhattan measure and 14.292 μsec using our modified Manhattan measure. This shows a fractional reduction of n = 4.6 in computational time which is notable. The research reported here has been simulated using Matlab and the timing of the simulations has been obtained using Turbo C++ programming on an Intel Pentium D 3.00 GHz PC.