Abouzeid, “Rate-distortion bounds on location-based routing protocol overheads in mobile a

Rate-Distortion Bounds on Location-Based Routing Protocol Overheads

in Mobile Ad Hoc Networks

Nabhendra Bisnik and Alhussein Abouzeid

Department of Electrical Computers and System Engineering

Rensselaer Polytechnic Institute

Troy,NY12180

bisnin@https://www.wendangku.net/doc/2c16292014.html,,abouzeid@https://www.wendangku.net/doc/2c16292014.html,

Abstract—We present an information theoretic analysis of the minimum routing overhead incurred for reliable routing of packets using location-based routing.We formulate the mini-mum routing overhead problem as a rate-distortion problem and derive a lower bound on the minimum routing overhead incurred.We also characterize the de?cit in transport capacity caused by the routing overheads.It is observed that for high mobility and packet arrival rates,the routing overheads may consume the entire capacity of a network.

I.I NTRODUCTION

The time varying topology of mobile networks makes ef?cient routing of packets a challenging problem.Under high node mobility,existing routing protocols for either incur a large overhead in order to cope with the mobility or yield low delivery ratio.Understanding the lower bounds on the amount of protocol overhead incurred for reliable routing of packets is important for development of ef?cient routing pro-tocols,and for understanding the effective network capacity available to the network users.

In this paper we present an analytical information-theoretic framework for characterizing the lower limit on over-head incurred by geographical routing protocols in a one-dimensional mobile wireless.In geographic routing each node maintains its location information at one or more location servers(e.g.see[3]).When a source wants to forward a packet to a destination,it queries an appropriate location server for location of the destination.The location server replies to the source node with the available location information.Thereafter,the source and intermediate nodes forward the packet according to the location of the des-tination.The mobility model considered in this paper is Brownian motion with varianceσ2.

We divide the geographic routing overheads into two cate-gories:(i)Location update overhead:The overhead incurred in updating the location servers such that the location errors in the reply to location queries is less than ,and(ii)Beacon overhead:The overhead incurred in beacon transmission such that the probability that a node has consistent neigh-borhood information when it needs to forward a packet is greater than1?δ.We formulate the problems of?nding the minimum values of the above-mentioned overheads as rate distortion problems[2].For location update overheads,the distortion measure used is squared error in the location stored at the location servers(squared error distortion error).For beacon overheads,the distortion measure is the probability that a perceived neighbor is not a actual neighbor(Hamming distortion measure).Using a rate-distortion formulation,we present lower bounds on the minimum geographic routing overhead incurred in terms of node mobility,packet arrival process,and reliability criteria andδ.We also discuss the residual capacity of mobile ad hoc networks after taking into account the routing overheads.

II.L OCATION U PDATE O VERHEAD

Let X i(t)and?X i(t)denote the actual location of node i and the location of the node available at the location server at time t.Let T i(j)denote the time at which j th packet destined to node i arrives in the network and let f S(t)denote the pdf of the packet inter-arrival time(T i(j)?T i(j?1)). It is required that the expected deviation of?X i(t)from X i(t)should be less than 2.Let P N denote the family of probability density functions for which

D iN=

1

N

N

j=1E[D i(T j]≤ (1)

where D i(t)=|X i(t)??X i(t)|.

De?nition1:R N( 2)is de?ned as the minimum rate (in terms of bits per packet)at which a destination must transmit its location information to its location server such that D iN≤ 2.According to[2],R N( 2)is given by

R N( 2)=min

P N∈P N( 2)

1

N

I P

N

(X N i;?X N i)(2)

where I P

N

(X N i;?X N i)is the mutual information between X N i and?X N i,X N i={X i(T1),X i(T2),...,X i(T N)},and ?X N

i

={?X i(T1),?X i(T2),...,?X i(T N)}.

The minimum rate at which a destination must update its location information such that a large fraction of packets are delivered,represented by R( 2),is given by

R( 2)=lim

N→∞

min R N( 2)(3) Theorem1:In order to ensure high delivery ratio,the lower bound on the location update rate(in bits per packet)

is given by

R( 2)≥h(X i(T1))?1

2

log2πe 2(4)

where h(X i(T1))is the differential entropy of the location of destination i at the time when the?rst packet destined to it arrives in the network.

Detailed proof of Theorem1is provided in[1].Theorem1 implies that the minimum update rate largely depends on h(X i(T1),which in turn depends on two factors:(i)the mobility pattern of the destination node and(ii)the packet inter-arrival time process.Let f X(x)denote the pdf of X i(T1)(without loss of generality,X i(T0)=0).For Brownian motion with varianceσ2and packet inter-arrival time distribution f S(t),f X(x)is given by

f X(x)= ∞τ=01√2πσ2τe?x22σ2τf S(τ)dτ(5) and R( 2)is given by

R( 2)≥h(f X(x))?1

2

log 2πe 2 bits/pkt(6)

where h(f X(x))=? ∞x=?∞f X(x)log(f X(x))dx The lower bound on the minimum overhead incurred by location update information in terms of bits/second,denoted by U( 2),is given by

U( 2)≥

1

E[S] h(f X(x))?12log 2πe 2

bits/sec

(7)

III.B EACON O VERHEAD

In communication networks,exchange of beacon messages is used for maintaining consistent neighborhood information. Let Z ij(t)be an indicator random variable which is equal to1if j belongs to the neighborhood of i at time t and equal to0otherwise.Let?Z ij(t)be an indicator random variable which is equal to1if i perceives j as its neighbor at time t and0otherwise.Letτi(k)denote the time at which node i forwards k th packet and fτ(t)denote the pdf ofτi(k)?τi(k?1).Vectors Z N ij and?Z N ij are de-?ned as Z N ij {Z ij(τi(1)),Z ij(τi(2)),...,Z ij(τi(N))}and ?Z N

ij

{?Z ij(τi(1)),?Z ij(τi(2)),...,?Z ij(τi(N))}.Similar to

the update rate analysis,let P(b)

N (δ)denote the family of

joint probability distribution function of Z N ij and?Z N ij such that P[Z ij(τi(k))??Z ij(τi(k))=0]≥1?δ?1≤k≤N. Thus the minimum beacon rate,R(b)(δ),may be expressed in the following manner

R(b)(δ)=lim

N→∞

inf R(b)N(δ)(8) where

R(b)N(δ)=inf

P N∈P(b)

N (δ)

1

N

I P

N

(Z N ij;?Z N ij)(9)

and I P

N

(Z N ij;?Z N ij)is the mutual information between Z N ij and?Z N ij.

Theorem2:The lower bound of the minimum beacon transmission rate of a node such that consistent neighborhood information is maintained with probability at least1?δis satis?ed is given

R(b)(δ)≥H2(p(l ))?H3…δ2,1?δ,δ2?beacons/msg(10) where

H2(x)=?x log(x)?(1?x)log(1?x) H3(x/2,1?x,x/2)=?x log(x/2)?(1?x)log(1?x)

l arg min

?r≤l≤r|

P[Z ij(τi(1))=1|X j(0)=l]?0.5|

and p(l )=P[Z ij(τi(1))=1||X j(0)?X i(0)|=l ]. Detailed proof of the above theorem is presented in[1]. The minimum overhead in terms of bits/second,denoted by U(b)(δ),is given by

U(b)(δ)≥

B

E[τ] H(p(l ))?H

δ2,1?δ,δ2 bits/sec

(11) where E[τ]is the expected packet inter-arrival time and B is the size of beacon packet in bits.

IV.C APACITY D EFICIT

Let C(n)denote the transport capacity of a wireless network with n nodes.Letηdenote the average distance traveled by location update information from a node to its location server.Note thatηdepends on the location service scheme being used and the distribution of nodes in the network.Thus the de?cit in transport capacity due to location update information is greater than or equal to nηU( 2)bit?meters/sec.The beacon update information travels a distance of r meters.Thus the capacity de?cit due to beacons is greater than or equal to nrU(b)(δ).Let C (n)denote the residual transport capacity-the capacity of the network available for transmitting actual user data after taking into account the routing overheads.C (n)is given by C (n)≤C(n)?n ηU( 2)?rU(b)(δ) bit?m/sec(12) An implication of(12)is that if C(n)=o(n)then for large enough n,the complete network capacity would be consumed by the routing overheads,thus not allowing any useful information to be transported through the network. The minimum value of n for which C (n)equals0depends on the packet arrival rate and mobility of the nodes.

V.C ONCLUSION

In this paper we presented an information theoretic frame-work for analyzing the minimum routing overhead incurred by geographic routing in one dimensional mobile ad hoc net-works.The extension of the formulation to two-dimensional networks and other routing paradigms will be the direction of future work.

R EFERENCES

[1]N.Bisnik and A.Abouzeid.Capacity de?cit in mobile wireless ad hoc networks due to routing overheads.Technical

Report,Department of ECSE,RPI,Troy,NY.Available at https://www.wendangku.net/doc/2c16292014.html,/homepages/ abouzeid/deficit.pdf.

[2]T.M.Cover and J.A.Thomas.Elements of Information Theory.John Wiley&sons,1991.

[3] B.Karp and H.T.Kung.GPSR:greedy perimeter stateless routing for wireless networks.In MOBICOM,pages

243–254,2000.