Mobile ad-hoc network

• US 20060176829A1
• Filed: 02/10/2006
• Published: 08/10/2006
• Est. Priority Date: 02/10/2005
• Status: Abandoned Application

• Current Assignee: University of Edinburgh
• Original Assignee: University of Edinburgh
• Inventors: Laurenson, David Irvine, Tan, Yow-Yiong Edwin, McLaughlin, Stephen
• Application Number:
  US11/351,777
• Publication Number:
  US 20060176829A1
• Time in Patent Office: Days
• US Class Current: 370/252
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method of assessing a communication route comprising a plurality of links between nodes in a mobile ad-hoc network comprises calculating the two-hop residual bandwidth of each node I of the route as $B_I\left(t\right)=B-\frac{\sum _{J\in N\left(I\right)}B\left(J\right)}{\varphi }$where B is the raw channel bandwidth, the summation is the overall consumed bandwidth from node I'"'"'s two-hop neighborhood nodes, JεN(I) and φ is a factor to account for protocol overhead, which may include handshaking, packet collision, re-transmission and/or back-off scheme traffic. An estimated transmission time for each of a plurality of links between said nodes may be calculated taking said two-hop residual bandwidth into account. For each possible route, a route efficiency function is determined at least by summing the estimated transmission times for all the links in the route, and the route in which the value of the route efficiency function is smallest is selected.

Claims

1. A method of assessing a communication route comprising a plurality of links between nodes in a mobile ad-hoc network, the method comprising calculating the two-hop residual bandwidth of each node I of the route as

$B_I$

( t ) = B - ∑

J ∈

N ⁡

( I ) ⁢

B ⁡

( J ) ϕ

where B is the raw channel bandwidth, the summation is the overall consumed bandwidth from node I'"'"'s two-hop neighborhood nodes, Jε

N(I) and φ

is a factor to account for protocol overhead.

2. A method according to claim 1, wherein said protocol overhead includes at least one of handshaking, packet collision, re-transmission or back-off scheme traffic.

3. A method according to claim 1, comprising the further steps of:

a. calculating a function giving an estimated transmission time for each of a plurality of links between said nodes taking said two-hop residual bandwidth into account,

b. for each possible route, determining a route efficiency function at least by summing the estimated transmission times for all the links in the route, and

c. selecting the route in which the value of the route efficiency function is smallest.

4. A method according to claim 3, wherein step (a) comprises estimating the transmission time for a packet of given size on each of said links.

5. A method according to claim 4, wherein the transmission time RBEI for said packet on a link I is calculated as:

${\mathrm{RBE}}_i=\mathrm{PSP}·<br><br>\frac{1}{B_I<br><br>\left(t\right)}$

where PSP is the Packet Success Probability, L is the packet size and B_I(t) is the two-hop residual bandwidth.

6. A method according to claim 3, wherein step (b) comprises determining the maximum of the transmission times of all possible channels along the route and the route efficiency function also depends on said maximum of the transmission times.

7. A method according to claim 6, wherein the route efficiency function is weighted between the estimated transmission times for all the links in the route and said maximum of the transmission times of all possible channels along the route.

8. A method according to claim 1, the method comprising the further steps of:

p. determining a traffic capacity for each of said nodes, depending on said two-hop residual bandwidth;

q. for each possible route, determining a route capacity function, namely the lowest traffic capacity of any node of the route, and

r. selecting the route with the highest route capacity function.

9. A method according to claim 8, wherein in step (p) the traffic capacity of a node I is determined as

${\mathrm{RBC}}_l=c$

B I ⁡

( t ) ⁢

min ⁡

( m , n ) n ⁢

 

⁢

log 3 ⁢

n

where, c(>

0) is a constant;

B_I(t) is the two-hop residual bandwidth and m and n are the number of mobile and static nodes, respectively.

10. A method according to claim 1, comprising the further steps of:

w. determining a traffic capacity for each of said nodes, depending on said two-hop residual bandwidth;

x. for each possible route, determining a route capacity function, namely the lowest traffic capacity of any node of the route,

y. if a set of routes exists for which the route capacity function of each route in the set is at least equal to a minimum value required by the data to be transmitted, selecting from said set the route with the smallest route efficiency function, said route efficiency function being calculated at least by summing estimated transmission times for all the links in the route; and

z. if the route capacity function of all possible routes is less than said minimum value, selecting the route with the highest route capacity function.

11. A method according claim 1, comprising a step of discovering possible routes by checking that the minimum bandwidth required for the data to be communicated is less than the two-hop residual bandwidth of each node in a candidate route.

12. A method according to claim 11, wherein said step of discovering possible routes includes checking that said minimum bandwidth required is less than the lowest value to which the two-hop residual bandwidth can fall when next updated.

13. A method according to claim 12, wherein said lowest value is calculated as

B_I(t)−

Δ

B_I(t)
where
Δ

B_I^new(t)=[α

·

Δ

B_I^old(t)]+[(1−

α

)·

β

·

|B_I^new(t)−

B_I^old(t)|]

α

(<

1) and β

(>

1) are adjustable parameters s;

Δ

B_I^old(t) and Δ

B_I^new(t) are the values of Δ

B_I(t) before and after updating, respectively and B_I^old(t) and B_I^new(t) are the values of B_I(t) before and after updating, respectively.

14. A method according to claim 12, wherein, if said minimum bandwidth required is greater than said lowest value to which said two-hop residual bandwidth can fall, a candidate route through the node is rejected.

15. A method according to claim 12, wherein, if said minimum bandwidth required lies between said lowest value to which said two-hop residual bandwidth can fall and the highest value to which said two-hop residual bandwidth can rise when next updated, said minimum bandwidth is updated using the current two-hop residual bandwidth of the node.

16. A method according to claim 15, wherein if said minimum bandwidth required is greater than said highest value to which said two-hop residual bandwidth can rise, a candidate route through said node is rejected.

17. A method according to claim 15, wherein said highest value is calculated as

B_I(t)+Δ

B_I(t)
where
Δ

B_I^new(t)=[α

·

Δ

B_I^old(t)]+[(1−

α

)·

β

·

|B_I^new(t)−

B_I^old(t)|]

α

(<

1) and β

(>

1) are adjustable parameters;

Δ

B_I^old(t) and Δ

B_I^new(t) are the values of Δ

B_I(t) before and after updating, respectively and B_I^old(t) and B_I^new(t) are the values of B_I(t) before and after updating, respectively.

18. A transceiver for use in a mobile-ad hoc network, adapted to perform the method according to claim 1.

19. A transceiver for use in a mobile-ad hoc network, adapted to perform the method according to claim 3.

20. A transceiver for use in a mobile-ad hoc network, adapted to perform the method according to claim 8.

21. A transceiver for use in a mobile-ad hoc network, adapted to perform the method according to claim 10.