Queing Model Network

Queuing Network Model for Link and Path Availability of Ad hoc Networks Vishal Jain

Monika Jain

M.Tech. (ICT), 200411029, DA-IICT. Post Bag No. 4,Gandhinagar, Gujarat, INDIA email: [email protected]

M.Tech. (ICT),200411022, DA-IICT. Post Bag No. 4,Gandhinagar, Gujarat, INDIA email: [email protected]

Abstract Ad hoc networks are networks where there is no fixed infrastructure. The mobile nodes are independent and have distributed control. Modeling of Ad hoc network is a critical task, which includes modeling of mobile behavior of nodes as well as behavior of wireless links. The mesh connected queuing network can be a good tool to model ad hoc network. In this work we are proposing a novel approach of modeling ad hoc network as a queuing network. The current state of art in modeling mobility in an ad hoc network consists of selecting a velocity and direction for a node and deriving an analytical model based on these parameters. This approach lacks the concept of path and link availability. In our novel approach, data taken from the various mobility scenarios through simulations are used to find out an appropriate distribution that gives connectivity between two nodes. The available and unavailable duration distributions obtained from AdHocSim are incorporated into queuing network. The effect of Velocity, Area and Pause time on link availability are studied and presented. We simulated queuing network in OMNet++. Packet error rate and Delay are measured and validated. Keywords Ad hoc networks, Link availability, Queuing, Modeling. 1 INTRODUCTION 1.1 Overview of Ad hoc Network Ad hoc networks [7] are networks where there is no fixed infrastructure. The mobile nodes are independent and have distributed control. These networks are low cost and easy to deploy. Ad hoc networks typically use wireless communication and hence transmissions are error prone. A particular node is able to transmit within some range depending on its power transmission capability. A node is able to communicate directly only with those nodes, which are within its transmission range. Ad hoc networks consist of nodes that are capable of routing packets. This routing capability helps one node to communicate with other node even if it is not in its transmission range. 1.2 Mobility Models

1-4244-0340-5/06/$20.00 ©2006 IEEE

Mobility models represent the mobile behavior of nodes in Ad hoc networks. A mobility model should attempt to mimic the movements of real mobile nodes. Changes in speed and direction must occur and they must occur in reasonable time slots. Few examples of mobility models [4] are given below. • Random Walk Mobility Model: A simple mobility model based on random directions and speeds. • Random Waypoint Mobility Model: A model that includes pause times between changes in destination and speed. • Random Direction Mobility Model: A model that forces Mobile nodes to travel to the edge of the simulation area before changing direction and speed. 1.3 Link Models Link model play a key role in performance analysis of Ad hoc networks. A link model models a link between directly reachable nodes. Few examples of link models [6] are given below: Gilbert-Elliott: Only two states are there one is good and other is bad, the model is described as two state Markov chain. K-state Markov chain: There are multiple states of link. Each state corresponds to a particular bit error rate (BER) value. The transition between neighboring states is allowed.

2. Related Work To the best of our knowledge very few researchers have attempted modeling of link and path availability in ad hoc networks by using statistical data. In [1] a closed form solution for connection availability of two hops ad hoc network is presented. Analytical expression for the leaving rate and the returning rate in the intersection region is also presented. But this work does not provide the connection availability model using the real probability distribution of the inter-leaving times. In [2] authors described a link and path availability model for Random walk mobility model. But this model would become complex as the complexity of underlying mobility model increases. In [3] a link and path model was analytically derived from Random walk

mobility model. But despite of all these models there is a need for a

successive movement of nodes and node density has been studied and results are as shown in next section

model, which can be applied, to all mobility models. Our work provides a framework to analyze not only synthetic models [4] but also traces [4]. In this work we propose link and path availability model using real probability distribution. Our model incorporates link and path model, thereby it is an improved modeling for real life scenario. A queuing network [8] is a collection of interactive queuing systems where departure of some queues form the arrival of others. In fully connected mesh network of queues, if links are modeled such that they emulate the behavior of wireless links and mobility, then the network can be considered analogous to ad hoc network. Further a closed form solution can be obtained for various metrics.

AdHocSim [5] was modified to generate connectivity duration for any two nodes in the network. TAB and TAB’ were collected and a distribution was generated. Various generated results for Random Direction mobility model are discussed in the next section.

3. Link Availability Our approach is to get a link availability & unavailability distribution among the nodes by simulations in AdHocSim [5] and then applying these distributions for one-hop, two-hop as well as multi-hop communication. Before going into details of the model let us see few definitions: 3.1 Definitions 1.

Field Area: It is the bounded area in which mobile nodes moves.

2.

Node-Node connection duration (TAB): It is the continuous duration for which two nodes remain connected.

3.

Node-Node disconnect duration (TAB’): It is the continuous duration for which two nodes remain disconnected.

4.

Node-Node connection duration distribution (D (TAB)): It is the distribution of TAB

5.

Node-Node disconnect duration (TAB’)): It is the distribution of TAB’

6.

P (A): It is proximity of node A corresponding to transmission range of A

7.

P (A’): It is part of field area which is not in the transmission range of A

8.

Trace of a node (TA): It is defined as the path followed by node A under some mobility model

9.

P(A, TB): Trace of node B in A’s proximity

distribution

(D

3.3 Simulation Results A) Independence of pair of nodes chosen For 100*100 square units of field area with three nodes, fig.1 and fig.2 shows TAB and TAB’ for different pair of nodes. Clearly the distributions are independent of the chosen node pair.

Fig.1 Node-Node Connection duration

Fig.2 Node-Node Disconnect duration

C) Effect of increase in Area It is clear from fig.3 that for same number of nodes as we increase the area mean TAB decreases and mean TAB’ increases.

Fig.3 Variation of TAB & TAB’ with Area

D) Effect of velocity The fig.4 shows that for same area and same no of nodes with increase in velocity the mean TAB and mean TAB’ decreases.

10. P’(A, TB): Trace of node B not in A’s proximity 3.2 Simulation Scenarios We simulated three mobility models namely Random direction, Random walk and Random waypoint. The effect of field area, velocity of nodes, pause time between

Fig.4 Variation of TAB & TAB’ with Velocity

Fig.5 Variation of TAB & TAB’ with Pause Time Fig.6 Single Hop Queuing Network

E) Effect of pause time Fig. 5 shows that for same area and same no of nodes with increase in pause time the mean TAB and mean TAB’ increases.

In our work we are modeling wireless link using a finite state discrete time Markov process . Let S = {SO, SI,…….. , SN} denotes the state space of the Markov process. As shown in Fig 7, the transition probabilities are

Theorem 1: For a particular mobility model scenario increase in area causes mean of D (TAB) to decrease and mean of D (TAB’) to increase.

{ai , i = 1,2,. . . ,N} and { bi , i = 1 , 2 , . . . , N}, respectively. Each state i is associated with a Bit Error Rate (BER) Pi.

Proof. Suppose we have two nodes A and B. Without loss of generality we can assume that node A is stable and B moves in the field with respect to A. The trace of B in P (A) have length l and in P (A’) be m. With increase in area the node is allowed to move in larger field therefore value of m increases. Thereby mean D (TAB) decreases and mean D (TAB’) increases. Theorem 2: For a particular mobility model scenario with increase in velocity of nodes the mean of D (TAB) and mean of D (TAB’) decreases.

We assume Pi's are in decreasing order, with PO = 1 (the link is down) and PN = 0 (no loss at all). a2

a1 1-a1

S0

an

S1 b1 1-a1-b1 b2

SN

1-bn

bn

Fig. 7 Markov Chain Model

Proof. We have two nodes say A and B. Without loss of generality we can assume that our node A is stable and B moves in the field with respect to A. The trace of B in P (A) have length l and in P (A’) be m. l and m are independent of velocity of node, hence by increasing velocity the time to traverse l and m decreases.

4.1 Validation of model To validate our model we took packet error rate and delay as metrics. Let us define a state S of the link, which gives the availability and unavailability of the link. Here S=1 implies that link is available and S=0 implies link is unavailable.

4. Single hop Communication model

Let D (TAB) is approximated to d (µ,σ) and D (TAB’) is approximated to d (µ’,σ’). Now state S of the link can be formulated as:

The proposed model, as simulated in OMNet++ [9], consists of nodes as shown in fig. 6. The internal architecture of each node is shown in next figure. It consists of an application, which generates packets at a rate of λ. These packets get accumulated in the queue at the sending node. Now, scheduler will check whether link is available or unavailable. An available duration is obtained from D (TAB), which indicates the duration for which node A is in transmission range of node B. When this duration expires a selftrigger message is generated which lead to generation of unavailability duration out of D (TAB’), and this cycle goes on. If link is available and there is no other packet on the link then packet is forwarded on the link.

S = f (µ,σ,µ’,σ’)

(1)

In our simulations, we simulate bit error rate on the link. Packet with length l is being transmitted along the link and its first bit is transmitted at time t. Assume that the Bit error rate (BER) of the link models, p (t), has taken FEC into account, i.e., a packet is lost if one or more bits of the packet are corrupt. Then the loss probability for the packet over the link when S=1: PERn (t) =

l 1- Π [1-p (t+i-1)] i=1

(2)

The value obtained for PER from above equation is compared with the value obtained from proposed model and both the values are matching as shown in fig.8 below.

Fig. 9 Variation of Mean Packet Delay

Fig. 8 Variation of Packet Error Rate

The model described follows M/X/∞ queuing discipline. Where X is service rate distribution derived from alternative selection of available and unavailable distribution. Let λ be the arrival rate of packets, which may be assumed to have exponential distribution. Service time is assumed to be a function of link delay d, transmission rate r and average packet length Lav. τ = φ (d , r, Lav)

(3)

Initially it looks for the availability of one-hop path. If not found, then it checks for two hop paths out of possible nC2 paths. A two-hop path between S and D is available if both the links forming path are available. For store-and-forward networks, the loss probability over the entire path of h hop for a packet starting at time t is: `

Hence service rate will be µ=(1/τ)

designed a 4 node open queuing networks as shown in fig. 10.

PERn (t) =

(4)

{ 1- Π [1-PER h

K =1

n

k (t

+ (k-1) * ln)]

}

(5)

Little’s Theorems [8] should hold true for above values of λ and µ. Closed form solutions are not available for these parameters but empirical calculation follows Little’s Theorems. We measured delay obtained from AdHocSim and compared it with the values obtained from proposed Queuing model. Measurements of delay were taken and results are as shown in the fig. 9 below. Results clearly show that values obtained from AdHocSim closely matches with the values obtained from proposed model. Fig. 10 Open Queuing Network with 4 nodes

5 Multi-hop Communication After modeling and validating single hop results we can proceed towards modeling of multihop communication between nodes in ad hoc network. We consider a complete connected graph of (N+2) nodes. N nodes are routers and other 2 nodes are source S, and destination D. From theorem 1, it is clear that node-node available or unavailable behavior remains same for any pair of nodes. The model is designed in such a way that it always find out shortest possible path in the network. For simulation purposes we have

If we assume link is always available then following equation holds. (I-PT) Λ = Γ

(6)

In the above equation [8] P is a matrix whose Pijth element gives the probability with which a customer leaves ith node and joins jth node, I is the identity matrix, Λ is a column vector giving effective arrival rate and Γ is a column vector giving external arrival rate.

The proposed queuing network delay is compared with the delay obtained from AdhocSim simulation. Both shows similar results. 6 Conclusion and Future Work In this work we have proposed a novel approach of modeling ad hoc network as mesh connected queuing network. The real distribution of available and unavailable duration is obtained from AdHocSim. Our approach not only fits for synthetic model but also for traces. The effect of variation of velocity, area and pause time on these distributions is studied. These distributions are incorporated into queuing network simulated in OMNet++. The links are modeled using K-state markov chain model. The results obtained from AdHocSim as well as OMNet++ are compared and presented. An abstract analytical model is developed for ad hoc network. We have studied three mobility models. A future work can be attempted to study group mobility models and other entity mobility models. As an extension to this work we are trying to obtain closed form solution for the proposed analytical model. Acknowledgement We would like to express our sincere thanks to Prof. R.B. Lenin and Prof. Sanjay Srivastava for their fruitful ideas during the entire course of this work.

References [1] Dimitar Trajanov, Sonja Filiposka et.al, Ad hoc Networks connection availability modeling, PE-WASUN, Italy, 2004. [2] A.Bruce McDonald,Taieb Znati, A path Availability model for wireless Ad hoc networks,IEEE WCNC,USA,1999 [3] Dan Yu,Hui Li,Ingo Gruber, Path Availability in Ad hoc network, ICT'2003, 2003, Tahiti, French Polynesia. [4] Tracy Camp, Jeff boleng, Vanessa Davies, A survey of Mobility models for Ad hoc network research, WCMC, 2002. [5] Nicola Concer, Adhocsim,2004. [6] Shiwen Mao, Shunan lin, Panwar, Wang, Reliable transmission of Video over Ad hoc networks using Automatic repeat request and Mutipath transport, IEEE 2001. [7] Perkins, Charles E, Ad Hoc networking, AddisonWesley, Boston, 2001. [8] E. Gelerbe, G. Pujolla, J.C.C. Nelson, Introduction to Queuing Networks, John Wiley & Sons. 1987. [9] www.omnetpp.org