Modeling and Analysis on a DTN Based Wireless Sensor Network Topology Control

Published Online October 2009 in MECS

Wireless sensor networks (WSNs) serve as a significant role to bridge the gap between the physical and logical worlds [1]. Nodes in WSNs are tiny embedded devices which only own limited computing ability, data storage space, constrained battery energy and narrow wireless network band width. Among the most critical issues of WSNs is nodes’ energy consumption in general. So, usually, in a WSNs application, to save the battery energy in each node, node can be in power saving model, or in sleeping mode which may lead intermitted network connection and long time delay of transmission

Manuscript received January 20, 2009; revised June 20, 2009; accepted July 20, 2009.

This paper is partly supported by Shanghai Normal University SK200709, DZL805, CL200652 and PL531.

even data transmission failure. To address the issue, in former paper we use the idea of delay tolerant network (DTN) protocol and prompted a delay tolerant wireless sensor web service framework (DTN-WSN-WS) as well as performance analysis which partly solved some relate problems[9,10].

Figure.1 DTN-WSN-WS Frame Work.

In recently further study, we found that although intermitted network connection in WSNs is not a good phenomenon in network, when it occurs, it indeed can keep some nodes in power saving mode. For most WSNs applications has some levels real time tolerant specifications constraints (or the maximum time delay tolerant, which is denoted by T _QoS ), for an example, some nodes must send the data to sink node each 10 minutes. To save the battery energy in nodes, during the 10 minutes intervals of data transmission there is no need to keep a network connection. If we can intelligently control WSNs network topology and get intermitted network connection during the 10 minutes intervals of transmission, we will find another way to save the nodes energy to the maximum extent.

Based on these ideas, we import the idea of Delay Tolerant Network (DTN) protocol. In this paper, first we give the modeling and analysis on node behaviors in DTN WSNs, then we present the end to end performance analysis in DTN WSNs to get the parameters of optimistic hops, maximum hops and each node’s neighbor number, after that we give some basic rules on DTN parameters selection for DTN based WSNs topology control. Finally, we do a related simulation by our DTN based WSNs topology control approach and HER routing algorithm; simulation results show that our approach and algorithm gained better performance in WSN life span, nodes energy equilibrium consumption than DADC.

• II.    RELATED WORKS

Topology Control (TC) is one of the most important techniques used in wireless ad hoc and sensor networks to reduce energy consumption and radio interference. [1] gave a whole survey of topology control for WSN. [2] proposed a distributed k-connected (KC) energy saving topology control algorithm for wireless sensor networks. In the algorithm, each node constructs a local k-connected sub-network independently based on the neighbor topology information, and adjusts its transmission power using a Max-Min method to save energy. [3] proposed the event-to-sink reliable transport (ESRT) protocol, which is a novel transport solution developed to achieve reliable event detection in WSN with minimum energy expenditure. [4] gave a topology control method for multi-path wireless sensor networks.[5] gave a topology control for delay sensitive applications in wireless sensor networks,[6] presented a energy-aware topology control for wireless sensor networks using mimetic algorithms, [7] put forward a energy-efficient localized topology control algorithms in IEEE 802.15.4-based sensor networks,[8] gave a algorithms for fault-tolerant topology in heterogeneous wireless sensor networks.[9] put a topology control and geographic routing in realistic wireless networks.

These papers share the common goal of this technique, which is to control the topology of the graph representing the communication links between network nodes with the purpose of maintaining some global graph property (e.g., connectivity), while reducing energy consumption and/or interference. Intermitted network connection should be avoided in topology control.

For the core current communication theory and protocols in WSNs are inherited from traditional wired or wireless network, and the preconditions of related research works are supposed to have at least one route existing from data transmitting source to destination and small delay of transmission. Intermitted network connection does not meet the preconditions of research; there is no doubt to see that most related protocols will run into fatal problems. When intermitted network connection phenomena occurs in WSNs, if traditional communication protocols are taken, nodes in WSNs may mistakenly treat intermitted network connection phenomena as network congestion or packets lose in transmission, to make matter worse, they may deal with these issues by adjusting the size of data sending window or resending packets which will lead much network traffic, lower network performance and much nodes battery energy consumption. So how to cope with intermitted network connection problem is becoming a new and challenge issue in WSNs. To the best of our knowledge, we think that these papers do not yet do related study on how to use Intermitted network connection phenomenon to control the topology of WSNs and save each node’s energy.

• III.    P ROBLEM D EFINATION

A wireless sensor network is denoted with Nwsn , Nwsn = {n1, n2 K niK}, ni is a node in Nwsn , ni is with a specific geographic location, battery power and 2 < i < N , the total number of nodes in WSN is denoted with Nwsn [9,10].

n_i ’s next hop nodes (or neighbor node) set is denoted with N c , N c = { n^j ,K, n k } , | N T| is the total number nodes of n_i 's neighbor node. Note that N_i^c may be controlled by dynamic regulating the signal power of each node, for example, by controlling each node’s sensing or transmitting power (or keeping some node in power saving mode), we can get different number of N_i^c for n_i . Set N_i^c is one problem of topological control for WSN. It is the initial parameters to calculate the routing, and very important for routing selection.

In traditional wired or wireless network, it supposed to have at least one route existing from data transmitting source to destination and small delay of transmission. At a given instant time t_i , a route can be denoted with R , ( t\t = t i ) ,and R , ( t\t = t i ) = { n s , L , n d }, where n_s is the source node, and n_d is the destination node, and s Ф d . h i (t|t = t i ) denotes the total hops of the route. We use R ( t|t = t i ) to denote the set of all routes from n s to n d . R ( t\t = t,) = { R ( t , ) , , R ( t,) 2 K R ( t,) , K R ( t,) c }. (see Figure.2)

Figure.2 A Typical Traditional Wireless Sensor Network

For most WSNs applications has some levels real time delay tolerant specifications constraints ( T_QoS ) which means the maximum delay time from end to end T_QoS is given. In a DTN WSNs, data are handled by “store and forward” approach, intermitted network connection phenomena may occur at any time.

Different from traditional route description above, a route in DTN can be denoted with R i ( t E [0, T q_oS ]) , and R , ( t e [0, T_QoS ]) = { n s , L , n_d } . where n_s is the source node, and n d is the destination node, and s ^ d h i (t E [0, T q_oS ]) denotes the total hops of the route.(see Figure.3)

E

H

F

Figure.3 A Typical DTN Wireless Sensor Network

By modeling and analysis the nodes behavior, we can get the delay time in each node in a route Ri (t E [0,TQoS]) , then we can deduce the total delay time from ns to nd Ti . To meet the requirement of within delay time of TQoS    for data transmitting, Ti < TqoS , then we can get the maximum total hops hmax(t E [0, TQos ]) in Ri(t E[0, TQos]) from ns to nd . h.^t E [0, IQS ]) is a key parameters in DTN WSNs topology.

In summary, the fundamentally science issues behind DTN topology control for given specific nodes collection in a specific geography space are:

• (1) . How to model and analysis the node behavior (for example, node in power saving state or service time of node) in a DTN WSNs, and get the total delay time T_i for data transmitting?

• (2) . For a specific T_QoS , how to find the maximum total hoPs ^h max ⁽ t ^{E [0, T}QoS ^]) in a route?

• (3) . How to control each node n_i ’s next hop nodes set N_i^c to get an optimistic WSN topology;

In this paper, instead of giving a specific DTN topology control algorithm, we mainly address these three key issues above.

• IV.    M ODELING ON N ODE BEHAVIOR

A. Queueing Model for WSNs Node

For a given specific WSNs, node can offer data collecting service, we denoted it with S _c . S _c is composited of two type of services, or S c = S n + S ^c,

S _n is called data service;

S ^c is called cache service . n

Data in each node may have different privilege levels to be transmitted. For example, if some data is beyond normal distribution region, it may imply some dangerous things happened, and the data should have high privilege to be transmitted. Besides, the user of Sn may be a common user (or other WSNs node) or a administrator, the administrator sends control packet to Sn regulate the work states of Sn , while the common user only request for the data from Sn [9,10].

So S _n service can be classified into different privilege levels, to make the problem simple, the users are classified into two classes, or administrators and common users.

Besides, to enhance the throughput of the system and save the battery energy ofSn，we also introduce a cache service system Sc to reduce unnecessary repeated n request from Sc . To analysis the performance of node behavior in DTN we build the following queueing mode

(See Figure.4)

Figure.4 Queue Model for the Framework

Queue.1 The first queue is forSc , Sc is only for WSNs nn cache data packet, WSNs cache system is usually a data search operation, and we use M/D/1/K for this queueing model. The total service request rate is Я , Sc messages come to Sc queue at the rate of Я, PA is probability of n             11

getting data from S^c . So we can arrive at Я 1 = A g p 1 . As for this queue is rather easy, we will not go any further Queue.2 This queue is for S _n . This queue is work for both WSNs control and data packet request, as for the service time of S _n is usually with general distribution and it may be in the state of energy saving (node service in vacations states), we use M/G/1/K non-preemptive priority with vacations for this queueing model. Note that the real service is hosted in a WSN node, while the buffer is hosted in S _n . All S _c messages are firstly sent to a job scheduling system ( JS ). JS will check the message type and the time stamp to determine which queue the request should be forward to process.

In this model, we assume service request message types are classified in to n priority classes. Messages of each priority class i ( i = 1,2, K n ) arrive according to a

Poisson process with rate X i and to be served by S^c_n with a general service time distribution of mean x i and second moment x_i ² . To make the problem simple, we assume there are two priority classes in our model, the first one is control message, which is usually the control message sent by the administrators or some urgent message request, it comes with the rate of X_c ; the second one is data message, it comes with the rate of X d . The arrival X_c and X d are assumed to be independent of each other and service process. All messages comes at the rate of X ₂ = X_c + X d . X_c is to be served by S _n with a general service time distribution of mean x_c and second moment X 2 . P_c is its traffic intensity or utilization factor. ^_c is the service rate . X_d is to be served by S _n with a general service time distribution of mean x_d and second moment x d . p d is its traffic intensity or utilization factor. ^ d is the service rate. Then we can deduce the relationship among these parameters above in the followings:

X = X 1 + X 2, X = XgP 1, X ₂ = X_c + X d

Pc = Xc gXc , Pd = Xd CXd , Pl = Л/Pl = Pc + Pd - X - X — ^ X^ x^ x=vgXc+ -fgXd, x2 = -gxgx2+ -d-gx2

X 2 X 2            X 2 X 2

Another import thing to be noted is S _n may be in energy saving state in a DTN WSNs. In this state S _n does not process any requests. Assume that V 1 , V ₂ , K are the residual of S _n ’s successive vacation time. The mean of vacation time V 1 , V 2 , K is V , and the second moment is V ²

R v

= lim

t ^ ” 2

For each M/G/1/K, given can the buffer size K_i [3]:

K i =

a

^^^^^e

m ( t )

Z V2

k = ¹_______

C m ( t )

Z vk

v i ²

² g vi

k = 1

block probability of P_k , we

a g b

2 g ln ( P i )

where i = c , d ,

a=- ln (PkK1- Pi+Pk gPi))+ln (Pi)

andS 2 is squared coefficient of variation of the service i process. Note that Ki can be hosted on Sn . The mean

residual service time R_s for all jobs in the queue [12] can be arrived:

n 2 n

Rs = ZPi ^ = 2ZXX i=1     ^    xi ^

So, the total residual service time ° [1] is i = Rv + Rs(2)

The waiting time of a job in class i is:

_______________i (3)

1 - Z Pk 11) 1 - zZ p .

k = 1      ) V

According the Little’s law, the average number of jobs in each class waiting queue is N_qⁱ , and

M i = ХЙУ =--------XlC°

Nq XigfV i    Z     i-1     \ Z      i\

| 1 - Z P k |c^ 1 - Z P k l

V     k=1    7 V     k=1

The total time that a job spent is T_i , and

B. Performance Analysis on Queue.2

Queue.2. is composed of two queues, one is for control (or urgent) message and the other one is for data message, both queues are M/G/1/K queueing system. Each node may be in power saving sate in DTN WSNs, the residual service time R_v in this state can be get by[1]:

Ti = Wi + Xi = -z------1----^-----i ----т + Xi (5

| 1 - Z P . 1 j1 - Z P k\ V k = 1      7 V k = 1      7

Figure.4 Residual Service Time for All Messages

K i , N q ⁱ , T i are very important initial parameters in node behavior in Fig.1. Let T_tⁱ denotes the maximum tolerant delay time, p_kⁱ denotes the blocking probability. To guarantee T_tⁱ and p_kⁱ constrained QoS, the following prerequisites must exist:

N i <  K &  T <  T (6) qt

Then we can determine the initial parameters in Fig.1, P i , X i , ^ i etc.. Moreover, for a given specific framework, we can give its performance evaluation by our model as well.

C. Numeral Results and Analysis

To analysis the results that we have deduced above, we give the following initial parameters in the framework: x, = 0.01 , ст² = 0.02 , x ² = ( x ,) + ст, ² ; x = 0.001 , d                     _d                     d         d          dc

ст² = 0.01 , x² = ( x ) + ст² ; V = 0.04 , ст² = 0.01 , c        ^{cc    c}            v

V = ( V ) ⁺ ст ^ ^ = 0.1 X 2 ,we get P k " P —Buffer Size

Fig.6 shows that with the increasing of p , W_c will also increase, but the wait time will be below than 1.4 second; while W_d will increase very fast, and the wait time will below 84 second. Given a specific k_i and T_tⁱ , we can roughly get the range of p i , for the service time ^ .usually is known, then we can regulate S c ’s rate X to get the QoS guaranteed service.

V . E ND TO E ND P ERFORMANCE F LOW ANALYSIS

In a DTN WSNs, data is stored and forwarded by nodes along a path from source to destination.

S1 F’ A B E

F REQ

S2 ^F’’

F

O-

Figure.8 Data Transmitting in A DTN WSNs

RRPL

D

Figure.5 p k - p -Buffer Size Relationship

According to the equation (2)(3)(4)(5), by increase the value of X ,we will also get increased traffic intensity of the system p ,the we can get the queue size and wait time of each message with different priority, see Figure.6 and Figure.7

Figure.6 Nc and Nд with p

Figure.7 Wc and W j with p

To guarantee bounded delay end to end with zero packet loss, we use Stop-and-GO queueing as deterministic bounds (See Fig.). Stop-and-GO queueing was prompted by Golestani, S.J [13].

The Stop-and-GO queueing rules in our model are stated as follows:

• (1) . Packet in incoming “Bundles” F ' and F '' are stored at node A, and cannot be forwarded until the beginning of the outgoing “Bundles” F following completion of “Bundles” F ' and F '' respectively.

• (2) . A node should not stay idle or in pore is any eligible “Bundles” in the queue.

The total delay D_p end-to-end, for any packet by Stop-and-GO queueing is bounded by[13]:

(m - 1)T + T < dp < (ggm+1)T + T (7)

Where, m is the hops of the route, g = 2 , T . in equation(5) is the total time that a job spent in a node, T is propagation delay which is determined by the transmitting technology that use in WSNs. For example, T k in a Zigbee WSNs is great then that in a Wi-Fi WSNs.

To meet a specific T_QoS , the up bound in equation (7)

must small than T_QoS ,i.e.

(g gm+1)T + Tk < tqos

Then we get the hops in the transmitting route is bounded by:

m <

T

TQoS

- T - T.

ggTi

The lower bound of m is denoted by I m I , and the

maximum total hops h _max ( t E [0, T q_oS ]) in a route must meet:

hmax (t E [0, TqoS ]) = Lm J =

T qoS -T k -T g g T i

Equation (9) mean for any route Ri from source node ns to nd ’ hiE [1, hmax (t E[0, TQoS ])L is:

Etx (k, d ) = Etx - elec (k) + Etx - amp (k, d ) k gEelec + k £fx gd 2, d < d0 = ^

, ^k gE elec ^{+ k} g^ mp gd 4 , ^d ^ ^d 0

Where, E_elec is the electronics energy, it depends on factors such as the digital coding, modulation, filtering, and spreading of the signal, as for the amplifier energy, ^£ fx gd 2 or ^£_mp gd 4 , it depends on the distance to the receiver and the acceptable bit-error rate.

For the data receiving nodes in WSN, to receive this message, the energy consumption model is:

Maximum Hops

Erx (k) = Erx - elec (k) = kEec

л h  (t e [0, Tn J) = m I = max ’ QoS L J

T qoS - T - T g g T i

0    10    20    30    40    50    60    70    80    90   100   110

Ti ( time of unit)

Figure.9 Data Transmitting in A DTN WSNs

To evaluate equation (9), we give the following initial parameters T q_oS = 1000 time unit, T k = 1 time unit; we get the relationship of h _max against T_i in Figure. Fig shows that with T_i increasing h _max drops rapidly.

• B.    The Determination of Optimistic Hops h ^*

From a global view, each node’s neighbor nodes should be determined by hops from source node to sink node and the distance of each hop.