Keywords
|
| broadcast;minimum transmission broadcast; network coding;transmission efficiency; wireless networks. |
INTRODUCTION
|
| A Wireless Network consists of several hosts which communicate with each other and roam around at their will. Due to certain limitations in the network a host may not be able to communicate directly with the other host in a single-hop fashion. In this case multi-hop scenario occurs where a packet sent by source is relayed by several intermediate hosts before reaching the destination for which broadcasting is essential. Broadcasting is a process where a node sends data to all other nodes in the network. Because of the shared nature of wireless channel it plays a very important role in a Wireless Network. It is a frequent operation in any type of wireless network. Many routing algorithms use broadcasting in their route discovery process [1]. It is widely used in sending control packets by various protocols either in wireless sensor networks or in vehicular networks or in any other such networks. Broadcasting techniques can be classified into various categories. |
| A. Naïve Broadcast Scheme: |
| Naïve Broadcast schemes are inefficient, which is a simple flooding which causes severe wastage of channel and severe packet collision. This will lead to Broadcast Storm Problem [2]. This Broadcast Storm Problem can be neglected in one-to-all scenarios but it becomes severe in case of many-to-all networks where there are several nodes and all the nodes send packets to all other nodes in the network because of that packet collision and contention increases. |
| B. Probabilistic Approach without Network Coding: |
| In probabilistic approach packets are forwarded with a given probability [3]. Here the challenge is to find the proper value of probability.Probability value of the packet is used to find the priority of the packet and the packets are sent accordingly. This has been developed only for one-to-all scenarios. |
| C. Deterministic Approach without Network Coding: |
| Deterministic approach makes use of connected dominating set of forwarders. The nodes which are in the forwarders list will only forward the packets. The challenge is to minimize the number of forwarders. Many approximation algorithms [4],[5] have been proposed. Only for one-to-all scenarios this has been proposed. |
| D. Network Coding Technique: |
| Network Coding [6] Technique is a trustworthy technique where it improves the transmission efficiency by combining the packets before forwarding them. Various researches have shown that the network coding can effectively reduce the number of transmissions [6],[7],[8],[9],[10]. The challenge in Network Coding technique is, upon reception of a packet whether to forward the packet immediately or to wait for additional amount of time in order to gain coding opportunity.Take Fig. 1 as an example, where node 1 and 2 are source nodes. Without network coding, the number of transmissions are 4 i.e. 2+2. With network coding the number of transmissions can be reduced to 3 where node 3 combines the two packets before forwarding them. |
NETWORK CODING TECHNIQUES
|
| A. Partial Dominant Pruning: |
| Partial Dominant Pruning (PDP) [11], which does broadcasting based on forwarder selection process but it doesn’taim for coding opportunity. Coding is not gained at all. PDP selects a forwarder list based on PDP algorithm. Only the nodes in the forwarder list forward the packets. This works as follows-Let N(u) represent the set of neighbours of node u, including u.Let N(N(u)) represent two-hop neighbourhood of node u. Consider u sends a broadcast packet to v, by selecting v as its forwarder node, v then selects a forwarder list, this forwarder list contains the minimum number of broadcast nodes that would re-broadcast packets to cover all the nodes which are in the 2-hop neighbourhood of it, N(N(v)).Among nodes in N(N(v)), nodes in N(u) have received the packets already while nodes in N(v) will receive the packet when v broadcasts it. Neighbours of nodes which are common in nodes in N(u) and N(v) i.e N(N(u)∩N(v)) will also receive the packets. Thus v needs only to determine its forwarder node set G(u,v)from nodes in B(u,v)=N(v)-N(u) to cover the nodes in U(u,v)=N(N(v))-N(u)-N(v)-N(N(u)∩N(v)).A greedy set cover algorithm is used to selectforwarding nodes. |
| B. Coding-based Broadcast: |
| Coding-based Broadcast (CODEB) selects forwarders by PDP where the nodes at two-hop are selected. It comprises of two algorithms, XOR-based coding and Reed-Solomon coding. However, the coding gain of CODEB is restricted since the forwarder selection process will not contain the coding opportunity [12]. CODEB incorporates three main techniques which are given as follows. |
| 1. Opportunistic listening: |
| CODEB operates in unselective mode withOmni-directional antennae. Nodes continuously listen all communicationsover the wireless medium and overheardpackets will be stored for a limited period. Nodes also broadcast the set of nodes it can hear which are one-hop neighbours to all its one-hop neighbours periodically. Using this,nodes will build a two-hop neighbour graph.By using this graph and the previous hop k of a packet p, node j can infer that the neighbours of k has received p. Based on this, every node create a neighbour reception table. If a new packet is unable to find any coding opportunity, then the packet can be sent to the interface queue or buffered in the coding layer for small amount of time. If the applications are delay tolerant, buffering can increase coding opportunities. |
| 2. Forwarder selection and pruning: |
| Here subset of neighbours is selected as forwarders. PDP algorithm is used to select forwarders .The forwarder set is put in the packet header and a node which is there in the forwarders list will only forward the packet. From opportunistic listening a list of nodes which has received packets can be identified. If a node is a forwarder node and it determines that all its neighbours have received the packet, then it is not necessary to send the packets to those neighbours. |
| 3. Opportunistic coding: |
| In opportunistic coding, each node examines its set of packets which are to be forwarded and its current neighbour table obtained through opportunistic listening. Then it determines whether it can exploit coding opportunities by sending coded packets. If it can, then it will send the packets.There are two algorithms for coding packets: |
| 1) A simple XOR-based algorithm that XOR a number of packets in the buffer so that maximum number of nodes are able to decode the packet. |
| 2) An optimal coding scheme which uses Reed-Solomon code as the coefficients for combining native packets linearly. |
| C. Responsibility Based Scheme: |
| The main idea behind Responsibility Based Scheme (RBS) [13]is, a node avoids broadcasting if it is not responsible for any of its neighbours. A node NA is not responsible for a neighbour NB if NB has received the message or if there is another neighbour NC such that NC has received the message and NB is closer to NC than it is to NA. Suppose NA stores IDs of all its neighbours that have broadcast the message during defer period. When node NA executes RBS algorithm first uses this information to determine which neighbours have not received the message.But it was designed for one-to-all broadcast. |
| D.Priority-based Network Coding Broadcast: |
| PNCB is a Priority based network coding broadcast protocol which aims at improving coding opportunity, has been proposed for many-to-all scenario. However it has been used only with reliable links where the data reception is guaranteed [14].PNCB consists of two phases—broadcast trees construction phase and priority-based coding-aware forwarding phase. |
| In the first phase, broadcast trees for all source nodes are constructed in such a way that attempts to minimize the number of internal nodes and maximize coding opportunities. |
| In the second phase, each node disseminates broadcast packets in a network coding manner, based on several coding-aware forwarding rules. In addition, the priority-based deadlock prevention mechanism is adopted to avoid deadlocks that may happen in few topologies. |
CONCLUSION
|
| This survey presents the various network coding techniques used for solving the MTB problem in wireless networks. Each surveyed method is significantly efficient. This paper shows the pros and cons of each method in various aspects. The efficiency of the surveyed method can be measured in terms of number of transmissions and computational time. The merits of each method can be taken into account and further these techniques can be enhanced for reducing the number of transmissions efficiently. |
Figures at a glance
|
 |
| Figure 1 |
|
References
|
- F.-W. Chen and J. –C. Kao, “Game-Based Broadcast over Reliable and Unreliable Wireless Links in Wireless Multihop Networks,” IEEETransactions on Mobile Computing, vol. 12, no. 8, pp. 1613-1624, Aug. 2013DilipKumar S. M. and Vijaya Kumar B. P. ,’Energy-AwareMulticast Routing in MANETs: A Genetic Algorithm Approach’, International Journal of Computer Science and Information Security(IJCSIS), Vol. 2,2009.
- S.-Y. Ni, Y. -C. Tseng, Y. –S. Chen and J. –P.Sheu, “The Broadcast Storm Problem in a Mobile Ad Hoc Network, “ in Proc. ACM/IEEEMobiCom, Seattle, Washinton, Aug. 1999.
- Y. Sasson, D. Cavin, and A. Schiper, “Probabilistic Broadcast forFlooding in Wireless Mobile Ad Hoc Networks,” in Proc. IEEE WCNC, NewOrleans, LA, March 2003.
- H.-I. Lu and R. Ravi, “Approximating Maximum Leaf Spanning Trees inAlmost Linear Time,” Journal of Algorithms, vol. 29, no. 1, pp. 132-141,Oct. 1998.
- P.-J. Wan, K. M. Alzoubi, and O. Frieder, “Distributed Construction ofConnected Dominating Set in Wireless Ad Hoc Networks,”MobileNetworks and Applications, vol. 9, no. 2, pp. 141-149, Apr. 2004.
- R. Ahlswede, C. Ning, S.Y. R. Li, and R. W. Yeung, “Network Information Flow, “ IEEE Trans. On Information Theory, vol. 46, no. 4,pp.1204-1216, July 2000.
- H. Shah Mansouri and M. R. Pakravan, “Reliable and Energy Efficient Single Source Broadcasting Using Network Coding in Wireless Ad-HocNetworks,” in Proc.ICT-MICC, Penang,Malaysia,May 2007.
- H. Shah Mansouri and M. R. Pakravan, “Network Coding Based Reliable Broadcasting in Wireless Ad-hoc Networks,” in Proc. IEEE Intl.Conference on Networks, Adelaide, Australia, Nov 2007.
- J. Widmer, C. Fragouli, and J. Le Boudec, “Low-Complexity Energy-Efficient Broadcasting in Wireless Ad-Hoc Networks Using NetworkCoding,” in Proc. Workshop on Network Coding, Theory, and Applications, Riva del Garda, Italy, April 2005.
- C. Fragouli, J. Widemer, and J.Y. Le Boudec, “A Network Coding Approach to Energy Efficient Broadcasting: From Theory to Practice, “inProc. IEEE INFOCOM, Bacelona, Spain, April 2006.
- W. Lou and J.Wu, “On reducing broadcast redundancy in ad hoc wireless networks,” IEEE Transactions on Mobile Computing, 2002.
- Li (Erran) Li, R. Ramjee, M. Buddhikot, and S. Miller, “Network Coding-Based Broadcast in Mobile Ad Hoc Networks” in Proc.IEEEINFOCOM, Phoenix, USA, Apr. 2008.
- M. Khabbazian and V. K. Bhargava, “Efficient Broadcasting in Mobile Ad Hoc Networks,” IEEE Trans. on Mobile Computing, vol. 8, no.2,pp. 231-245, Feb. 2009.
- Chieh-Hao Chang; Jung-Chun Kao; Fu-Wen Chen; Shih Hsun Cheng, "Many-to-all priority-based network-coding broadcast in wirelessmultihop networks," Wireless Telecommunications Symposium (WTS), 2014 , vol., no., pp.1,6, 9-11 April 2014.
|
Menu