Link mobility tracking and its application to mobile ad hoc networks

• US 20070153737A1
• Filed: 12/30/2005
• Published: 07/05/2007
• Est. Priority Date: 12/30/2005
• Status: Active Grant

• Current Assignee: George Mason Intellectual Properties, Inc., Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Choi, Young-Gon, Singh, Shubhranshu, Roh, Yong-Sung, Mark, Brian, Suri, Vamit
• Granted Patent: US 8,335,207 B2
• Time in Patent Office: Days
• US Class Current: 370/331
• CPC Class Codes: H04W 40/14 based on stability
• CPC Class Codes: H04W 40/18 based on predicted events
• CPC Class Codes: H04W 40/20 based on geographic position or location

Abstract

Embodiments of the present invention provide a method for tracking link mobility between two mobile nodes. Each node estimates a link mobility state of a link between itself and each of its neighbor nodes, accumulates successively the link mobility states, estimates link mobility parameters using the successively estimated link mobility states, and predicts a link availability probability using the link mobility parameters. The link mobility tracking can be applied to various routing protocols so as to implement mobility aware routing which enhance the routing performance.

Claims

1. A method for tracking link mobility between two mobile nodes, comprising:

estimating, at each node, a link mobility state of the link between a pair of nodes;

accumulating successively the link mobility states;

estimating link mobility parameters using the successively estimated link mobility states;

predicting a link availability probability using the link mobility parameters.

2. The method of claim 1, wherein the link mobility state is estimated with observation data received form each of neighbor nodes.

3. The method of claim 2, wherein the observation data includes a received signal strength indicator (RSSI).

4. The method of claim 2, wherein the observation data includes Time-of-Arrival (TOA).

5. The method of claim 1, wherein the link mobility state is computed by an equation:

s_n+1=sgn As_n+W_n1·

(As_n+w_n), s₁ denotes a first component of a vector s,

$A=\left[\begin{array}{ccc}1& T& T^2/2\\ 0& 1& T\\ 0& 0& \mathrm{\alpha <br><br>}\end{array}\right],$

T denotes a sampling interval between s_n and s_n+1, α

is a parameter of a mobility model, w_n+[w_n,1,w_n,2,w_n,3]′

is a 3×

1 discrete-time zero mean, white Gaussian process with autocorrelation function R_w(k)=δ

_kQ where δ

₀₌1 and δ

_k=0 when k≠

0, and ′

is the matrix transpose operator.

6. The method of claim 5, wherein the link mobility parameters are A and Q.

7. The method of claim 6, wherein the link availability probability is computed by an equation:

$\begin{array}{c}{p}_{n+1|n}<br><br>\stackrel{\mathrm{△<br><br>}}{=}<br><br><br><br>P<br><br>\left[d_{n+1|n}\le <br><br>d_{\mathrm{th}}\right]\\ =<br><br>\frac{1}{\sqrt{2<br><br>{\mathrm{\pi <br><br>\sigma <br><br>}}_{n+1|n}}}<br><br>{\int <br><br>}_0^{d_{\mathrm{th}}}<br><br>{\mathrm{e<br><br>}}^{\frac{-\left(x-{\hat{d}}_{n+1|n}\right)}{2<br><br>{\mathrm{\sigma <br><br>}}_{n+1|n}^2}}<br><br>d<br><br>x\\ =<br><br>Q<br><br>\left(\frac{d_{\mathrm{th}}-{\hat{d}}_{n+1|n}}{{\mathrm{\sigma <br><br>}}_{n+1|n}}\right)-Q<br><br>\left(\frac{-{\hat{d}}_{n+1|n}}{{\mathrm{\sigma <br><br>}}_{n+1|n}}\right)\end{array}$

where d_th is transmission/reception range of nodes,

$Q<br><br>\left(x\right)<br><br>\stackrel{\mathrm{△<br><br>}}{=}<br><br>\frac{1}{\sqrt{2<br><br>\mathrm{\pi <br><br>}}}<br><br>{\int <br><br>}_x^{\mathrm{\infty <br><br>}}<br><br>{\mathrm{e<br><br>}}^{-y^2/2}<br><br>d<br><br>y$

denotes the standard Q-function, d_n+1|n and σ

_n+1|n are predicted link distance and standard deviation at time n+1 with observations up to time n.

8. A method for deciding a route from a source node to a destination node, directly or via at least one intermediate node, on the basis of stabilities of different paths between the source and destination nodes in a mobile ad hoc network, comprising:

calculating a stability of each path using link stabilities between neighbor nodes on the path;

comparing the paths stabilities of different routes; and

selecting the path having a highest stability, thus using the route with maximum lifetime.

9. The method of claim 8, wherein the step of selecting the path includes:

determining whether or not there are more than one node having the highest stability;

comparing hop counts of the paths having the highest stability; and

choosing the path having a lowest hop count as the route.

10. The method of claim 8, wherein the path stability is determined by a stability of a weakest one among the links of the same path.

11. The method of claim 8, wherein the step of calculating the stability of each path includes:

calculating stabilities of links on each path; and

selecting a stability of a weakest link among the links as the path stability.

12. The method of claim 11, wherein the step of calculating stabilities of the links on each path includes:

estimating a link mobility state of the link between the neighbor nodes;

accumulating successively the link mobility states;

estimating link mobility parameters using successively estimated link mobility states;

predicting a link availability probability using the link mobility parameters; and

obtaining the link stability from the link availability probability.

13. The method of claim 12, wherein the link mobility state is estimated with observation data received from each of neighbor nodes.

14. The method of claim 13, wherein the observation data includes a received signal strength indicator (RSSI).

15. The method of claim 13, wherein the observation data includes Time-of-Arrival (TOA).

16. The method of claim 12, wherein the link mobility state is computed by an equation:

s_n+1=sgnAs_n+w_n1·

(As_n+w_n), s₁ denotes a first component of a vector s,

$A=\left[\begin{array}{ccc}1& T& T^2/2\\ 0& 1& T\\ 0& 0& \mathrm{\alpha <br><br>}\end{array}\right],$

T denotes a sampling interval between s_n and s_n+1, α

is a parameter of a mobility model, w_n=[w_n,1,w_n,2,w_n,3]′

is a 3×

1 discrete-time zero mean, white Gaussian process with autocorrelation function R_w(k)=δ

_kQ where δ

₀=1 and δ

_k=0 when k≠

0, and ′

is the matrix transpose operator.

17. The method of claim 16, wherein the link mobility parameters are A and Q.

18. The method of claim 17, wherein the link availability probability is computed by an equation:

$\begin{array}{c}{p}_{n+1|n}<br><br>\stackrel{\mathrm{\Delta <br><br>}}{=}<br><br><br><br>P<br><br>\left[d_{n+1|n}\le <br><br>d_{\mathrm{th}}\right]\\ =<br><br>\frac{1}{\sqrt{2<br><br>{\mathrm{\pi <br><br>\sigma <br><br>}}_{n+1|n}}}<br><br>{\int <br><br>}_0^{d_{\mathrm{th}}}<br><br>{\mathrm{e<br><br>}}^{\frac{-\left(x-{\hat{d}}_{n+1|n}\right)}{2<br><br>{\mathrm{\sigma <br><br>}}_{n+1|n}^2}}<br><br>d<br><br>x\\ =<br><br>Q<br><br>\left(\frac{d_{\mathrm{th}}-{\hat{d}}_{n+1|n}}{{\mathrm{\sigma <br><br>}}_{n+1|n}}\right)-Q<br><br>\left(\frac{-{\hat{d}}_{n+1|n}}{{\mathrm{\sigma <br><br>}}_{n+1|n}}\right)\end{array}$

where d_th is transmission/reception range of nodes,

$Q<br><br>\left(x\right)<br><br>\stackrel{\mathrm{\Delta <br><br>}}{=}<br><br>\frac{1}{\sqrt{2<br><br>\mathrm{\pi <br><br>}}}<br><br>{\int <br><br>}_x^{\mathrm{\infty <br><br>}}<br><br>{\mathrm{e<br><br>}}^{-y^2/2}<br><br>d<br><br>y$

 

denotes the standard Q-function, d_n+1|n and σ

_n+1|n are predicted link distance and standard deviation at time n+1 with observations up to time n.