مدلسازی و تجزیه و تحلیل عملکرد از هاپ شبکه های ad hoc چندگانه

Mobile ad hoc networks are becoming very attractive and useful in many kinds of communication and networking applications. Due to the advantage of numerical analysis, analytical modelling formalisms, such as stochastic Petri nets, queuing networks and stochastic process algebra have been widely used for performance analysis of communication systems. To the best of our knowledge, there is no previous analytical study that analyses the performance of multi-hop ad hoc networks, where mobile nodes move according to a random mobility model in terms of the end-to-end delay and throughput. This work presents a novel analytical framework developed using stochastic reward nets for modelling and analysis of multi-hop ad hoc networks, based on the IEEE 802.11 DCF MAC protocol, where mobile nodes move according to the random waypoint mobility model. The proposed framework is used to analyse the performance of multi-hop ad hoc networks as a function of network parameters such as the transmission range, carrier sensing range, interference range, number of nodes, network area size, packet size, and packet generation rate. The proposed framework is organized into several models to break up the complexity of modelling the complete network, and make it easier to analyse each model as required. The framework is based on the idea of decomposition and fixed point iteration of stochastic reward nets. The proposed models are validated using extensive simulations.

Traditional wireless communication networks, namely cellular and satellite networks, require a fixed infrastructure over which communication takes place. Accordingly considerable efforts and resources are required for such networks to be set up, before they can actually be used. In cases where setting up an infrastructure is a difficult or even impossible task, such as in emergency/rescue operations, military applications or disaster relief, other alternatives need to be devised. Mobile ad hoc networks (MANETs) are stand alone wireless networks that lack the service of a backbone infrastructure [1]. They consist of a collection of mobile nodes, where the mobile nodes act as both sources and routers for other mobile nodes in the network. A node can send a message to another node beyond its transmission range by using yet further nodes as relay points operating as routers. This mode of communication is known as wireless multi-hop. All nodes of the network have the same capabilities and no base stations or central access points need to be involved in the data exchange. In some instances, a gateway node may be presented in an ad hoc network which may allow the nodes to communicate with an external network, e.g. the Internet. In MANETs, each node is supplied with an antenna that allows it to transmit and receive information from the other nodes. The antenna can radiate and receive within a certain radius, called the transmission range. The radius is determined by the transmission power. When a node transmits to another node, its transmission can be heard by all nodes that lie within the transmission range. The higher the transmission power, the larger the number of nodes that can be reached in a single transmission, but also the higher the amount of the interference that may be experienced. The network is formed as soon as one of the nodes expresses a wish to exchange information with one of the other nodes (unicast) or with more than one node (multicast). Such networks were initially designed for use in the military and emergency relief applications. Lately, the ad hoc network model has been proposed in many other applications [1]. Mobile ad hoc networks share many of the properties of wired and infrastructure wireless networks, but also have certain unique features which come from the characteristics of the wireless channel. Nodes in MANETs are free to move, thus the network topology may change rapidly and therefore, nodes need to collect connectivity information from other nodes periodically. One implication of this is an increased message overhead in collecting topology information. Mobility is a crucial factor affecting the design of MANET protocols, including Medium Access Control (MAC), Transmission Control Protocol (TCP), and routing protocols. Mobile ad hoc networks are becoming very attractive and useful in many kinds of communication and networking applications, due to their efficiency, simplicity (in installation and use), relatively low cost, and availability. It is to be noted that most of the research that has studied the performance of MANET was evaluated using Discrete event simulation (DES) utilizing a broad band of simulators such as NS2 [2], OPNET [3], and GloMoSim [4]. The principal drawback of DES models is the time and resources needed to run such models for large realistic systems, especially when results with high accuracy (i.e. narrow confidence intervals) are required. Due to the advantages of numerical analysis, analytical modelling formalisms, such as stochastic Petri nets and stochastic process algebra, have been used for performance analysis of communication systems. Compared to measurement and simulation methods, analytical modelling is a less costly method [5] and [6]. It generally provides the best insight into the effects of various parameters and their interactions [5] and [7]. Hence, analytical modelling is the method of choice for a cost effective evaluation of communication systems. Multi-hop ad hoc networks are too complex to allow analytical study for explicit performance expressions. Consequently, the number of analytical studies of this type of network is small [8], [9], [10], [11], [12], [13], [14], [15], [16], [17] and [18]. In addition, most of these studies have a number of drawbacks, which can be summarized as follows: 1. Most of analytical research in MANET supposes that the nodes are stationary (no mobility), or the network is connected all the times, to simplify the analysis [8], [9], [10], [11], [12], [13], [14], [15], [16], [17] and [18]. 2. In order to be mathematically tractable, most analytical studies suppose that the nodes in the network area are uniformly or regularly distributed [9], [11], [12] and [16]. 3. Some of the research is restricted to the analysis of single hop ad hoc networks [8], [9], [10] and [13]. 4. The impact of the interference range on the performance of multi-hop ad hoc networks is either ignored or largely simplified [8], [9], [10], [11], [12], [13], [14], [15], [16], [17] and [18]. 5. To simplify the analysis, most studies investigate MANETs in the case of a saturated traffic load (i.e. at all times every node has a packet to send) or finite load traffic, not in both cases [8], [11], [12] and [14]. 6. For computing the expected length (number of hops) of paths in multi-hop ad hoc networks, inaccurate approximate methods have been used [14], [15] and [16] (see Section 2 for more detail). 7. To reduce the state space of the analytical models of MANETs, most of the research is macroscopic (dynamics of actions are aggregated, motivated by limit theorems) [8], [9], [10], [11], [12], [13], [14] and [16]. To the best of our knowledge, there is no analytical study that analyses the performance of multi-hop ad hoc networks based on the IEEE 802.11 MAC protocol, where nodes move according to a random mobility model, in terms of the end-to-end delay and throughput. This work presents an analytical framework, developed using the Stochastic Reward Net (SRN) [19] and mathematical modelling techniques, for the modelling and analysis of multi-hop ad hoc networks based on the IEEE 802.11 DCF MAC protocol where nodes move according to the random waypoint mobility model (RWPMM). The proposed framework is used to analyse the performance of multi-hop ad hoc networks as a function of different parameters such as transmission range, carrier sensing range, interference range, node density, packet size, and packet generation rate. Although the proposed framework is specific to a certain type of a MAC protocol and random mobility model, it can be adapted for use with other MAC protocols and mobility models. The proposed methodology could also be used to analyse other type of networks. To present an approach for the modelling and analysis of large-scale ad hoc network systems, there are two requirements in advance. First, the model should be detailed enough to describe some important network characteristics that have a significant impact on the performance. Second, it should be simple enough to be scalable and analyzable. It is clear that these two requirements are potentially contradictory. To fulfil these two requirements, to model multi-hop ad hoc networks using stochastic reward nets, we cannot construct a model for all nodes in the network by placing a model for each node into it one by one, because we will face the state explosion problem. Alternatively, in the same way as introduced in previous studies [8], [9], [10], [11], [12], [13], [14], [15], [16], [17] and [18], by exploiting the large amount of symmetry in multi-hop ad hoc networks in order to simplify the analysis, only the behaviour of a single hop communication between any two nodes in the network needs to be modelled. Then, the single hop communication model is used to derive some parameters that are used to compute performance metrics, such as delay and throughput, for the entire path. Single hop communication is modelled under the average workload computed for all possible instances of network topologies taking into account the average effects of the random access behaviour of each node, the buffer overflow probabilities at each node, interference induced from neighbour and hidden nodes, and frequent path failure and redirection due to random mobility of nodes. Because the underlying CTMC would be far too large for numerical analysis, we cannot model the single hop communication using one SRN model. Therefore, to do that, we propose a framework organized into several models to break up the complexity. The proposed framework consists of one mathematical model (called the path length model), and four SRN models (called the path analysis model, data link layer model, network layer model and transport layer model). The proposed framework is based on the idea of decomposition and fixed point iteration [20] and [21] of stochastic reward nets. Thus, to derive any network performance metric, the SRN models are solved iteratively until the convergence of the desired performance metric. The proposed models describing the behaviour of a single hop communication are used to evaluate the delay and throughput per hop which are used to compute the end-to-end delay and throughput per path. It is clear that the choice of metric greatly influences the way in which the analysis is undertaken. Therefore the approach presented here is specific to these metrics, and considering different metrics, for instance those based on variance or percentiles, would require the specification of a different analysis algorithm. The rest of the paper is organized as follows. Section 2 discusses the related work. Section 3 describes the adopted network model and assumptions. The proposed framework for modelling a single hop communication between two nodes is presented in Section 4. Section 5 analyses the paths traffic load to derive expressions for the average packet forward rate per node and throughput per path. Section 6 includes the calculation of the expected number of interfering and hidden nodes. The data link layer and network layer model is presented in Sections 7 and 8, respectively. In Section 9, the analytical procedure used to solve the proposed models is introduced. Section 10 presents results of the analytical models and simulation. Conclusions and future work are given in Section 11.

This work introduces an analytical framework for modelling and performance analysis of multi-hop ad hoc networks based on the IEEE 802.11 MAC protocol, where nodes move according to the random waypoint mobility model. The proposed framework consists of five models; the path length model, path analysis model, data link layer model, network layer model, and transport layer model. To compute the required performance indices, such as delay and throughput, the SRN models are solved iteratively using the fixed point iteration technique. The effects of various network factors, such as communication range, density of nodes, random access behaviour, interference range, carrier sensing range, and traffic load, on the performance of the network in terms of the end-to-end delay and network throughput, have been analysed. The proposed models are validated using extensive simulations. The results show a close match between the analytical results and those obtained from the network simulation using NS2. The computation time needed to solve the proposed analytical models is negligible compared to that of the simulation model. The computation time of the network simulation increases exponentially with the number of nodes in the network. With a large number of nodes, the network simulation is computationally expensive and ultimately infeasible. Analytical results show that the carrier sensing range, packet size, network area size, interference range, and transmission range have great effects on the performance of multi-hop ad hoc networks based on the IEEE 802.11 MAC protocol for either the BA or RTS/CTS scheme. From analytical results, the following conclusions are drawn: (1) In multi-hop ad hoc networks, as opposed to single hop ad hoc networks, the BA method outperforms the RTS/CTS method especially in conditions of heavy load, high node density, large packet size, and large carrier sensing or transmission ranges. This is because of the blocking problem which arises in the RTS/CTS mechanism. (2) For both the BA and RTS/CTS schemes, the performance of multi-hop ad hoc networks deteriorates with increasing the carrier sensing range. This is because of increasing number of interfering nodes which increases the probability of packet collision and contention between nodes, and decreases the channel availability. (3) Decreasing the size of network area has two contradictory effects on network performance. Although reducing it decreases the path length, which improves network performance, it also increases node density which increases interference and contention between nodes and thus packet collision probability. This causes network performance for either BA or RTS/CTS methods to degrade. (4) Increasing the transmission range may improve the performance of the network due to decreasing path length. However, it also increases the interference range. The greater the interference range, the greater the interference induced by hidden and interfering nodes, which causes deterioration in network performance. Therefore, for both BA and RTS/CTS methods, due to these two contradictory effects, increasing the transmission range does not usually enhance the performance of the network, although this depends on other network parameters. As the next step of this study, to improve the proposed model, for the time delays of non-Markovian (deterministic or nondeterministic) events and actions (transitions) that have been approximated with exponential distributions, we will apply phase-type distributions. However, this will increase the complexity and computation time of analysis of the models. Also, the proposed framework will be used to compute the optimal frame size, transmission range, carrier sensing range, and node density according to different network parameters and channel conditions so as to maximise network throughput and minimise end-to-end delay. Moreover, we aim to model and evaluate the Transmission Control Protocol (TCP) in multi-hop ad hoc networks using the proposed framework. In addition, other routing protocols, random mobility models, and MAC protocols well be adopted. This paper has focussed exclusively on deriving mean performance metrics. This analysis has been a non-trivial undertaking and represents a significant step forward in the modelling of MANETs. Average metrics are fundamental to understanding performance, but they are also limited. It would clearly be desirable to derive expressions for variance or percentiles that would give greater understanding of the likelihood that a level of performance could be achieved. However, this would be a significant additional task, requiring a major redesign of the approach developed in this paper. It would be computationally feasible to derive expressions to approximate variance, for instance using the simple methodology based on computation based on marginal probabilities, presented in [35]. Such approximate methods have been shown to work well only in situations where there is only limited dependency between components, which is not the case for the models in this paper. As such, applying these methods directly would be of dubious potential value as a prediction of variance, but might still be useful in comparing competing deployment scenarios. We intend to explore this issue further in future work.