DETERMINISTIC BROADCASTING AND RANDOM LINEAR NETWORK CODING IN MOBILE AD HOC NETWORKS
ABSTRACT
Network coding has been successfully used in thepast for efficient broadcasting in wireless multi-hop networks.Two coding approaches are suitable for mobile networks; randomlinear network coding (RLNC) andXOR-based coding. In thispaper, we focus on the problem of multiple source broadcastingin mobile ad hoc networks. We make the observation that RLNCprovides increased resilience to packet losses compared withXOR-based coding. We develop an analytical model that justifiesour intuition. However, the model also reveals that combiningRLNC with probabilistic forwarding, which is the approach takenin the literature, may significantly impact RLNC’s performance.Therefore, we take the novel approach to combine RLNC witha deterministic broadcasting algorithm in order to prune transmissions.More specifically, we propose a connected dominatingset-based algorithm that works in synergy with RLNC on the“packet generation level.” Since managing packet generations isa key issue in RLNC, we propose a distributed scheme, which isalso suitable for mobile environments and does not compromisethe coding efficiency. We show that the proposed algorithmoutperformsXOR-based as well as RLNC-based schemes evenwhen global knowledge is used for managing packet generations.
PROPOSED SYSTEM:
We develop an analytical model (Section IV) that shedslight on the differences between RLNC and XOR basedbroadcast schemes oriented towards energy efficiency.Such information is very useful since only sparseempirical data exist in the literature for comparing thetwo methods. The model confirms that RLNC is capableof providing increased resilience to transmission errors.• We use the developed model to unveil the potentialpitfalls of combining RLNC and probabilistic forwardingand stress the need for a topology-aware pruning process.• Following our observations, we turn to deterministicbroadcasting, which has never been used for pruningtransmissions in the context of an RLNC enabled scheme.More specifically, the proposed algorithm (Section V)implements CDS (Connected Dominating Set) basedforwarding rules “on the generation level” in order toallow the flow of packet generations over the CDS. Therationale is that the CDS will provide a more systematicand topology-aware pruning of redundant transmissionswithout impairing the coding efficiency of RLNC.• We address the problem of generation management,i.e. the need of nodes to distributively agree in thegrouping of packets into generations. Although this isvital for practically implementing RLNC, some of itsaspects that are critical when packets from differentsources are “mixed” into a generation, are rarelydiscussed in the literature. We review the pendingproblems and propose a distributed mechanism that doesnot compromise the coding efficiency (Section VI).• Our analytical model also reveals that an increasedpacket loss rate significantly impairs the performanceof RLNC in nodes experiencing poor connectivity. Thisholds true even if deterministic broadcasting is used.To tackle the problem, we extend the proposed algorithmin order to enhance the topology-awareness of thepruning process (Section VIII).
EXISTING SYSTEM:
Several studies have investigated the use of network codingfor broadcasting in wireless networks. The proposed algorithmscan be classified, based on the coding method, into:i) RLNC-based, and ii) XOR-based approaches. RLNC-basedalgorithms build on the concepts ofpractical RLNC. From this category, only the algorithmsthat focus on energy efficiency are suitable for mobilenetworks. All of them take a probabilistic approach to forwardencoded packets. More specifically, Fragouli et al.extend the probabilistic algorithm, proposed and intro-duce two topology-aware heuristics to determine the numberof encoded packets, that each node should forward, in orderfor the receivers to decode the original packets. The algorithmalso allows the encoding of packets from different sourcesby incorporating rules for the distributed management ofpacket generations. Other techniques extend this algorithm bymodifying the forwarding heuristics and the generation man-
CONCLUSION
Random linear network coding is used to enhance theresilience of protocols to packet losses. We proved, throughanalysis, that we need to utilize a topology-aware algorithmin order to maximize its benefits. To this end, despite thecommon approach in the literature, which is to use randomlinear coding on top of probabilistic forwarding schemes, wechose the synergy with a CDS-based broadcast algorithm.Furthermore, we proposed an extension of the basic algorithmin order to enhance topology-awareness and cater for poorlyconnected nodes, especially when the packet loss rate ishigh. We demonstrated, through simulation, the efficiencyof both approaches. Moreover, we provided a distributedmechanism for managing generations. The mechanism doesnot compromise the coding efficiency even in cases of highmobility and increased packet loss rate. In the future, weplan to investigate new generation management techniques andexplore their impact on the performance of RLDP.agement mechanism. The second subclass of RLNC-basedalgorithms focuses on reliability and integrates somekind of feedback mechanism. The feedback information isused to determine the optimal rate, i.e. the number of packetsto be forwarded by intermediate nodes, so that delivery ofpackets is guaranteed. Clearly, this strategy is not orientedtowards minimizing the cost of broadcasting. Furthermore,a feedback mechanism increases the cost while its implementationis not straightforward in mobile networks. Therefore,those algorithms have only been proposed for static networks.Finally, Ostovari et al. study the problem of timelinessin broadcasting. They use RLNC over broadcasting trees in astatic network and under the assumptions of lossless links andknowledge of global information
REFERENCES
[1] M. Abolhasan, T. Wysocki, and E. Dutkiewicz, “A review of routingprotocols for mobile ad hoc networks,” Ad hoc Netw., vol. 2, no. 1,pp. 1–22, Jan. 2004.
[2] A. N. Mian, R. Baldoni, and R. Beraldi, “A survey of service discoveryprotocols in multihop mobile ad hoc networks,” IEEE PervasiveComput., vol. 8, no. 1, pp. 66–74, Jan. 2009.
[3] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network informationflow,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204–1216,Jul. 2000.
[4] C. Fragouli, J. Widmer, and J.-Y. Le Boudec, “Efficient broadcast-ing using network coding,” IEEE/ACM Trans. Netw., vol. 16, no. 2,pp. 450–463, Apr. 2008.
[5] J. Widmer and J.-Y. Le Boudec, “Network coding for efficient communicationin extreme networks,” in Proc. ACM SIGCOMM WorkshopDelay-Tolerant Netw. (WDTN), Aug. 2005, pp. 284–291.
[6] T. Kunz, K. Mahmood, and L. Li, “Broadcasting in multihop wirelessnetworks: The case for multi-source network coding,” in Proc. IEEE Int.Conf. Commun. (ICC), Jun. 2012, pp. 6679–6684.
[7] L. Li, R. Ramjee, M. Buddhikot, and S. Miller, “Network coding-basedbroadcast in mobile ad-hoc networks,” in Proc. IEEE Int. Conf. Comput.Commun. (INFOCOM), May 2007, pp. 1739–1747.
[8] S. Yang and J. Wu, “Efficient broadcasting using network coding anddirectional antennas in MANETs,” IEEE Trans. Parallel Distrib. Syst.,vol. 21, no. 2, pp. 148–161, Feb. 2010.
[9] N. Kadi and K. Al-Agha, “Optimized MPR-based flooding in wirelessad hoc network using network coding,” in Proc. 1st IFIP WirelessDays (WD), Nov. 2008, pp. 1–5.
[10] A. Asterjadhi, E. Fasolo, M. Rossi,J.Widmer,andM.Zorzi,“Towardnetwork coding-based protocols for data broadcasting in wireless ad hocnetworks,” IEEE Trans. Wireless Commun., vol. 9, no. 2, pp. 662–673,Feb. 2010.
[11] I.-H. Hou, Y.-E. Tsai, T. F. Abdelzaher, and I. Gupta, “AdapCode:Adaptive network coding for code updates in wireless sensor networks,”in Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM), Apr. 2008,pp. 1517–1525.
[12] S. Y. Cho and C. Adjih, “Wireless broadcast with network coding:Dynamic rate selection,” in Proc. IFIP Annu. Med. Ad Hoc Netw.Workshop, 2008, pp. 191–202.