New Ad Hoc Network Design Guarantees Delivery
Most networks we deal with each day, such as those that use Ethernet, Wi-Fi, and cellular communication, have central nodes which know the shape of the network and can direct traffic through it. In some situations, including emergency areas and battlefields, such networks are impossible so ad hoc or decentralized networks are used, which means no node knows the entire network. One concern about using these kinds of networks is ensuring data is delivered, but researchers at MIT have found a new design which can guarantee delivery.
Traditional ad hoc network designs utilize a probabilistic method to demonstrate that it is very unlikely a delivery will not be successful, due to the random nature of the network. This new design is deterministic though and actually the only way for delivery to fail requires a specific structure which is impossible. To send data in this new network, first a node selects one other node to send the data to, and then it selects a second, different node to again send the information to. It continues to send the information for two rounds before it adds a third distinct node, after which it sends data to the three nodes for three consecutive rounds. This pattern continues on until every node has been contacted directly or indirectly.
As an added bonus, this method appears to be more efficient than other designs as it requires less communication between nodes to successfully send data. Also the math involved seems to indicate a maximum speed for sending a message in an ad hoc network, but the researchers have not been able to prove that yet.