Method for broadcasting alert message in mobile multi-hop networks using inferred distance prioritization

• US 8,155,044 B2
• Filed: 01/21/2009
• Issued: 04/10/2012
• Est. Priority Date: 01/21/2009
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Yim, Raymond, Guo, Jianlin, Orlik, Philip V.
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): Cehic, Kenan
• Application Number:
  US12/357,157
• Publication Number:
  US 20100182982A1
• Time in Patent Office: 1,175 Days
• Field of Search: 370310-350
• US Class Current: 370/312
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 64/006 with additional information processing, e.g. for direction or speed determination
• CPC Class Codes: H04W 72/569 of the traffic information
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

A method and system broadcasts an alert packet in a wireless multi-hop network of nodes. An event is sensed in a source node of the network, and an alert packet is broadcast in response to sensing the event. The alert packet is received in a set of candidate nodes within a broadcast range of the source node. Each candidate node infers a distance between the candidate node and the source node based on a receive power of the received alert packet, and determines a priority for rebroadcasting the alert packet, wherein the priority is based on the distance to minimizing a probability of collisions while rebroadcasting the alert packet and extend a range of the rebroadcasting.

Claims

1. A method for broadcasting an alert packet in a wireless multi-hop network of nodes, comprising:

sensing an event in a source node of the network;

broadcasting an alert packet in response to sensing the event;

receiving the alert packet in a set of candidate nodes within a broadcast range of the source node;

inferring, in each candidate node, a distance between the candidate node and the source node based on a receive power of the received alert packet;

determining, in each candidate node, a priority for rebroadcasting the alert packet, wherein the priority is based on the distance to minimizing a probability of collisions while rebroadcasting the alert packet and extend a range of the rebroadcasting; and

determining back-off times for rebroadcasting packets for the set of the candidate nodes based on the priority of each candidate node and a back-off probability distribution, wherein the back-off probability distribution is a non-uniform distribution among the nodes with the same priority, such that a cumulative probability for the nodes increases with the distance from the source node.

2. The method of claim 1, wherein the distance is determined by a global positioning system or any other mechanisms at the node.

3. The method of claim 1, wherein the distance is dependent of a transmit power of the broadcasting.

4. The method of claim 1, wherein the distance is independent of a transmit power of the broadcasting.

5. The method of claim 1, wherein the priority is used to determine a back-off time before the rebroadcasting, and wherein a high priority has a short back-off time, and a low priority has a long back-off time.

6. The method of claim 5, further comprising:

sensing, in each candidate node, whether a channel for the rebroadcasting is free before the back-off time expires; and

rebroadcasting only if the channel is free.

7. The method of claim 1, wherein the priority is selected from a non-uniform probability distribution function, which assigns a higher priority to the candidate nodes farther away from the source node, while at the same time minimizes the probability of collisions.

8. The method of claim 1, wherein the alert packet s rebroadcast only if the alert packet has not been previously received.

9. The method of claim 1, wherein the alert packet includes an identification of the source node, a sequence number, and content related to the event.

10. The method of claim 9, wherein the alert packet further includes a location of a last node rebroadcasting the alert packet.

11. The method of claim 5, further comprising:

decrementing the back-off time until a predetermined time expires;

sensing a channel for the rebroadcasting while decrementing; and

suspending the decrementing while other nodes are broadcasting.

12. The method of claim 11, further comprising:

resuming the decrementing after the channel becomes free.

13. The method of claim 1, wherein the priority is independent on a maximum distance of the broadcasting.

14. The method of claim 11, further comprising:

discarding the alert packet while suspending.

15. The method of claim 9, wherein the identification of source node and sequence number is stored by each candidate node.

16. The method of claim 10, wherein the identification expires after a predetermined time interval.

17. The method of claim 5, wherein the alert packet includes an identification of the source node, a sequence number, and content related to the event, and further comprising:

decrementing the back-off time until a predetermined time expires;

sensing a channel for the rebroadcasting while decrementing;

suspending the decrementing while other nodes are broadcasting; and

discarding the alert packet based on the identity and the sequence number while suspending.

18. The method of claim 17, further comprising:

decoding the received alert packet while suspending.

20. The method of claim 1, wherein the determining back-off times comprises:

determining a probability matrix satisfying a criteria

19. A system for broadcasting an alert packet in a wireless multi-hop network of nodes, comprising:

a source node configured to sense an event and to broadcast an alert packet in response to sensing the event; and

a set of candidate nodes, wherein each candidate node is configured to receive the alert packet when within a broadcast range of the source node, and

wherein each candidate node further comprises;

means for inferring a distance between the candidate node and the source node based on a receive power of the received alert packet; and

means for determining a priority for rebroadcasting the alert packet, wherein the priority is based on the distance to minimizing a probability of collisions while rebroadcasting the alert packet and extend a range of the rebroadcasting; and

means for determining back-off times for rebroadcasting packets for the set of the candidate nodes based on the priority of each candidate node and a back-off probability distribution, wherein the back-off probability distribution is a non-uniform distribution among the nodes with the same priority, such that a cumulative probability for the nodes increases with the distance from the source node.