Network-coding And Link-correlation-based Multi-packet Flooding Protocol

With the rapid development of information technology, wireless sensornetworks(WSNs) have been used to many applications. Flooding is a fundamentalrouting protocol in WSNs, which supporting many important high-level protocols andapplications. In WSNs, existing work on flooding mainly focuses on single-packetproblem, while work in sequential multi-packet problem is surprisingly little. Thispaper proposes OppCode, a new opportunistic network-coding based floodingarchitecture for multi-packet dissemination in WSNs, where both unreliable andcorrelated links commonly exist. Instead of flooding a single packet each time, eachnode encodes multiple native packets chosen from a specific fixed-size page to anencoded packet, and then rebroadcasts it further.The key idea consists of two parts: one is opportunistically coding decision, inwhich each node grasps every possible coding opportunity greedily to conduct anencode-and-forward operation in order to maximize its total (or aggregate) codinggain of all neighbors based on the probabilistic estimations of packets each neighboralready has (i.e., coverage); the other is paged collective acknowledgements (ACKs),in which one rebroadcast that arrives at a receiver acts as not only an implicit ACK ofsuccessful disseminations of all packets in the entire page for the sender, but alsoprobabilistic ACK to update page-scale per-packet coverage estimations for itsneighbors in a batch.We evaluate our design using extensive simulations and on a20-node WSNstestbed, and show that OppCode largely increases performance of multi-packetflooding compared with state-of-the-art solutions, especially when links are highlyunreliable and correlated with each other. The gains vary from a few percent toseveral folds depending on the network density, link conditions, coverage thresholdand page size.