Processing broadcast data in a mobile ad-hoc network

• US 20050078678A1
• Filed: 10/12/2004
• Published: 04/14/2005
• Est. Priority Date: 10/13/2003
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kim, Byoung-Chul, Park, Yong-Seok, Choe, Byung-Gu
• Granted Patent: US 7,269,147 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Processing broadcast data in a mobile Ad-hoc network includes: determining if all of the broadcast packets have been received using a Latest Broadcast Count Number (NBC) stored in a neighbor table within a buffer of a pertinent node and Broadcast Count Number (BC) contained in the broadcast packets received from a transmitting node upon receipt of broadcast packets transmitted from the transmitting node. The Broadcast Count Number (BC) of the received broadcast packet is compared with a buffer size of the pertinent node if all of the broadcast packets transmitted from the transmitting node have been received. A hello packet for flushing a buffer of the transmitting node is generated and transmitted to the transmitting node, the buffer of the pertinent node is flushed, and the neighbor table of the flushed buffer is updated, if the Broadcast Count Number (BC) of the received broadcast packet exceeds the buffer size.

Claims

1. A method comprising:

receiving broadcast packets transmitted from a transmitting node and determining if all of the broadcast packets have been received using a Latest Neighbor'"'"'s Broadcast Count Number (NBC) stored in a neighbor table within a buffer of a pertinent node and a Broadcast Count Number (BC) contained in the broadcast packets received from the transmitting node;

comparing the Broadcast Count Number (BC) of the received broadcast packet with a buffer size of the pertinent node if all of the broadcast packets transmitted from the transmitting node have been received; and

generating a hello packet for flushing a buffer of the transmitting node and transmitting the hello packet to the transmitting node, flushing the buffer of the pertinent node, and updating the neighbor table of the flushed buffer of the pertinent node in accordance with the broadcast packet if the Broadcast Count Number (BC) of the received broadcast packet exceeds the buffer size of the pertinent node.

2. The method according to in claim 1, wherein the neighbor table comprises ID information of a broadcast packet transmitting node, Latest Neighbor'"'"'s Broadcast Count Number (NBC) information, buffer size information of a buffer storing the received broadcast packets and bit map information regarding a list of packets from among the received broadcast packets that have not been received due to a packet error or missing packet.

3. The method according to claim 1, wherein the transmitting node comprises a relay node to relay the broadcast packets transmitted via a sender node which generates and transmits the broadcast packets toward a receiving node.

4. The method according to claim 1, wherein each broadcast packet comprises an IP header field, a relayer node list information field including list information of neighboring relayer nodes, a broadcast count information field of broadcast packets transmitted from an associated node and a broadcast data field.

5. The method according to claim 1, further comprising updating received broadcast packet information in the neighbor table if the Broadcast Count Number (BC) of the received broadcast packet does not exceed the buffer size of the pertinent node.

6. The method according to claim 1, further comprising periodically generating a hello packet containing broadcast packet receipt confirmation information and transmitting the hello packet to the transmitting node according to a predetermined time period or a predetermined packet number upon receipt of the broadcast packet from the transmitting node.

7. The method according to claim 1, wherein the hello packet comprises a packet type information field, a reply information (NACK, ACK) field regarding receipt of the broadcast packet, a flag information field including a reserved field, an ID information field of a neighboring transmitting node, a Broadcast Count Number (BC) information field, a bit map information field (NACK MAP) of missing packets identified by a failure to receive a broadcast packet receipt, a neighbor information field containing ID information of the sender node and neighboring relayer nodes and NACK information as to reply information in response to the failure to receive the broadcast packet receipt, a broadcast retransmission information field containing ID information of a corresponding node from which a broadcast packet has not been received, and a node and ID information or source (SRC) address of the corresponding node.

8. The method according to claim 1, further comprising:

determining if the Broadcast Count Number BC contained in the received broadcast packets is larger than a Broadcast Count Number (NBC+1) following the Latest Neighbor'"'"'s Broadcast Count Number (NBC) if all of the broadcast packet have not been received;

updating a missing packet list in the neighbor table of the receiver node and transmitting a hello packet for retransmission of a missing packet if the Broadcast Count Number transmitted up to the present from the transmitting node is larger than the Broadcast Count Number received up to the present; and

determining if the receiver node has received all of the packets and a corresponding broadcast packet has been received at the request of another node for retransmission of a missing packet and discarding the received broadcast packet if the Broadcast Count Number transmitted up to the present from the transmitting node is not larger than the Broadcast Count Number received up to the present.

9. The method according to claim 6, wherein generating and transmitting a hello packet to the transmitting node comprises:

sequentially retrieving broadcast data bit map information regarding respective nodes which transmitted the broadcast packets stored in the neighbor table to determine if there is a missing packet; and

generating a hello packet for requesting the missing packet using a bit map in the neighbor table and transmitting the hello packet to a corresponding node which transmitted the missing packet if it has been determined that there is a missing packet.

10. The method according to claim 9, wherein, upon receiving the hello packet, the transmitting node:

determines if the hello packet has been received from a new node which is not listed in a neighbor table within a buffer of the transmitting node;

determines if the received hello packet is a triggering hello packet for flushing a full buffer if the hello packet has been received from a node listed in the neighbor table of the transmitting node;

examines bit map information in the received hello packet to determine if there is a missing packet if the received hello packet is not the triggering hello packet but is a hello packet for periodically informing receipt of a broadcast packet; and

transmits a broadcast packet corresponding to the missing packet to the node which transmitted the hello packet and updating the neighbor table of the transmitting node if there is a missing packet.

11. The method according to claim 10, wherein, if the received hello packet is determined to be a triggering hello packet, the transmitting node:

determines if triggering hello packets have been received from all of the neighboring nodes for the purpose of buffer flushing;

flushes the buffer if the triggering hello packets have been received from all of the neighboring nodes and sets a timer to count a set time if the triggering hello packets have not been received from all of the neighboring nodes; and

compares the counted time with the set time and flushes the buffer even though the triggering hello packets have not been received from all of the neighboring nodes if the counted time exceeds the set time.

12. A method comprising:

providing at least one sender node and a relayer node to relay broadcast packets from the sender node to a receiver node;

the receiver node determining if all of the broadcast packets transmitted from the sender or relayer node have been received based upon a Latest Neighbor'"'"'s Broadcast Count Number (NBC) stored in a neighbor table within a buffer of the receiver node and a Broadcast Count Number (BC) contained in the broadcast packets received from the sender or relayer node upon receiving the broadcast packets from the sender or relayer node;

the receiver node comparing the received broadcast packets with the buffer size of the Broadcast Count Number (BC) if all of the broadcast packets from the sender or relayer node have been received; and

generating a hello packet for flushing a buffer in the sender or relayer node and transmitting the hello packet to any of the sender and relayer nodes which transmitted the broadcast packets, flushing the buffer of the receiver node, and updating the neighbor table of the flushed neighbor table of the receiver node using the received broadcast packets if the Broadcast Count Number (BC) of the received broadcast packets exceeds the buffer size of the receiver node.

13. The method according to claim 12, wherein the neighbor table within the buffer of the receiver node comprises ID information of the relayer node which relayed the broadcast packets, latest NBC information received from the node which transmitted the broadcast packets, buffer size information of the buffer storing the received broadcast packets and bit map information regarding a list of packets from among the received broadcast packets which have not been received due to a packet error or missing packet.

14. The method according to claim 12, wherein each of the broadcast packets comprises an IP header field, a relayer node list information field containing list information of neighboring relayer nodes of the receiver node, a broadcast count information field for the broadcast packets transmitted from a corresponding node, and a broadcast data field.

15. The method according to claim 12, further comprising the receiver node periodically generating and transmitting a hello packet containing broadcast packet receipt confirmation information to the relayer node or to the sender node via the relayer node according to a predetermined time interval or a predetermined packet number upon receiving the broadcast packet from the relayer node.

16. The method according to claim 15, wherein the hello packet transmitted to the relayer node or to the sender node via the relayer node from the receiver node comprises:

a packet type information field, a reply information (NACK, ACK) field regarding receipt of the broadcast packet, a flag information field including a reserved field, an ID information field of a neighboring transmitting node, a broadcast count (BC) information field, a bit map information field (NACK MAP) of missing packets identified by a failure to receive a broadcast packet receipt, a neighbor information field containing ID information of the sender node and neighboring relayer nodes and NACK information as reply information in response to the failure to receive the broadcast packet receipt and a broadcast retransmission information field containing ID information of a corresponding one of the relayer and sender nodes from which a broadcast packet has not been received and a node and ID information or source (SRC) address of the corresponding node.

17. The method according to claim 12, further comprising:

determining if the Broadcast Count Number (BC) contained in the received broadcast packet is larger than a Broadcast Count Number NBC+1 following the Latest Neighbor'"'"'s Broadcast Count Number (NBC) if it has been determined that all of the transmitted broadcast packets have not been received from the relayer node;

updating a missing packet list in the neighbor table of the receiver node and transmitting a hello packet for retransmission of a missing packet if the Broadcast Count Number transmitted up to the present from the relayer node is larger than the Broadcast Count Number received up to the present; and

determining if the receiver node has received all of the packets and a corresponding broadcast packet has been received at the request of another node for retransmission of a missing packet and discarding the received broadcast packet if the Broadcast Count Number transmitted up to the present from the relayer node is not larger than the Broadcast Count Number received up to the present.

18. The method according to claim 12, wherein generating and transmitting a hello packet to the relayer node or to the sender node via the relayer node comprises:

sequentially retrieving broadcast data bit map information regarding the sender and relayer nodes which have transmitted broadcast packets stored in the neighbor table within the buffer of the receiver node to determine if there is a missing packet; and

generating a hello packet for requesting the missing packet using bit map information in the neighbor table and transmitting the hello packet to the relayer node or to the sender node via the relayer node that transmitted the missing broadcast packet if it has been determined that there is a missing packet.

19. The method according to claim 18, wherein upon receiving the hello packet, the relayer or sender node:

determines if the hello packet has been received from a new receiver node which is not listed in a neighbor table within a buffer of the relayer or sender node;

determines if the received hello packet is a triggering hello packet for flushing a full buffer if the hello packet has been received from a node listed in the neighbor table of the relayer or sender node;

examines bit map information in the received hello packet to determine if there is a missing packet if the received hello packet is not the triggering hello packet but is a hello packet for periodically informing receipt of broadcast packets; and

transmits a broadcast packet corresponding to the missing packet to the receiver node which transmitted the hello packet and updates the neighbor table of the relayer or sender node if there is a missing packet.

20. The method according to claim 19, wherein, if the received hello packet is determined to be a triggering hello packet, the relayer or sender node:

determines if the triggering hello packets have been received from all of the neighboring nodes for flushing the buffer;

flushes the buffer if the triggering hello packets have been received from all of the neighboring nodes, and sets a timer to count a set time if the triggering hello packets have not been received from all of the neighboring nodes; and

compares the counted time with the set time and flushes the buffer even though the triggering hello packets have not been received from all of the neighboring nodes if the counted time exceeds the set time.

21. A method comprising:

providing at least one sender node and a relayer node to relay broadcast packets from the sender node to a receiver node;

transmitting a hello packet processed by the relayer or sender node upon receipt of the broadcast packets;

determining if the hello packet has been received from a new receiver node which is not listed in a neighbor table within a buffer of the relayer or sender node;

determining if the received hello packet is a triggering hello packet for flushing a full buffer if the hello packet has been received from a node listed in the neighbor table of the relayer or sender node;

examining bit map information in the received hello packet to determine if there is a missing packet if the received hello packet is not the triggering hello packet but is a hello packet for periodically acknowledging receipt of the broadcast packets; and

transmitting a broadcast packet corresponding to the missing packet to the receiver node which transmitted the hello packet and updating the neighbor table of the relayer or sender node if there is a missing packet.

22. The method according to claim 21, wherein if the received hello packet is determined to be a triggering hello packet, the relayer or sender node:

determines if the triggering hello packets have been received from all of neighboring nodes for flushing the buffer;

flushes the buffer if the triggering hello packets have been received from all of the neighboring nodes and sets a timer to count a set time if the triggering hello packets have not been received from all of the neighboring nodes; and

compares the counted time with the set time and flushes the buffer even though the triggering hello packets have not been received from all of the neighboring nodes if the counted time exceeds the set time.

23. The method according to claim 21, wherein the hello packet transmitted from the receiver node comprises:

a packet type information field, a reply information (NACK, ACK) field regarding receipt of the broadcast packet, a flag information field including a reserved field, an ID information field of a neighboring transmitting node, a broadcast count (BC) information field, a bit map information field (NACK MAP) of missing packets in response to a failure to receive a broadcast packet receipt, a neighbor information field containing ID information of the sender node and neighboring relayer nodes and NACK information as reply information in response to the failure to receive the broadcast packet receipt and a broadcast retransmission information field containing ID information of a corresponding one of the relayer and sender nodes from which a broadcast packet has not been received and a node and ID information or source (SRC) address of the corresponding node.