Multi-criteria optimization for relaying in multi-hop wireless ad hoc and sensor networks

• US 7,872,977 B2
• Filed: 06/04/2008
• Issued: 01/18/2011
• Est. Priority Date: 06/04/2007
• Status: Expired due to Fees

• Current Assignee: New Jersey Institute of Technology
• Original Assignee: New Jersey Institute of Technology
• Inventors: De, Swades, Egoh, Komlan
• Primary Examiner(s): Ferris; Derrick W
• Assistant Examiner(s): YEUNG, MANG HANG
• Application Number:
  US12/132,860
• Publication Number:
  US 20090016224A1
• Time in Patent Office: 958 Days
• Field of Search: 370/238
• 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, at a node, a first criterion for analyzing receiver-side relay election;

obtaining, at the node, a second criterion for analyzing receiver-side relay election;

determining a tradeoff parameter;

weighting the first criterion with a first weighting parameter and the second criterion with a second weighting parameter, wherein a ratio of the first weighting parameter to the second weighting parameter comprises the tradeoff parameter;

aggregating the weighted first criterion and the weighted second criterion using an aggregation formula to obtain a single virtual criterion; and

ranking candidate relay nodes 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, with a processor of a transmission optimization system, 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;

optimizing, with the processor of the transmission optimization system, 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; and

resolving, with the processor of the transmission optimization system, contention among contending potential relays to elect a most suitable candidate as a next hop relay, wherein resolving contention among contending potential relays comprises determining a response time delay, X_i, based on;

X_i=g_α

(d_i)=a(α

)d_i^α

+b(α

)

where α

is the shape parameter and d_i is forward progress.

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

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

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

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

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

a processor configured to;

determine a tradeoff parameter;

weight a first criterion with a first weighting parameter and a second criterion with a second weighting parameter, wherein a ratio of the first weighting parameter to the second weighting parameter comprises the tradeoff parameter;

aggregate the first weighted criterion and the second weighted criterion using an aggregation formula;

obtain a single virtual criterion with the aggregation formula; and

rank candidate relay nodes based on the single virtual criterion.

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

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

14. 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;

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; and

resolve contention among contending potential relays to elect a most suitable candidate as a next hop relay, wherein resolving contention among contending potential relays comprises determining a response time delay, X_i, based on;

X_i=g_α

(d_i)=a(α

)d_i^α

b+b(α

)

where α

is the shape parameter and d_i is forward progress.

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

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

17. The system of claim 14, wherein the processor is further configured to resolve contention among the contending potential relays by using a distance dependent time back off procedure.

18. The system of claim 14, wherein the processor is further configured to resolve contention among the contending potential relays by using a random time back off procedure.