# A Novel Two-Terminal Reliability Analysis for MANET

Authors: Xibin Zhao; Zhiyang You; Hai Wan
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Mobile ad hoc network (MANET) is a dynamic wireless communication network. Because of the dynamic and infrastructureless characteristics, MANET is vulnerable in reliability. This paper presents a novel reliability analysis for MANET. The node mobility effect and the node reliability based on a real MANET platform are modeled and analyzed. An effective Monte Carlo method for reliability analysis is proposed. A detailed evaluation is performed in terms of the experiment results.


---

## Body

## 1. Introduction

With the rapid proliferation of wireless lightweight devices, such as laptops, PDAs, and wireless telephones, the potential and importance of mobile computing have become prominent. Some applications of mobile networks will no longer depend on a fixed infrastructure. Mobile ad hoc network (MANET), which is composed of a set of mobile wireless devices, is particularly suitable in building temporary wireless applications in the environment without infrastructure, such as emergency rescue. MANET has become one of the most important research areas in wireless networks [1].There are some remarkable characteristics of MANET, such as infrastructure-less environment, multihop routing, dynamic topology, and constrained resource [1]. Without infrastructure, communication in MANET among these devices relies on the intermediate devices by multihop routing. Every device can move freely in MANET, so the topology of network is dynamic. Because of these characteristics, MANET is weak in the continuity of communication compared to traditional network. The infrastructure-less environment means that communication in MANET cannot rely on any fixed infrastructure which is natural in traditional wireless network. Every communication depends on the packets forwarding of intermediate devices by multihop routing, but resource-constrained devices are not always reliable, sometimes the device even being selfish [2]. Besides, the mobility of the device makes the duration of communication not long.The continuity of communication means the reliability of network, since the general definition of reliability is the ability of continuing to perform a specified operation despite the effects of malfunctioning and damage [3]. Reliability is very important for network, especially for MANET [4]. How to ensure the reliability of MANET attracts extensive attention [5, 6]. But the first step to ensure reliability of MANET is the ability to analyse reliability. The reliability analysis always refer to the terminal reliability, which means the ability that partial or all the devices remain connected, on the assumption that there is failure of link and node (the wireless device is always termed as node in MANET). Terminal reliability analysis is a quantitative analysis by mathematical modeling [7]. And the terminal reliability analysis is necessary for network, especially for MANET. Based on terminal reliability analysis, we can find the key factor of reliability in network, and then this information can be used to guide the protocol design. What is more, the result of terminal reliability analysis can also be the guideline to deploy MANET, especially for MANET with large scale.There are many researches proposed for terminal reliability analysis in traditional network and MANET. The terminal reliability is always composed of node reliability and link reliability [7]. In traditional network, the node and the link are supposed to be available only for a given percentage of time [7]. Based on the assumption, terminal reliability can be computed. And the complexity of terminal reliability computing is proved to be exponential [8]. So in traditional network, the main researches of terminal reliability are focused on how to reduce the computing complexity [8, 9]. But the terminal reliability computations in MANET should consider the failures of nodes and links in addition to the dynamic of network connectivity caused by nodes’ mobility [10]. So the traditional method cannot be used in MANET. The terminal reliability analysis in MANET is proposed [4]. Based on the nodes’ mobility model in MANET, researchers consider that the dynamic topology is composed of many configurations, and each configuration has its existence probability. The integral terminal reliability of the MANET depends on the terminal reliability and existence probability of each configuration.Most of the above researches suppose that the node and the link are prone to be failure and the failure of node and link is assumptive. It is not appropriate in MANET environment. In traditional network, the causes of failure of node and link are complicated and even uncertain. It is hard to find which is the most important. So in order to compute the node and link reliability simply, the failure of node and link is assumptive. But in MANET, the main reason of the node and link failure is obvious. Recent research considers the mobility to be the most important fact of link failure [4, 10], and the terminal reliability is computed based on the mobility model. But in typical article [4], the reliability of all nodes is set to the same value, regardless of the situation of the network such as node density. And in [4] the terminal reliability increases with the node density. In fact, the limited capacity of wireless network is proved, and the throughput of the wireless network furnished to each user diminishes to zero as the number of users increases [11]. The throughput will influence the transmission capacity of the wireless network, and it is obvious that it will affect the terminal reliability of MANET. Besides, the congestion of wireless network also needs to be taken into account in MANET. The congestion, which means that an excessive amount of packets arriving at a network bottleneck leads to many packet drops, is universal in traditional network, but it is more serious in MANET due to the node mobility and a shared wireless multihop channel [12]. Actually, the congestion is one of the reasons that the capacity is limited in MANET, and the congestion will affect the terminal reliability in MANET similarly. So it is unrealistic to set all nodes with the same reliability in MANET.In order to compute the terminal reliability in a more realistic way, this paper proposes the node reliability model on the basis of the analysis of the wireless device and experimental result in a real MANET platform. And with this model and related work, we provided a novel two-terminal reliability analysis for MANET. The remainder of this paper is organized as follows. Section2 introduces related work. Section 3 proposes the two-terminal reliability analysis for MANET. Section 4 is the calculation of the two-terminal reliability. Section 5 gives the conclusion.


## 2. Related Works

The research of reliability is prevalent in traditional network.  Most studies related to terminal reliability consider that each node in the network is a terminal. And the reliability analysis is always referring to the two-terminal, k-terminal, and all-terminal. Two-terminal is the basis of these terminal reliabilities, and two-terminal can be expanded to k-terminal and all-terminal [4, 13, 14]. Traditional definition of two-terminal reliability is the probability that there exists at least one path between two nodes [7]. Recent research considers that two-terminal reliability is the probability of a message to successfully reach the destination node from the source node [4]. In fact, these two definitions are the same; two nodes refer to the source node and destination node, and delivering a message needs at least one path.The two-terminal reliability research is followed by the development of the network.In traditional network, the researchers focus on how to compute the two-terminal reliability based on the node and link reliability and how to reduce the computational complexity of the two-terminal reliability. Fratta and Montanari proposed a method to compute the two-terminal reliability which is based on the Boolean algebra [7]. They considered that every link in the network is independent and is available on the average only for a given percentage of time. They also assumed that all nodes are completely reliable. Subsequently, based on the case analysis, the above researchers developed a recursive algorithm to compute the reliability by removing the assumption of completely reliable node [8]. Hansler also considers that the complete reliable node is unrealistic and provided a fast recursive algorithm to calculate the two-terminal reliability with unreliable link and unreliable node [9]. Similarly, Torrieri focused on the unreliable node in large network and presented a method which can be embedded in the Dotson algorithm to compute the two-terminal reliability [15]. And Netes and Filin also took the node reliability into account and provided an improved calculation based on the traditional method [16]. Kuo et al. proposed a time efficient calculation which is based on edge expansion diagrams [17]. Marseguerra et al. introduced the uncertainty into the calculation of reliability and this calculation is based on the genetic algorithms and Monte Carlo simulation [18].As in wireless network, the researches are less than in traditional network. AbElFotoh and Colbourn proposed a calculation of two-terminal reliability for radio-broadcast networks [19]. They only considered that the node can fail, but proved that the failure of link can be expended to this calculation. Chen and Lyu provided reliability analysis which is based on the Markov model in wireless CORBA [20].Recently, as the MANET is considered to be more useful in real environment and it is weak in reliability, the reliability analysis of MANET becomes one of the hotspots in reliability research. Kharbash and Wang indicated that reliability computations in MANET should consider the failure of nodes and links in addition to the dynamic of network connectivity caused by nodes’ mobility [10]. Then the calculation of two-terminal reliability is presented. But they do not model the mobility into reliability analysis, but only considered influence of mobility by network simulation tool. Cook and Ramirez-Marquez included the mobility model of MANET into reliability analysis [4]; these researchers consider that the dynamic topology is composed of many configurations, and each configuration has its existence probability. The integral two-terminal reliability of the MANET depends on the terminal reliability and existence probability of each configuration. Furthermore, these researchers extended the calculation to capacitated MANET [13] and cluster-based MANET [14]. But, as said before, it is unrealistic to set all nodes with the same probability to fail in MANET.


## 3. Reliability Analysis for MANET

### 3.1. Definition

In this paper, we utilize the current definitions of two-terminal reliability: two-terminal reliability is the probability of a message successfully reaching the destination node from the source node.Every symbol used in this paper is defined in Table1.Table 1
Definition of symbols.
N
Set of nodes
n
|
N
|, number of N
i
Index of nodei, i=1,…,n
r
i
Reliability of nodei
G
(
N
)
NetworkG(N)
C
Set of possible configurations of networkG(N)
l
i
j
Virtual link between nodesi and j
L
Link configuration matrix
η
l
Number of linked node pairs
η
u
Number of unlinked node pairs
α
k
One of the configurations inG(N), k=1,…,|C|
P
(
α
k
=
1
)
The existence probability ofαk
λ
Constant probability of link existence
g
Average neighbor nodes
g
i
Neighbor nodes of nodei
2
T
R
α
k
Two-terminal reliability of configurationαk
2
TR
Two-terminal reliability of MANET


### 3.2. Assumptions

In order to focus on the key factors and simplify the analysis, we list the assumptions as follows.(1)
The source node and destination node which we refer to are known and constant.(2)
Every node is of the same type and with the same situation.(3)
Every node has the same wireless transmission range and every node pair within the wireless transmission range is considered to be connected.(4)
Every node keeps the same data transmission with each of its neighbors.(5)
The mobility of node is the random waypoint mobility model.(6)
The capacity of every link is binary, which means the link either exists or does not exist.


### 3.3. Reliability Analysis

The MANET is abstracted intoG(N), with the set of nodes N. The number of nodes is n, and each node has an index. Each node has its reliability which is represented by ri,i=1,…,n.lij is the virtual binary link between node i and node j. 0 represents the link between nodes i and j exists; otherwise 1 represents this link does not exist. And L is the matrix of lij.Here, the problem of the two-terminal reliability analysis is how to model the link and node reliability correctly and how to conduct the two-terminal reliability computation based on the link and node reliability.


#### 3.3.1. Link Reliability

The main purpose of the paper focuses on the node reliability in the resource-constrained and dynamic MANET environment. So we utilize the reasonable link reliability analysis from [4], which first included the mobility into the reliability analysis. Then we introduce this link reliability analysis briefly.The mobility of MANET is the random waypoint mobility model, which is a general mobility model for MANET [21]. The authors of [4] considered that once n is fixed, the states of the network can be enumerated. And they call these states configurations which are represented by αk,k=1,…,|C|, where the C is defined as the set of all possible configurations. With the random waypoint mobility model, let g be the average number of neighbors per node. And the probability of link existence is λ=g/(n-1). Then the existence probability of each configuration is given by the formula P(αk=1)=ληl(1-λ)ηu, where the ηl and ηu are numbers of linked and unlinked node pairs respectively. And the two-terminal reliability of configuration αk can be formalized as 2TRαk=P(αk=1)∏pathri, where ri is the reliability of node i and path is the shortest route between the source and destination nodes in the configuration.The link reliability can be computed from above formula for each configuration, and then we start modeling the reliability of node.


#### 3.3.2. Node Reliability

Traditional reliability researches assumed that all the nodes are completely reliable or failure at the same probability. It is reasonable in the traditional network, because the causes of node failure are complex, such as power off, equipment failure, and malicious attack. Even these factors are uncertain sometimes. So it is hard to distinguish the influence of these factors. Aiming at simplifying the modeling, the node reliability is assumptive. But these assumptions are no longer suitable for MANET environment. According to the mobility model, the node can move freely in the area. Sometimes, as the node acts as both receiver and router, some nodes may forward more packets than others, because of their positions.In a network, data transmission between nodes is inevitable. But when every neighbor node keeps communication with the nodes with the more neighbors at the same time, there will be excessive amount of packets arriving at these nodes. Once the data reception ability of the nodes cannot afford the number and rate of packets, congestion will occur and the packet loss rate of the nodes will increase. Then it will result in the unreliability of node. Obviously, the congestion is related to the density of the node in some area, and it will influence the terminal reliability by reducing the node reliability. According to the result of [4], when λ and ri are fixed, the value of terminal reliability will increase with the node number in the network. Since the λ is g/(n-1), the average neighbor nodes g, which have the same mean with the density of the node, will also increase with the node number. Therefore, it is unrealistic to assign the same value to reliability to all nodes in MANET.According to the above analysis, we consider the number of neighbor nodes of each node is the most important factor which influences the node reliability in MANET. For each node, more neighbor nodes, which result in the unreliability of node, mean more link connections between the nodes and their neighbors. So in this paper, when modeling the node reliability, we will focus on deducing the relationship between the number of link connections and the node reliability. But so far there are not any researches concentrating on this relationship, then the theoretical calculation model of node reliability related to the number of link connections is vacant in MANET. References [11, 12] considered that the throughput of each user diminishes to zero or the congestion will occur when the number of the nodes increases. But they did not study the relationship between them. It is important for node reliability modeling in this paper, which the traditional researches did not refer to. In fact, based on our experimental experience, the node reliability will not be greatly influenced, when the number of nodes is small. Because every wireless device has its capacity, if the processed data do not exceed the capacity, there will not be too much effect. The effect will be very tiny. But when there are enough nodes communicating at the same area, the node reliability will decrease to zero quickly, because of the congestion. However, it still lacks quantitative analysis. Therefore, we propose some general experiments in a real MANET platform and hope that the above qualitative analysis will be proved and the relationship will be modeled on the basis of experimental results.The experiments are carried out on iNet, which is a real experimental and applied platform for MANET. iNet is developed by key laboratory for information system security of Ministry of Education of China, and this project is funded by the National 863 Plan (Project no. 2007AA040701-1), China, and The State Key Development Program for Basic Research of China (Grant no. 2010CB328000). Based on iNet, we aim to study the urgent security problem of MANET and to advance the application of MANET in campus. The implementation of iNet is mainly based on the NDIS (Network Driver Interface Specification) which is provided by Microsoft, and the wireless standard is WiFi. The operation system which iNet supported includes Windows XP, Windows 2003, Windows Mobile 5.0, and Windows Mobile 6.0. So the node in iNet can be many types of wireless devices which have Windows operation system and WiFi, such as desktop, notebooks, PDA, and smartphone. According to assumption 2, we all use the same type of wireless device in the experiments.The wireless device used in this experiment is Dopod CHT9000, which is a powerful smartphone with 400 MHz CPU, 64 MB RAM, and 128 MB ROM, supporting 802.11 b/g, running Windows Mobile 6.0. As said before, the purpose of the experiment is concluding the relationship between the number of link connections and the node reliability, so a general experimental schematic is designed as in Figure1.Figure 1
Experimental schematic of node reliability.Figure1 shows that every neighbor node communicates with the destination node which is set in the center of the figure and every neighbor node within the wireless transmission range of the destination nodes. The experiment is evaluating the node reliability of the destination node, when the number of the communicated neighbor node increases.Then the steps of the experiment are given in detail as follows.Step 1.
Initialize the location of the destination node and the neighbor nodes.
This step is trying to confirm that the distance between destination node and neighbor node is less than the wireless transmission range, and the route between the destination node and neighbor node is only one hop. In MANET, within the wireless transmission range does not mean that you can communicate with the destination directly, because of routing protocol which is on the purpose of the efficiency. In order to ignore the influence of the multihop routing, we modify the routing module of iNet and ensure the communication is within one hop.Step 2.
Deploy the communication process in the neighbor nodes, and launch the experiment by sending the data packets from neighbor nodes to the destination node at a fixed sending rate for a period of time.
In this step, we use the test module of the iNet. The main function of the test module is to launch the communication between nodes and record the key data of the communication. Many parameters can be set in the test module, such as the IP of the destination node, the size of packet, the packet sending rate, the time of packet sending, and the TTL of the packet. In this experiment, aiming to simplify the modeling, we assume that every node keeps the same data transmission with each of its neighbors. So the packet send rate is fixed to two packets per second, the packet size is set to 512 bytes, and the packet sending keeps on for 20 minutes.Step 3.
Analyze the record of data packets at the destination node and neighbor nodes, and compute the packet loss rate at the destination node.
As mentioned in Step2, the test module can record the key data of the communication, such as the number of sending packets, the number of receiving packets, and the ID of every packet. With this record, we can get some key factors of the network, such as packet loss rate, packet delay, and throughput. As mentioned before, the experiment aims to evaluate the node reliability, since the definite two-terminal reliability is the probability of a message to successfully reach the destination node from the source node, so the same to the node reliability means the probability to be active. In the view of the terminal reliability in MANET, an active node means it can receive and forward the packets, and the loss packets presume that the node is not active at that time; therefore we consider that the packet loss rate is related to the node reliability in this paper, and the node reliability equals to 1 less packet loss rate. In the experiment, the average packet loss rate is computed by the packets record for the fixed time.Step 4.
Add a node to the experimental environment, and redo Steps1, 2, and 3.
This step changes the experimental condition by increasing the number of the neighbor nodes, and the next step is the same as Steps1, 2, and 3.Then the result of the experiment is shown in Figure2.Packet loss rate (a) and node reliability (b) of the experiment.
(a)
(b)From Figure2(a), we find that packet loss rate of the destination is not affected until where are seven neighbor nodes, and when the number of neighbor nodes reaches eight, the packet loss rate increases to 100% quickly. This also proves the above qualitative analysis.Based on the results of the packet loss rate, we can get the result of the node reliability, which is shown in Figure2(b).As in Figure2(b), we consider that the variety of the node reliability is similar to the style of hyperbolic tangent function, so we use an amended hyperbolic tangent function to fit the result of the node reliability. The fitting function is assumed as f(x)=(1-tanha(x-b))×c, where f(x) is denoted as the node reliability, x is the number of the neighbor nodes, and a,b,andc are the coefficients. The curve fitting of node reliability is shown in Figure 3.Figure 3
Curve fitting of the node reliability.The result of the curve fitting is shown in Algorithm1.Algorithm 1
Coefficients (with 95% confidence bounds):
a=0.896
b=9.953
c=0.4936
Goodness of fit:
SSE: 0.004319
R-square: 0.999
Adjusted R-square: 0.9989
RMSE: 0.01594From Algorithm1, we prove that the assumption of the fitting function is correct.Since the experiment is carried out in a real MANET platform and the experimental scheme is general, we consider that the node reliability is according to the form which we assumed above. Besides, the variety of node reliability is related to the coefficients of the assumption, because of the different wireless device, different packet size, different packet sending rate, and so on. As the above qualitative analysis, different wireless device means different capacity, which decides the beginning point of the decrease. The different packet size and packet sending rate influence the congestion, which results in both the beginning point of the decreasing and the rate of the decreasing. So the model of node reliability is formalized asri=(1-tanhα(gi-β))×γ, where ri is the node reliability of the node i, gi is the number of the neighbor nodes, and α,β, and γ are the coefficients which are related to the type of wireless device, packet size, and packet sending rate.


#### 3.3.3. Reliability Calculation

Based on the link reliability and node reliability from the above analysis, two-terminal reliability of MANET can be conducted as follows:(1)2TR=∑k=1|C|2TRαk=∑k=1|C|P(αk=1)∏pathri=∑k=1|C|P(αk=1)∏path(1-tanhα(gi-β))×γ.This function shows that the topology of dynamic MANET can be divided into|C| configurations, and each configuration has its existence probability P(αk=1). In each configuration we search for the shortest path from source node to the destination node, and then node reliability of this path is represented by the multiplying of reliability of each node in the path. Of course, if there is no path from the source to the destination node, the reliability of this configuration is zero.Then we compute the 2TR by the above function. It is obvious that the most direct method is enumeration. The result is shown in Table2. The parameters are set as the first line of Table 2. Parameters are chosen randomly. From Table 2, we can find that 2TR increases with the number of the nodes, because the node reliability will not be influenced when the number of neighbor nodes is small.Table 2
Enumeration result of 2TR.
λ
=
0.5
,
α
=
1.0
,
β
=
10.0
,
γ
=
0.5
Nodes
Links
Configuration
2TR
Run time (s)
3
3
8
0.625
0.032
4
6
64
0.75
0.5
5
10
1024
0.8535
8.219
6
15
32768
0.9236
494.282
7
21
2097152
0.963
45635.8The computation of 2TR must be suitable for the MANET with large scale. Through theoretical modeling to analyze the reliability of MANET with only a few nodes is meaningless.  Since|C| is 2n(n-1)/2, the enumeration method iterates at least |C| times, which increases with the n exponentially. As in Table 2, it is obvious that the run time increases quickly with the configuration of the network: more than 12 hours is needed for the computation of 2TR when the number of the nodes is 7. So in order to analyze 2TR with large scale, it is necessary to introduce an efficient calculation method to compute the 2TR.


## 3.1. Definition

In this paper, we utilize the current definitions of two-terminal reliability: two-terminal reliability is the probability of a message successfully reaching the destination node from the source node.Every symbol used in this paper is defined in Table1.Table 1
Definition of symbols.
N
Set of nodes
n
|
N
|, number of N
i
Index of nodei, i=1,…,n
r
i
Reliability of nodei
G
(
N
)
NetworkG(N)
C
Set of possible configurations of networkG(N)
l
i
j
Virtual link between nodesi and j
L
Link configuration matrix
η
l
Number of linked node pairs
η
u
Number of unlinked node pairs
α
k
One of the configurations inG(N), k=1,…,|C|
P
(
α
k
=
1
)
The existence probability ofαk
λ
Constant probability of link existence
g
Average neighbor nodes
g
i
Neighbor nodes of nodei
2
T
R
α
k
Two-terminal reliability of configurationαk
2
TR
Two-terminal reliability of MANET


## 3.2. Assumptions

In order to focus on the key factors and simplify the analysis, we list the assumptions as follows.(1)
The source node and destination node which we refer to are known and constant.(2)
Every node is of the same type and with the same situation.(3)
Every node has the same wireless transmission range and every node pair within the wireless transmission range is considered to be connected.(4)
Every node keeps the same data transmission with each of its neighbors.(5)
The mobility of node is the random waypoint mobility model.(6)
The capacity of every link is binary, which means the link either exists or does not exist.


## 3.3. Reliability Analysis

The MANET is abstracted intoG(N), with the set of nodes N. The number of nodes is n, and each node has an index. Each node has its reliability which is represented by ri,i=1,…,n.lij is the virtual binary link between node i and node j. 0 represents the link between nodes i and j exists; otherwise 1 represents this link does not exist. And L is the matrix of lij.Here, the problem of the two-terminal reliability analysis is how to model the link and node reliability correctly and how to conduct the two-terminal reliability computation based on the link and node reliability.


### 3.3.1. Link Reliability

The main purpose of the paper focuses on the node reliability in the resource-constrained and dynamic MANET environment. So we utilize the reasonable link reliability analysis from [4], which first included the mobility into the reliability analysis. Then we introduce this link reliability analysis briefly.The mobility of MANET is the random waypoint mobility model, which is a general mobility model for MANET [21]. The authors of [4] considered that once n is fixed, the states of the network can be enumerated. And they call these states configurations which are represented by αk,k=1,…,|C|, where the C is defined as the set of all possible configurations. With the random waypoint mobility model, let g be the average number of neighbors per node. And the probability of link existence is λ=g/(n-1). Then the existence probability of each configuration is given by the formula P(αk=1)=ληl(1-λ)ηu, where the ηl and ηu are numbers of linked and unlinked node pairs respectively. And the two-terminal reliability of configuration αk can be formalized as 2TRαk=P(αk=1)∏pathri, where ri is the reliability of node i and path is the shortest route between the source and destination nodes in the configuration.The link reliability can be computed from above formula for each configuration, and then we start modeling the reliability of node.


### 3.3.2. Node Reliability

Traditional reliability researches assumed that all the nodes are completely reliable or failure at the same probability. It is reasonable in the traditional network, because the causes of node failure are complex, such as power off, equipment failure, and malicious attack. Even these factors are uncertain sometimes. So it is hard to distinguish the influence of these factors. Aiming at simplifying the modeling, the node reliability is assumptive. But these assumptions are no longer suitable for MANET environment. According to the mobility model, the node can move freely in the area. Sometimes, as the node acts as both receiver and router, some nodes may forward more packets than others, because of their positions.In a network, data transmission between nodes is inevitable. But when every neighbor node keeps communication with the nodes with the more neighbors at the same time, there will be excessive amount of packets arriving at these nodes. Once the data reception ability of the nodes cannot afford the number and rate of packets, congestion will occur and the packet loss rate of the nodes will increase. Then it will result in the unreliability of node. Obviously, the congestion is related to the density of the node in some area, and it will influence the terminal reliability by reducing the node reliability. According to the result of [4], when λ and ri are fixed, the value of terminal reliability will increase with the node number in the network. Since the λ is g/(n-1), the average neighbor nodes g, which have the same mean with the density of the node, will also increase with the node number. Therefore, it is unrealistic to assign the same value to reliability to all nodes in MANET.According to the above analysis, we consider the number of neighbor nodes of each node is the most important factor which influences the node reliability in MANET. For each node, more neighbor nodes, which result in the unreliability of node, mean more link connections between the nodes and their neighbors. So in this paper, when modeling the node reliability, we will focus on deducing the relationship between the number of link connections and the node reliability. But so far there are not any researches concentrating on this relationship, then the theoretical calculation model of node reliability related to the number of link connections is vacant in MANET. References [11, 12] considered that the throughput of each user diminishes to zero or the congestion will occur when the number of the nodes increases. But they did not study the relationship between them. It is important for node reliability modeling in this paper, which the traditional researches did not refer to. In fact, based on our experimental experience, the node reliability will not be greatly influenced, when the number of nodes is small. Because every wireless device has its capacity, if the processed data do not exceed the capacity, there will not be too much effect. The effect will be very tiny. But when there are enough nodes communicating at the same area, the node reliability will decrease to zero quickly, because of the congestion. However, it still lacks quantitative analysis. Therefore, we propose some general experiments in a real MANET platform and hope that the above qualitative analysis will be proved and the relationship will be modeled on the basis of experimental results.The experiments are carried out on iNet, which is a real experimental and applied platform for MANET. iNet is developed by key laboratory for information system security of Ministry of Education of China, and this project is funded by the National 863 Plan (Project no. 2007AA040701-1), China, and The State Key Development Program for Basic Research of China (Grant no. 2010CB328000). Based on iNet, we aim to study the urgent security problem of MANET and to advance the application of MANET in campus. The implementation of iNet is mainly based on the NDIS (Network Driver Interface Specification) which is provided by Microsoft, and the wireless standard is WiFi. The operation system which iNet supported includes Windows XP, Windows 2003, Windows Mobile 5.0, and Windows Mobile 6.0. So the node in iNet can be many types of wireless devices which have Windows operation system and WiFi, such as desktop, notebooks, PDA, and smartphone. According to assumption 2, we all use the same type of wireless device in the experiments.The wireless device used in this experiment is Dopod CHT9000, which is a powerful smartphone with 400 MHz CPU, 64 MB RAM, and 128 MB ROM, supporting 802.11 b/g, running Windows Mobile 6.0. As said before, the purpose of the experiment is concluding the relationship between the number of link connections and the node reliability, so a general experimental schematic is designed as in Figure1.Figure 1
Experimental schematic of node reliability.Figure1 shows that every neighbor node communicates with the destination node which is set in the center of the figure and every neighbor node within the wireless transmission range of the destination nodes. The experiment is evaluating the node reliability of the destination node, when the number of the communicated neighbor node increases.Then the steps of the experiment are given in detail as follows.Step 1.
Initialize the location of the destination node and the neighbor nodes.
This step is trying to confirm that the distance between destination node and neighbor node is less than the wireless transmission range, and the route between the destination node and neighbor node is only one hop. In MANET, within the wireless transmission range does not mean that you can communicate with the destination directly, because of routing protocol which is on the purpose of the efficiency. In order to ignore the influence of the multihop routing, we modify the routing module of iNet and ensure the communication is within one hop.Step 2.
Deploy the communication process in the neighbor nodes, and launch the experiment by sending the data packets from neighbor nodes to the destination node at a fixed sending rate for a period of time.
In this step, we use the test module of the iNet. The main function of the test module is to launch the communication between nodes and record the key data of the communication. Many parameters can be set in the test module, such as the IP of the destination node, the size of packet, the packet sending rate, the time of packet sending, and the TTL of the packet. In this experiment, aiming to simplify the modeling, we assume that every node keeps the same data transmission with each of its neighbors. So the packet send rate is fixed to two packets per second, the packet size is set to 512 bytes, and the packet sending keeps on for 20 minutes.Step 3.
Analyze the record of data packets at the destination node and neighbor nodes, and compute the packet loss rate at the destination node.
As mentioned in Step2, the test module can record the key data of the communication, such as the number of sending packets, the number of receiving packets, and the ID of every packet. With this record, we can get some key factors of the network, such as packet loss rate, packet delay, and throughput. As mentioned before, the experiment aims to evaluate the node reliability, since the definite two-terminal reliability is the probability of a message to successfully reach the destination node from the source node, so the same to the node reliability means the probability to be active. In the view of the terminal reliability in MANET, an active node means it can receive and forward the packets, and the loss packets presume that the node is not active at that time; therefore we consider that the packet loss rate is related to the node reliability in this paper, and the node reliability equals to 1 less packet loss rate. In the experiment, the average packet loss rate is computed by the packets record for the fixed time.Step 4.
Add a node to the experimental environment, and redo Steps1, 2, and 3.
This step changes the experimental condition by increasing the number of the neighbor nodes, and the next step is the same as Steps1, 2, and 3.Then the result of the experiment is shown in Figure2.Packet loss rate (a) and node reliability (b) of the experiment.
(a)
(b)From Figure2(a), we find that packet loss rate of the destination is not affected until where are seven neighbor nodes, and when the number of neighbor nodes reaches eight, the packet loss rate increases to 100% quickly. This also proves the above qualitative analysis.Based on the results of the packet loss rate, we can get the result of the node reliability, which is shown in Figure2(b).As in Figure2(b), we consider that the variety of the node reliability is similar to the style of hyperbolic tangent function, so we use an amended hyperbolic tangent function to fit the result of the node reliability. The fitting function is assumed as f(x)=(1-tanha(x-b))×c, where f(x) is denoted as the node reliability, x is the number of the neighbor nodes, and a,b,andc are the coefficients. The curve fitting of node reliability is shown in Figure 3.Figure 3
Curve fitting of the node reliability.The result of the curve fitting is shown in Algorithm1.Algorithm 1
Coefficients (with 95% confidence bounds):
a=0.896
b=9.953
c=0.4936
Goodness of fit:
SSE: 0.004319
R-square: 0.999
Adjusted R-square: 0.9989
RMSE: 0.01594From Algorithm1, we prove that the assumption of the fitting function is correct.Since the experiment is carried out in a real MANET platform and the experimental scheme is general, we consider that the node reliability is according to the form which we assumed above. Besides, the variety of node reliability is related to the coefficients of the assumption, because of the different wireless device, different packet size, different packet sending rate, and so on. As the above qualitative analysis, different wireless device means different capacity, which decides the beginning point of the decrease. The different packet size and packet sending rate influence the congestion, which results in both the beginning point of the decreasing and the rate of the decreasing. So the model of node reliability is formalized asri=(1-tanhα(gi-β))×γ, where ri is the node reliability of the node i, gi is the number of the neighbor nodes, and α,β, and γ are the coefficients which are related to the type of wireless device, packet size, and packet sending rate.


### 3.3.3. Reliability Calculation

Based on the link reliability and node reliability from the above analysis, two-terminal reliability of MANET can be conducted as follows:(1)2TR=∑k=1|C|2TRαk=∑k=1|C|P(αk=1)∏pathri=∑k=1|C|P(αk=1)∏path(1-tanhα(gi-β))×γ.This function shows that the topology of dynamic MANET can be divided into|C| configurations, and each configuration has its existence probability P(αk=1). In each configuration we search for the shortest path from source node to the destination node, and then node reliability of this path is represented by the multiplying of reliability of each node in the path. Of course, if there is no path from the source to the destination node, the reliability of this configuration is zero.Then we compute the 2TR by the above function. It is obvious that the most direct method is enumeration. The result is shown in Table2. The parameters are set as the first line of Table 2. Parameters are chosen randomly. From Table 2, we can find that 2TR increases with the number of the nodes, because the node reliability will not be influenced when the number of neighbor nodes is small.Table 2
Enumeration result of 2TR.
λ
=
0.5
,
α
=
1.0
,
β
=
10.0
,
γ
=
0.5
Nodes
Links
Configuration
2TR
Run time (s)
3
3
8
0.625
0.032
4
6
64
0.75
0.5
5
10
1024
0.8535
8.219
6
15
32768
0.9236
494.282
7
21
2097152
0.963
45635.8The computation of 2TR must be suitable for the MANET with large scale. Through theoretical modeling to analyze the reliability of MANET with only a few nodes is meaningless.  Since|C| is 2n(n-1)/2, the enumeration method iterates at least |C| times, which increases with the n exponentially. As in Table 2, it is obvious that the run time increases quickly with the configuration of the network: more than 12 hours is needed for the computation of 2TR when the number of the nodes is 7. So in order to analyze 2TR with large scale, it is necessary to introduce an efficient calculation method to compute the 2TR.


## 3.3.1. Link Reliability

The main purpose of the paper focuses on the node reliability in the resource-constrained and dynamic MANET environment. So we utilize the reasonable link reliability analysis from [4], which first included the mobility into the reliability analysis. Then we introduce this link reliability analysis briefly.The mobility of MANET is the random waypoint mobility model, which is a general mobility model for MANET [21]. The authors of [4] considered that once n is fixed, the states of the network can be enumerated. And they call these states configurations which are represented by αk,k=1,…,|C|, where the C is defined as the set of all possible configurations. With the random waypoint mobility model, let g be the average number of neighbors per node. And the probability of link existence is λ=g/(n-1). Then the existence probability of each configuration is given by the formula P(αk=1)=ληl(1-λ)ηu, where the ηl and ηu are numbers of linked and unlinked node pairs respectively. And the two-terminal reliability of configuration αk can be formalized as 2TRαk=P(αk=1)∏pathri, where ri is the reliability of node i and path is the shortest route between the source and destination nodes in the configuration.The link reliability can be computed from above formula for each configuration, and then we start modeling the reliability of node.


## 3.3.2. Node Reliability

Traditional reliability researches assumed that all the nodes are completely reliable or failure at the same probability. It is reasonable in the traditional network, because the causes of node failure are complex, such as power off, equipment failure, and malicious attack. Even these factors are uncertain sometimes. So it is hard to distinguish the influence of these factors. Aiming at simplifying the modeling, the node reliability is assumptive. But these assumptions are no longer suitable for MANET environment. According to the mobility model, the node can move freely in the area. Sometimes, as the node acts as both receiver and router, some nodes may forward more packets than others, because of their positions.In a network, data transmission between nodes is inevitable. But when every neighbor node keeps communication with the nodes with the more neighbors at the same time, there will be excessive amount of packets arriving at these nodes. Once the data reception ability of the nodes cannot afford the number and rate of packets, congestion will occur and the packet loss rate of the nodes will increase. Then it will result in the unreliability of node. Obviously, the congestion is related to the density of the node in some area, and it will influence the terminal reliability by reducing the node reliability. According to the result of [4], when λ and ri are fixed, the value of terminal reliability will increase with the node number in the network. Since the λ is g/(n-1), the average neighbor nodes g, which have the same mean with the density of the node, will also increase with the node number. Therefore, it is unrealistic to assign the same value to reliability to all nodes in MANET.According to the above analysis, we consider the number of neighbor nodes of each node is the most important factor which influences the node reliability in MANET. For each node, more neighbor nodes, which result in the unreliability of node, mean more link connections between the nodes and their neighbors. So in this paper, when modeling the node reliability, we will focus on deducing the relationship between the number of link connections and the node reliability. But so far there are not any researches concentrating on this relationship, then the theoretical calculation model of node reliability related to the number of link connections is vacant in MANET. References [11, 12] considered that the throughput of each user diminishes to zero or the congestion will occur when the number of the nodes increases. But they did not study the relationship between them. It is important for node reliability modeling in this paper, which the traditional researches did not refer to. In fact, based on our experimental experience, the node reliability will not be greatly influenced, when the number of nodes is small. Because every wireless device has its capacity, if the processed data do not exceed the capacity, there will not be too much effect. The effect will be very tiny. But when there are enough nodes communicating at the same area, the node reliability will decrease to zero quickly, because of the congestion. However, it still lacks quantitative analysis. Therefore, we propose some general experiments in a real MANET platform and hope that the above qualitative analysis will be proved and the relationship will be modeled on the basis of experimental results.The experiments are carried out on iNet, which is a real experimental and applied platform for MANET. iNet is developed by key laboratory for information system security of Ministry of Education of China, and this project is funded by the National 863 Plan (Project no. 2007AA040701-1), China, and The State Key Development Program for Basic Research of China (Grant no. 2010CB328000). Based on iNet, we aim to study the urgent security problem of MANET and to advance the application of MANET in campus. The implementation of iNet is mainly based on the NDIS (Network Driver Interface Specification) which is provided by Microsoft, and the wireless standard is WiFi. The operation system which iNet supported includes Windows XP, Windows 2003, Windows Mobile 5.0, and Windows Mobile 6.0. So the node in iNet can be many types of wireless devices which have Windows operation system and WiFi, such as desktop, notebooks, PDA, and smartphone. According to assumption 2, we all use the same type of wireless device in the experiments.The wireless device used in this experiment is Dopod CHT9000, which is a powerful smartphone with 400 MHz CPU, 64 MB RAM, and 128 MB ROM, supporting 802.11 b/g, running Windows Mobile 6.0. As said before, the purpose of the experiment is concluding the relationship between the number of link connections and the node reliability, so a general experimental schematic is designed as in Figure1.Figure 1
Experimental schematic of node reliability.Figure1 shows that every neighbor node communicates with the destination node which is set in the center of the figure and every neighbor node within the wireless transmission range of the destination nodes. The experiment is evaluating the node reliability of the destination node, when the number of the communicated neighbor node increases.Then the steps of the experiment are given in detail as follows.Step 1.
Initialize the location of the destination node and the neighbor nodes.
This step is trying to confirm that the distance between destination node and neighbor node is less than the wireless transmission range, and the route between the destination node and neighbor node is only one hop. In MANET, within the wireless transmission range does not mean that you can communicate with the destination directly, because of routing protocol which is on the purpose of the efficiency. In order to ignore the influence of the multihop routing, we modify the routing module of iNet and ensure the communication is within one hop.Step 2.
Deploy the communication process in the neighbor nodes, and launch the experiment by sending the data packets from neighbor nodes to the destination node at a fixed sending rate for a period of time.
In this step, we use the test module of the iNet. The main function of the test module is to launch the communication between nodes and record the key data of the communication. Many parameters can be set in the test module, such as the IP of the destination node, the size of packet, the packet sending rate, the time of packet sending, and the TTL of the packet. In this experiment, aiming to simplify the modeling, we assume that every node keeps the same data transmission with each of its neighbors. So the packet send rate is fixed to two packets per second, the packet size is set to 512 bytes, and the packet sending keeps on for 20 minutes.Step 3.
Analyze the record of data packets at the destination node and neighbor nodes, and compute the packet loss rate at the destination node.
As mentioned in Step2, the test module can record the key data of the communication, such as the number of sending packets, the number of receiving packets, and the ID of every packet. With this record, we can get some key factors of the network, such as packet loss rate, packet delay, and throughput. As mentioned before, the experiment aims to evaluate the node reliability, since the definite two-terminal reliability is the probability of a message to successfully reach the destination node from the source node, so the same to the node reliability means the probability to be active. In the view of the terminal reliability in MANET, an active node means it can receive and forward the packets, and the loss packets presume that the node is not active at that time; therefore we consider that the packet loss rate is related to the node reliability in this paper, and the node reliability equals to 1 less packet loss rate. In the experiment, the average packet loss rate is computed by the packets record for the fixed time.Step 4.
Add a node to the experimental environment, and redo Steps1, 2, and 3.
This step changes the experimental condition by increasing the number of the neighbor nodes, and the next step is the same as Steps1, 2, and 3.Then the result of the experiment is shown in Figure2.Packet loss rate (a) and node reliability (b) of the experiment.
(a)
(b)From Figure2(a), we find that packet loss rate of the destination is not affected until where are seven neighbor nodes, and when the number of neighbor nodes reaches eight, the packet loss rate increases to 100% quickly. This also proves the above qualitative analysis.Based on the results of the packet loss rate, we can get the result of the node reliability, which is shown in Figure2(b).As in Figure2(b), we consider that the variety of the node reliability is similar to the style of hyperbolic tangent function, so we use an amended hyperbolic tangent function to fit the result of the node reliability. The fitting function is assumed as f(x)=(1-tanha(x-b))×c, where f(x) is denoted as the node reliability, x is the number of the neighbor nodes, and a,b,andc are the coefficients. The curve fitting of node reliability is shown in Figure 3.Figure 3
Curve fitting of the node reliability.The result of the curve fitting is shown in Algorithm1.Algorithm 1
Coefficients (with 95% confidence bounds):
a=0.896
b=9.953
c=0.4936
Goodness of fit:
SSE: 0.004319
R-square: 0.999
Adjusted R-square: 0.9989
RMSE: 0.01594From Algorithm1, we prove that the assumption of the fitting function is correct.Since the experiment is carried out in a real MANET platform and the experimental scheme is general, we consider that the node reliability is according to the form which we assumed above. Besides, the variety of node reliability is related to the coefficients of the assumption, because of the different wireless device, different packet size, different packet sending rate, and so on. As the above qualitative analysis, different wireless device means different capacity, which decides the beginning point of the decrease. The different packet size and packet sending rate influence the congestion, which results in both the beginning point of the decreasing and the rate of the decreasing. So the model of node reliability is formalized asri=(1-tanhα(gi-β))×γ, where ri is the node reliability of the node i, gi is the number of the neighbor nodes, and α,β, and γ are the coefficients which are related to the type of wireless device, packet size, and packet sending rate.


## 3.3.3. Reliability Calculation

Based on the link reliability and node reliability from the above analysis, two-terminal reliability of MANET can be conducted as follows:(1)2TR=∑k=1|C|2TRαk=∑k=1|C|P(αk=1)∏pathri=∑k=1|C|P(αk=1)∏path(1-tanhα(gi-β))×γ.This function shows that the topology of dynamic MANET can be divided into|C| configurations, and each configuration has its existence probability P(αk=1). In each configuration we search for the shortest path from source node to the destination node, and then node reliability of this path is represented by the multiplying of reliability of each node in the path. Of course, if there is no path from the source to the destination node, the reliability of this configuration is zero.Then we compute the 2TR by the above function. It is obvious that the most direct method is enumeration. The result is shown in Table2. The parameters are set as the first line of Table 2. Parameters are chosen randomly. From Table 2, we can find that 2TR increases with the number of the nodes, because the node reliability will not be influenced when the number of neighbor nodes is small.Table 2
Enumeration result of 2TR.
λ
=
0.5
,
α
=
1.0
,
β
=
10.0
,
γ
=
0.5
Nodes
Links
Configuration
2TR
Run time (s)
3
3
8
0.625
0.032
4
6
64
0.75
0.5
5
10
1024
0.8535
8.219
6
15
32768
0.9236
494.282
7
21
2097152
0.963
45635.8The computation of 2TR must be suitable for the MANET with large scale. Through theoretical modeling to analyze the reliability of MANET with only a few nodes is meaningless.  Since|C| is 2n(n-1)/2, the enumeration method iterates at least |C| times, which increases with the n exponentially. As in Table 2, it is obvious that the run time increases quickly with the configuration of the network: more than 12 hours is needed for the computation of 2TR when the number of the nodes is 7. So in order to analyze 2TR with large scale, it is necessary to introduce an efficient calculation method to compute the 2TR.


## 4. The Calculation and Analysis of 2TR

### 4.1. Calculation of 2TR

Since the computational complexity exponential increases with the number of the nodes, an efficient approximation algorithm is needed. Monte Carlo method is considered to be a useful simulation tool for the approximate computation of the network reliability, especially for the complex network with large scale [22]. And many recent reliability analysis researches utilize this method [4, 13, 14, 18]. Our calculation is an improvement of [4].We consider that the Monte Carlo calculation of 2TR is composed of many simulation samples. And each simulation sample can be divided into two procedures: the initialization procedure and the routing procedure.The initialization procedure is to generate the random link configuration matrix, which is according to the probability of link existence and the node reliability. The initialization procedure mainly simulates the node mobility and the failure of the node. The initialization procedure includes three steps.Step 1 (link simulation).
Simulate the capacity of every link, which either exists or does not exist, based on the probability of link existence. Generate a random number between 0 and 1, and compare with the probability of link existence, if the random number is not bigger than the probability of link existence; the link exists, otherwise, the link does not exist. Then the initial link configuration matrix is generated.Step 2 (node simulation).
Simulate the failure of every node, based on the initial link configuration matrix which is generated in Step1. Compute the node reliability of every node on the basis of the number of the neighbor nodes which can be goten from the initial link configuration. Generate a random number between 0 and 1, and compare with the node reliability; if the random number is not bigger than the node reliability, the node is active, otherwise, the node is failure.Step 3 (link resimulation).
Resimulate the link configuration matrix, based on the result of Step2. If the node is failure, the link must not exist.After each run, the random link configuration matrix is generated. Then the routing procedure is launched. The purpose of this procedure is to check the existence of path in the link configuration matrix which is generated at random in the initialization procedure. If there is a path form the source node to the destination node, the value of this samplesi is set to 1, otherwise the si is set to 0, where i represents the index of samples. Then, the Monte Carlo method of 2TR can be computed by the following function:
(2)2TRMC=∑i=1|S|si|S|.S is the set of samples, and the |S| represents the number of the  samples.  If the |S| is large enough, the 2TRMC can be approximated equal to 2TR. The simulation result, which is compared with the enumeration result, is listed in Table 3. The parameters are set as the first line of Table 2.Table 3
The comparison of enumeration result and simulation result.
λ
=
0.5
,
α
=
1.0
,
β
=
10.0
,
γ
=
0.5
,
|
S
|
=
1000000
Nodes
Enumeration
Monte Carlo
Relative error (%)
3
0.625
0.6243
0.112
4
0.75
0.7503
0.04
5
0.8535
0.8534
0.012
6
0.9236
0.9233
0.032
7
0.963
0.9633
0.031From Table3, we can see that simulation result is approximated to the enumeration result with the number of simulation samples equal to 1000000, and most of the relative errors between enumeration method and Monte Carlo method are below 0.1%.Furthermore, in order to observe the influence of the node reliability, the simulation result, which uses the Monte Carlo method to compute the 2TR with more node number, is shown in Figure4. Figure 4(a) is the variety of the 2TR when the node number rises from 3 to 50. Figure 4(b) is the computation time for each computation of 2TR in Figure 4(a). The parameters are set the same with the first line of Table 3. From Figure 4(a), we can find that 2TR is increasing with the node number at first, and at the point when the node number is equal to 10, the 2TR starts to reduce until 0. This is consistent with our above analysis. When the node number is small, the node reliability is not influenced, and more nodes joining the network bring more active links, then the probability of the path from the source node to the destination node increases with node number. However, when the node number keeps on rising, as the probability of link existence is fixed, there are more average neighbor nodes, which may result in the failure of the node, and more average neighbor nodes more failure nodes, then the 2TR will be reducing. Besides, Figure 4(b) also shows that the computation time of 2TR is not raising so much as the enumeration method, and the relationship between computation time and the number of nodes is almost linear function.Simulation result of 2TR.
(a)
(b)


### 4.2. Analysis of 2TR

After modeling the 2TR and computing the result, it is still necessary to analyze the sensibility of parameters in 2TR and find the key factor which influences the terminal reliability. Then the analysis result can be used to guide the design of the protocol and the deployment of MANET, which is the main purpose of the terminal reliability modeling for MANET.Firstly, we study the effect of probability of link existence by further experiment. The parameters of the node reliability are fixed andα=1.0,β=10.0,andγ=0.5. Then the probability of link existence changes from 0.1 to 1 and every time plus 0.1. At each value of the probability of link existence, we compute the 2TR with the node number varying from 3 to 40. The result is shown in Figure 5.Figure 5
Sensibility of probability of link existence.The “X” and “Y” represent the number of nodes and the probability of link existence. From Figure 6, we can find that there is a wave crest for each value of the probability of link existence. When the node number and the probability of link existence is small, the 2TR is small too, but both the node number and the probability of link existence are too many, and the 2TR is also small, even to zero. So when we deploy the MANET or designing protocol in this environment, it is necessary to compute the wave crest and make a balance between the node number and the probability.  As a similar cluster-based method introduced in [23], dividing MANET into small groups may be helpful for this environment. Besides, we also find that failure of nodes has more effect on the 2TR, especially when the node number is large. What is more, the probability of link existence influences the reducing rate of the 2TR. As in Figure 6, bigger probability of link existence makes the 2TR reduce more quickly with the node number. It also means that there is smaller redundancy when the probability of link existence is high, and we must make the balance more carefully.Figure 6
Sensibility of parameterα.Since the node reliability is more important, so it is necessary to analyze the influence of parameters in the node reliability. Here we only considerα and β, which have more effect on the node reliability.Figure6 shows the difference of the 2TR, when α is changing from 1 to 5. β, γ, and λ are set to 10, 0.5, and 0.5. The “X” and “Y” represent the value of α and the number of the nodes.From Figure6, we can find that 2TR is not sensitive with parameter α, when the α changes from 1 to 5, and the 2TR almost has not variety with the increasing node number. In fact, the α affects the reducing rate of the node reliability, and the variety of the node reliability is tiny with the changing of α.Then Figure7 shows the difference of the 2TR, when β is changing from 4 to 14. α, γ, and λ are set to 1, 0.5, and 0.5. The “X” and “Y” represent the value of β and the number of the nodes.Figure 7
Sensibility of parameterβ.From Figure7, we can find that 2TR is more sensitive to parameter α than β. In the function of the node reliability, the β mainly influences the point when the node reliability starts to reduce; in other word, β has the same meaning with the capacity of the node. So when deploying a MANET, it is important to notice and measure the capacity of the node.


## 4.1. Calculation of 2TR

Since the computational complexity exponential increases with the number of the nodes, an efficient approximation algorithm is needed. Monte Carlo method is considered to be a useful simulation tool for the approximate computation of the network reliability, especially for the complex network with large scale [22]. And many recent reliability analysis researches utilize this method [4, 13, 14, 18]. Our calculation is an improvement of [4].We consider that the Monte Carlo calculation of 2TR is composed of many simulation samples. And each simulation sample can be divided into two procedures: the initialization procedure and the routing procedure.The initialization procedure is to generate the random link configuration matrix, which is according to the probability of link existence and the node reliability. The initialization procedure mainly simulates the node mobility and the failure of the node. The initialization procedure includes three steps.Step 1 (link simulation).
Simulate the capacity of every link, which either exists or does not exist, based on the probability of link existence. Generate a random number between 0 and 1, and compare with the probability of link existence, if the random number is not bigger than the probability of link existence; the link exists, otherwise, the link does not exist. Then the initial link configuration matrix is generated.Step 2 (node simulation).
Simulate the failure of every node, based on the initial link configuration matrix which is generated in Step1. Compute the node reliability of every node on the basis of the number of the neighbor nodes which can be goten from the initial link configuration. Generate a random number between 0 and 1, and compare with the node reliability; if the random number is not bigger than the node reliability, the node is active, otherwise, the node is failure.Step 3 (link resimulation).
Resimulate the link configuration matrix, based on the result of Step2. If the node is failure, the link must not exist.After each run, the random link configuration matrix is generated. Then the routing procedure is launched. The purpose of this procedure is to check the existence of path in the link configuration matrix which is generated at random in the initialization procedure. If there is a path form the source node to the destination node, the value of this samplesi is set to 1, otherwise the si is set to 0, where i represents the index of samples. Then, the Monte Carlo method of 2TR can be computed by the following function:
(2)2TRMC=∑i=1|S|si|S|.S is the set of samples, and the |S| represents the number of the  samples.  If the |S| is large enough, the 2TRMC can be approximated equal to 2TR. The simulation result, which is compared with the enumeration result, is listed in Table 3. The parameters are set as the first line of Table 2.Table 3
The comparison of enumeration result and simulation result.
λ
=
0.5
,
α
=
1.0
,
β
=
10.0
,
γ
=
0.5
,
|
S
|
=
1000000
Nodes
Enumeration
Monte Carlo
Relative error (%)
3
0.625
0.6243
0.112
4
0.75
0.7503
0.04
5
0.8535
0.8534
0.012
6
0.9236
0.9233
0.032
7
0.963
0.9633
0.031From Table3, we can see that simulation result is approximated to the enumeration result with the number of simulation samples equal to 1000000, and most of the relative errors between enumeration method and Monte Carlo method are below 0.1%.Furthermore, in order to observe the influence of the node reliability, the simulation result, which uses the Monte Carlo method to compute the 2TR with more node number, is shown in Figure4. Figure 4(a) is the variety of the 2TR when the node number rises from 3 to 50. Figure 4(b) is the computation time for each computation of 2TR in Figure 4(a). The parameters are set the same with the first line of Table 3. From Figure 4(a), we can find that 2TR is increasing with the node number at first, and at the point when the node number is equal to 10, the 2TR starts to reduce until 0. This is consistent with our above analysis. When the node number is small, the node reliability is not influenced, and more nodes joining the network bring more active links, then the probability of the path from the source node to the destination node increases with node number. However, when the node number keeps on rising, as the probability of link existence is fixed, there are more average neighbor nodes, which may result in the failure of the node, and more average neighbor nodes more failure nodes, then the 2TR will be reducing. Besides, Figure 4(b) also shows that the computation time of 2TR is not raising so much as the enumeration method, and the relationship between computation time and the number of nodes is almost linear function.Simulation result of 2TR.
(a)
(b)


## 4.2. Analysis of 2TR

After modeling the 2TR and computing the result, it is still necessary to analyze the sensibility of parameters in 2TR and find the key factor which influences the terminal reliability. Then the analysis result can be used to guide the design of the protocol and the deployment of MANET, which is the main purpose of the terminal reliability modeling for MANET.Firstly, we study the effect of probability of link existence by further experiment. The parameters of the node reliability are fixed andα=1.0,β=10.0,andγ=0.5. Then the probability of link existence changes from 0.1 to 1 and every time plus 0.1. At each value of the probability of link existence, we compute the 2TR with the node number varying from 3 to 40. The result is shown in Figure 5.Figure 5
Sensibility of probability of link existence.The “X” and “Y” represent the number of nodes and the probability of link existence. From Figure 6, we can find that there is a wave crest for each value of the probability of link existence. When the node number and the probability of link existence is small, the 2TR is small too, but both the node number and the probability of link existence are too many, and the 2TR is also small, even to zero. So when we deploy the MANET or designing protocol in this environment, it is necessary to compute the wave crest and make a balance between the node number and the probability.  As a similar cluster-based method introduced in [23], dividing MANET into small groups may be helpful for this environment. Besides, we also find that failure of nodes has more effect on the 2TR, especially when the node number is large. What is more, the probability of link existence influences the reducing rate of the 2TR. As in Figure 6, bigger probability of link existence makes the 2TR reduce more quickly with the node number. It also means that there is smaller redundancy when the probability of link existence is high, and we must make the balance more carefully.Figure 6
Sensibility of parameterα.Since the node reliability is more important, so it is necessary to analyze the influence of parameters in the node reliability. Here we only considerα and β, which have more effect on the node reliability.Figure6 shows the difference of the 2TR, when α is changing from 1 to 5. β, γ, and λ are set to 10, 0.5, and 0.5. The “X” and “Y” represent the value of α and the number of the nodes.From Figure6, we can find that 2TR is not sensitive with parameter α, when the α changes from 1 to 5, and the 2TR almost has not variety with the increasing node number. In fact, the α affects the reducing rate of the node reliability, and the variety of the node reliability is tiny with the changing of α.Then Figure7 shows the difference of the 2TR, when β is changing from 4 to 14. α, γ, and λ are set to 1, 0.5, and 0.5. The “X” and “Y” represent the value of β and the number of the nodes.Figure 7
Sensibility of parameterβ.From Figure7, we can find that 2TR is more sensitive to parameter α than β. In the function of the node reliability, the β mainly influences the point when the node reliability starts to reduce; in other word, β has the same meaning with the capacity of the node. So when deploying a MANET, it is important to notice and measure the capacity of the node.


## 5. Conclusion

Most traditional terminal reliability analysis are based on theoretical analysis, but ignore the real influence of node reliability of MANET. The paper proposes a node reliability model for the MANET. Based on the node reliability model and traditional research, a new two-terminal reliability analysis for MANET is presented. Because of the complexity of the calculation, the paper also provides an efficient algorithm to compute the reliability for MANET, and the experiment results prove the correctness and efficiency of the algorithm. Furthermore, analysis of the experiment result shows that the node mobility of MANET causes more impact on the terminal reliability than the link reliability in the MANET and it is necessary to make a balance when deploying or designing protocol in MANET. Besides, the capacity of the node which influences the node reliability is also important for the deployment.



---

*Source: 216186-2013-04-09.xml*