Mobile Edition
Print
Get the Mag
Weekly Updates1. Introduction
Perkins and Bhagwat (2001) and Toh (2002) were the first to describe the Mobile Ad hoc Wireless Network (MAWN) which is a rapidly developing technology. These authors provide examples of the applications for which MAWNs are being developed; they include personal, commercial and military networks. As the MAWN migrates from a developmental network scheme to a ubiquitous commodity, the expectation for and importance of reliable operation will grow.
The MAWN is a network that is absent of infrastructure and consists only of mobile nodes, also referred to as terminals, which form the network by connecting to other neighboring nodes via wireless links. The result is a flexible network with a dynamic network topology. The topology of the MAWN, also referred to as its configuration, continually changes in order to adapt to the needs of its member nodes. Current research in this area focuses on the development and refinement of protocols which can be resilient in the face of node mobility and the associated network volatility. Volatility, as it pertains to a MAWN, describes the frequency and scope of changes to the connectivity configuration of the network.
It is this same aspect of the MAWN (continuously changing configurations) that makes the traditional single reliability block diagram analysis inappropriate. In order to capture the flexibility of a MAWN in a reliability model, it must be acknowledged that the initial configuration of the network will change throughout the mission's duration. The exact configuration(s) cannot be either predicted or controlled with certainty rather, they can only be described probabilistically. Much research has been done on related topics, including: the reliability of infrastructure-based networks, mobility modeling and ad hoc network protocols. This research is summarized in Section 2 of this paper. However, for reliability purposes, these topics have not been integrated previously; with the exception of the paper by Cook and Ramirez-Marquez (2007) - a work upon which this paper expands.
This paper seeks to fill the need for reliability analysis methods that consider node mobility and the resultant impact on network configuration(s) in tandem with node and network reliability. Without such methods, the state of the art lacks the capacity to consider the reliability of a MAWN or optimize its design during the development phase of the system's life cycle.
In order to design and deploy a reliable MAWN the ability to determine reliability and identify the primary factors influencing this measure is essential. The proposed Monte Carlo (MC) simulation method transforms existing reliability methods and links mobility modeling techniques in such a way so that the parameters characterizing a MAWN can be identified and the two-terminal reliability of the MAWN may be approximated.
The remainder of this paper is organized as follows: Section 2 describes, in greater detail, the ad hoc networking concept, its applications and the focus of recent research in related fields. Section 3 discusses and defines a group of metrics that apply directly and indirectly to the reliability of a MAWN and describes a new MC method to obtain accurate approximations. These time-dependent metrics include: two-terminal reliability for a MAWN, network coverage and network volatility. As an example, Section 4 applies the proposed MC method to analyze a tactical (military) MAWN. This implementation is analyzed and the results are presented. Finally, Section 5 explores the sensitivity of MAWN reliability when several parameters are individually varied. The paper is then concluded with a discussion of the contributions of this work and recommendations of future research in this area.
Assumptions
1. The source node is known and constant.
2. The starting position of the nodes is known, and nodes are connected if they are within a defined transmission range. That is, route discovery and route maintenance is performed without failure and instantaneously.
3. Nodes move randomly according to the random waypoint mobility model.
4. All nodes have the same reliability and performance capability (range).
5. A link either exists or it does not exist. As shown by Pahlavan and Krishnamurthy (2002), in practice, links may have a diminished capacity as path loss increases. If the link exists, the capacity is sufficient to pass all traffic taking that route.
6. Node failures are statistically-independent and are not repaired during the mission. Node failures are assumed binary. That is, a node is either completely operating or completely failed.
Notation
N = set of nodes;
|L(t)| = operator representing sum elements in L at time t;
[absolute value of (N)] the number of nodes in the network;
[n.sub.i] = a binary variable representing the state of the ith node;
[r.sub.i](t) = reliability of node i:
G(N, L) = network G, composed of nodes and their links;
[l.sub.i,j](t) = wireless link between nodes i and j;
L(t) = link configuration matrix;
2T[R.sub.m](t) = two-terminal MAWN reliability;
[LAMBDA](t) = connectivity vector;
[[LAMBDA].sub.i](t) = connectivity of ith node to the source;
Q = number of runs in the MC simulation;
[d.sub.i,j](t) = distance between nodes i and j;
[[tau].sub.ij] = radial transmission range;
[x.sub.i](t) = position of the ith node along the x-axis;
[y.sub.i](t) = position of the ith node along the y-axis;
[chi](t) = connectivity of the network;
[theta] = scale parameter of the Weibull failure distribution;
[beta] = shape parameter of the Weibull failure distribution;
[[upsilon].sub.i](t) = velocity of the ith node;
[[phi].sub.i](t) = direction of the ith node;
[bar.[omega]](t) = volatility of network link status.
2. Related works
2.1. Ad hoc networks--concept, design and application
Toh (2002) defined an ad hoc network as "a collection of two or more devices equipped with wireless communications and networking capability." He further expanded the description by explaining the method by which their networking capability is realized. Like point-to-point radios, ad hoc devices can communicate directly with other devices within their range. However, unlike their predecessors they may also communicate with those outside their range by using intermediate nodes to relay or forward the message to the destination node. This second capability, multi-hop communications without network infrastructure, is what makes ad hoc networking unique. In contrast with other networks, the MAWN makes use of only its own nodes to enable communication paths. As such, a MAWN does not require the infrastructure of traditional networks; routers, switches, wiring, base stations, etc. The links between MAWN nodes are created and terminated as these nodes move into and out of each others' range. The volatility (frequency and significance of change) of the network configuration is a result of the mobility of its nodes.
Perkins and Bhagwat (2001) described the task of designing an ad hoc network. These authors summarized the objective as follows: "operate each mobile node as a specialized router, which periodically advertises its view of the interconnection topology with other mobile nodes within the network." The unique capability is that nodes do not only send and receive but also relay messages. The challenge then, is dealing with the impacts of mobility and a non-deterministic network configuration. For the most accurate picture of topology, a continuous advertisement of path information is required. However, this is not practical due to bandwidth and power constraints. For an optimal solution, the network volatility must be considered.
In addition to military applications, the commercial sector has acknowledged the benefits offered by the MAWN. Perkins and Bhagwat (2001) described the commercial applications of ad hoc networking, including: conferencing, home networking, personal networks (i.e., Bluetooth) and embedded computing. Ad hoc networking is used in conferencing when the infrastructure that enables an office LAN is not available such as, within a conference room without wired internet. Similarly, home and personal networks employ MAWN technology when wired access is not practical.
2.2. MC methods for network reliability
Due to the analytical complexity and computational cost of developing a closed-form solution, simulation methods, specifically MC simulation, are often used to analyze network reliability. Elperin et al. (1991) presented a MC method used to solve network reliability problems where graph evolution models are used to increase the accuracy of the resultant approximation. Rocco and Moreno (2002) proposed two methods to analyze the two-terminal reliability of networks. These methods leverage cellular automata to refine the approach and avoid unnecessary recalculations. Cancela and El Khadiri (2003) proposed a method to solve the k-terminal reliability problem; specifically they proposed a formulation using a recursive variance-reduction MC estimator. The primary contribution of their method is a reduction in simulation time while providing an accurate approximation. Marseguerra et al. (2005) developed a MC method to obtain an approximation of network reliability in the presence of uncertainty about the reliability of both links and nodes. Recently, Cook and Ramirez-Marquez (2007) provided analytical and MC-based methods to determine the two-terminal reliability of a MAWN (2T[R.sub.m]). In that previous publication, the existence of links was considered in a probabilistic manner to account for the unique features of the MAWN. However, there remains a gap in understanding the exact link between a probability and a specific mobility profile for a node. This paper expands upon the first work of Cook and Ramirez-Marquez (2007) by including, directly, mobility models in order to allow mobility parameters, such as maximum velocity, to be varied and therefore analyzed directly. The methods within this paper will now allow for the determination of reliability impacts under specific mobility considerations. As an example, one may consider the different reliability when the same networking radios are used to create a network on two different types of vehicles.
FEED