MULTI-CRITERIA OPTIMIZATION FOR RELAYING IN MULTI-HOP WIRELESS AD HOC AND SENSOR NETWORKS

• US 20090016224A1
• Filed: 06/04/2008
• Published: 01/15/2009
• Est. Priority Date: 06/04/2007
• Status: Active Grant

• Current Assignee: New Jersey Institute of Technology
• Original Assignee: New Jersey Institute of Technology
• Inventors: De, Swades, Egoh, Komlan
• Granted Patent: US 7,872,977 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A generalized multi-parameter mapping function aggregates decision criteria into a single virtual criterion to rank the potential relay candidates. Optimal rules for next hop relay as applicable to both transmitter-side selection and receiver-side election based forwarding schemes are also provided. Examples of network performance based on two optimization criteria include one-hop progress (greediness) and packet success rate (link quality). A suitable mapping function trades off the greediness for link quality. Simulation information is provided that indicates that the implementation according to the mapping function outperforms the reported transmitter-side link-aware forwarding schemes.

Claims

1. A method for relaying in multi-criteria receiver-side relay election wireless networks, said method comprising:

obtaining a first criterion for analyzing receiver-side relay election;

obtaining a second criterion for analyzing receiver-side relay election;

optimizing a combination of the first criterion and the second criterion to form an aggregation formula;

aggregating information from the first criterion and information from the second criterion based on the aggregation formula, said aggregating that obtains a single virtual criterion; and

ranking relay candidates based on the single virtual criterion.

2. The method of claim 1, wherein the first criterion is one-hop progress.

3. The method of claim 1, wherein the first criterion is packet success rate.

4. The method of claim 1, wherein the second criterion is one-hop progress.

5. The method of claim 1, wherein the second criterion is packet success rate.

6. A method for optimizing a transmission of a wireless packet in a wireless network, said method comprising:

using a mapping function to determine a shape parameter that can be used to minimize the duration of an election between nodes in the wireless network and to reduce the probability of collision between contending potential relays; and

optimizing the shape parameter to minimize the duration of an election between nodes in the wireless network and to reduce the probability of collision between contending potential relays.

7. The method of claim 6, further comprising resolving contention among contending potential relays to elect a most suitable candidate as a next hop relay.

8. The method of claim 7, wherein resolving contention among contending potential relays comprises resolving by a distance dependent time back off procedure.

9. The method of claim 7, wherein resolving contention among contending potential relays comprises resolving by a random time back off procedure.

10. The method claim 7, wherein resolving contention among contending potential relays comprises determining a response time delay, X_i, based on:

X_i=g_a(d_i)=a(a)d_i^a+b(a)

where α

is the shape parameter and d_i is forward progress.

11. The method of claim 6, further comprising optimizing the shape parameter for a single criterion approach to relaying packets in a wireless network.

12. The method of claim 6, further comprising optimizing the shape parameter for a multi-criteria approach to relaying packets in a wireless network.

13. A system for multi-criteria receiver-side relay elections in wireless networks, the system comprising:

a processor configured to;

form an aggregation formula based on a combination of a first criterion and a second criterion;

obtain a single virtual criterion by aggregating information from the first criterion and information from the second criterion based on the aggregation formula; and

rank relay candidates based on the single virtual criterion.

14. The system of claim 13, wherein the first criterion is one-hop progress and the second criterion is packet success rate.

15. The system of claim 13, wherein the processor is further configured to elect a next hop relay based on the relay candidate rank.

16. A system that optimizes a transmission of a wireless packet in a wireless network, the system comprising:

a processor configured to;

determine a shape parameter for minimizing duration of an election between nodes in the wireless network and reducing probability of collision between potential relays; and

optimize the shape parameter to minimize duration of an election between nodes in the wireless network and to reduce probability of collision between contending potential relays.

17. The system of claim 16, wherein the processor is further configured to optimize the shape parameter for a single criterion approach to relaying packets.

18. The system of claim 16, wherein the processor is further configured to optimize the shape parameter for a multi-criteria approach to relaying packets.

19. The system of claim 16, wherein the processor is further configured to resolve contention among contending potential relays to elect a most suitable candidate as a next hop relay by a distance dependent time back off procedure.

20. The system of claim 16, wherein the processor is further configured to resolve contention among contending potential relays to elect a most suitable candidate as a next hop relay by a random time back off procedure.