Apparatus and method for practical and efficient broadcast in mobile ad hoc networks
View Patent ↗The present invention demonstrates how network-coding can be applied to a deterministic broadcast approach, resulting in significant reductions in the number of transmissions in the network. We propose two algorithms, that rely only on local two-hop topology information and make extensive use of opportunistic listening to reduce the number of transmissions: 1) a simple XOR-based coding algorithm and 2) a Reed-Solomon based coding algorithm that determines the optimal coding gain achievable for a coding algorithm that relies only on local information.
1. A method of performing broadcast operations of information to be transmitted from one or more sources to all nodes in an ad-hoc mobile communications network, said method comprising the steps of:
determining at a node a set of forwarding nodes for re-transmission of said information from said node to a given number of neighboring nodes in said network;
deterministically rebroadcasting said information to said other given number of nodes in said network, wherein said information that is rebroadcast is done so utilizing opportunistic coding.
2. The method of claim 1 , wherein said coding is performed utilizing an XOR-based coding algorithm.
3. The method of claim 1 , wherein said coding is performed utilizing a Reed-Solomon coding algorithm.
4. The method of claim 3 , wherein said coding algorithm determines the optimal coding gain achievable for a coding algorithm that relies upon local information.
5. The method of claim 4 , wherein said deterministic approach is a partial dominant pruning (PDP) based approach.
6. The method of claim 5 , wherein the forwarder set is stamped in the packet header and a node only rebroadcasts a packet when it is chosen as a forwarder.
7. The method of claim 1 , wherein each forwarder node examines its set of to-be-forwarded packets and its current neighbor table obtained through opportunistic listening, and dynamically determines if it can exploit coding opportunities to send coded packets, instead of sending native packets.
8. The method of claim 1 , wherein each forwarder node builds a neighbor reception table in order to determine which neighbor nodes receive given packets, such that the forwarder may deduce which neighbor nodes are able to receive packets from the forwarder.
9. A method of operating a node in an ad hoc mobile communications network for performing broadcast operations, wherein upon receiving a packet a node updates its neighbor table and delegates a subset of neighbors of said node as forwarders, said method comprising the steps of:
determining whether opportunities for coding exist for encoding a received packet with a set of already received packets that needs to be forwarded;
generating one or more encoded packets if opportunities for coding exist;
if no coding opportunities exist and the packet is related to a delay tolerant application, then buffering the packet for a given amount of time in order to enable additional coding opportunities; and
scheduling coded or non-coded packets for transmission.
10. The method of claim 9 , wherein a step of coding includes the steps of: processing a given packet at the head of a queue and sequentially processing other packets in the queue that when combined with said given packet will allow all neighbors of the node to decode the packet, wherein, if successful, these packets are added to a set B of packets to be encoded using XOR or Reed-Solomon codes.
11. The method of claim 10 , wherein for XOR encoding, said node uses a neighbor table obtained through opportunistic listening to ensure that all neighbors have already received at least |B|−1 of the packets in set B, in order to decode the coded packet.
12. The method of claim 10 , wherein for Reed-Solomon encoding, said node uses a neighbor table obtained through opportunistic listening to ensure that all neighbors have already received at least |B|−k of the packets in set B, in order to decode the coded packet.
13. The method of claim 9 , wherein for Reed-Solomon encoding said node constructs a coded packet set Q, wherein a set of native packet IDs is added to each coded packet.
14. The method of claim 13 , wherein the set of IDs can be spread across k packets, wherein a node adds the index number of codes used.
15. A node apparatus performing broadcast operations of information to be transmitted from one or more sources to all nodes in an ad-hoc mobile communications network, said apparatus operable to:
determine at a node a set of forwarding nodes for re-transmission of said information from said node to a given number of neighboring nodes in said network; and
deterministically rebroadcast said information to said other given number of nodes in said network, wherein said information that is rebroadcast is done so utilizing opportunistic coding.
16. The apparatus of claim 15 , wherein said coding is performed utilizing an XOR-based coding algorithm.
17. The apparatus of claim 15 , wherein said coding is performed utilizing a Reed-Solomon coding algorithm.
18. The apparatus of claim 17 , wherein said coding algorithm determines the optimal coding gain achievable for a coding algorithm that relies upon local information.
19. The apparatus of claim 15 , wherein each forwarder node examines its set of to-be-forwarded packets and its current neighbor table obtained through opportunistic listening, and dynamically determines if it can exploit coding opportunities to send coded packets, instead of sending native packets.
20. The apparatus of claim 15 , wherein each forwarder node builds a neighbor reception table in order to determine which neighbor nodes receives given packets, such that the forwarder may deduce which neighbor nodes are able to receive packets from the forwarder.