书：无线传感网中的网络编码技术

Chapter 1 Network Coding Techniques for Wireless and Sensor Networks 1Pouya Ostovari,1Jie Wu, and2Abdallah Khreishah Abstract Network coding is a technique where relay nodes mix packets using mathemat- ical operations, which reduces the number of transmitted packets. Network coding was first proposed for wired networks to solve the bottleneck problem and to in- crease the throughput. However, the broadcast nature of wireless networks and the diversity of the links make network coding more attractive in wireless networks. Network coding can be classified as either inter or intra-session. Inter-session net- work coding allows the packets from different sessions (sources) to be mixed to solve the bottleneck problem. In contrast, intra-session network coding, which can be used to address the packet loss problem, uses the diversity of the wireless links and mixes packets from the same sessions. In this chapter, we survey the recent works on network coding in both general wireless networks and wireless sensor networks. We present various network coding techniques, their assumptions, appli- cations, as well as an overview of the proposed methods. Key words: Network coding, wireless networks, wireless sensor networks, inter- session, intra-session, broadcast, multicast, unicast. 1.1 Introduction As the demand for communication services is growing, wireless solutions becomes more and more important. Due to their ease of deployment, wireless networks play a major role in our lives. They are also ideal to provide a convenient solution to the last mile problem [1][2]. Wireless networks can be cellular networks that are used for mobile phones, or Wi-Fi networks that provide an Internet connection. Different multihop wireless network settings are used. Mesh networks can be used to provide Internet access and file sharing [3]. Wireless Sensor Networks [4] (WSN) can be 1Department of Computer & Information Sciences, Temple University, Philadelphia, PA 19122 � 2Department of Electrical & Computer Engineering, New Jersey Institute of Technology, Newark, NJ 07102 1 2 1Pouya Ostovari,1Jie Wu, and2Abdallah Khreishah ݏͳ ݎ ݏʹ ݌ͳ ݌ʹ ݌ʹ ݌ͳ ݏͳ ݎ ݏʹ ݌ͳ ݌ʹ ݌ͳ�ْ ݌ʹ (a) (b) Fig. 1.1 Binary network coding. used for military applications, such as enemy detection in battlefields. They can also be used for disaster detection and monitoring applications. Despite the diverse types of wireless networks and their applications, the com- mon features of wireless networks create opportunities to be exploited and chal- lenges to be addressed. These common features include the broadcast nature of wireless links, the interference among the links, the diversity of the links, and the lossy behavior of the links [5]. Also, the correlation between the links may affect the performance of the wireless communication protocols. Inter-Session Network Coding. The broadcast nature of wireless networks is considered a challenge, as it creates interference between the links and produces unnecessary multiple copies of the same packet. However, if we allow the intermedi- ate wireless nodes to code the packets, the broadcast nature becomes an opportunity. Consider the example in Figure 1.1(a), where nodes s1 and s2 want to exchange their own packets, p1 and p2, respectively. Assuming that these nodes are out of range of each other, this communication incurs four transmissions; two transmissions for sending the packets to the relay node, and two transmissions for relaying the pack- ets. However, the relay node can simply XOR the packets and send the coded packet p1� p2 [6], which is shown in Figure 1.1(b). The nodes s1 and s2 can retrieve each others’ packets by XOR-ing p1� p2 with their own packets, p1 and p2, respectively. As a result, the number of transmissions has been reduced to three by using binary network coding. Inter-session network coding solves the bottleneck problem and reduces the number of transmissions, by allowing packets from different sessions (sources) to be coded together. By reducing the number of required transmissions, network coding increases the throughput and decreases the interference between the links in wireless networks. Intra-Session Network Coding. Another important application of network cod- ing is to provide reliability in wireless networks. The traditional way to provide reliability for both wired and wireless networks is to use feedback messages to re- port the received (or lost) packets. By using feedback messages, the sender node will know which packets need to be sent again. However, these feedback messages consume bandwidth. Consider the example in Figure 1.2; the source node wants to deliver packets p1 and p2 to the node d. The reliability of the link s1 ! d is equal to 23 . In the case that the source node sends three coded packets, p1+ p2, p1+2p2, and 2p1+ p2, on average, the destination node will receive two of the three coded packets. Therefore, the destination nodes will be able to retrieve the packets p1 and 1 Network Coding Techniques for Wireless and Sensor Networks 3 ݏͳ ݀ 2/3 ݌ͳ ݌ʹ ݌ͳ+ʹ݌ʹ ݌ͳ+݌ʹ 2݌ͳ+݌ʹ Source packets Random linear coding Fig. 1.2 Application of network coding to provide reliability. p2. However, without network coding, we need to use a feedback mechanism or else the source node needs to transmit each packet twice. As a result, communica- tion schemes with network coding can provide reliability with a fewer transmissions than schemes without network coding. Coding the packets from the same session (source) is called intra-session net- work coding, which exploits the diversity of the links. In intra-session network cod- ing, the packets from the same source are coded together (usually linearly), which makes the importance of the packets the same. Therefore, when k packets are coded together, a relay node does not need to know exactly which packets are received by the destination node; it is thereby enough to successfully deliver k coded packets out of the transmitted coded packets. Opportunistic Routing. An efficient way to address packet loss in wireless net- works without network coding is to use opportunistic routing approaches [7]. When a node broadcasts a packet, it is probable that the next-hop does not receive the packet. However, because of the broadcast nature of the wireless medium, and the diversity among the links, a neighbor of the sender can receive and forward the packet as the next-hop with high probability. In opportunistic routing, there is no specific path from the source to the destination, and any node that overhears the packet can relay it. Take Figure 1.3 as an example, in which node s wants to send 4 packets to the destination d. The delivery rate of the links are shown beside the links. Assume that each relay node received the packets shown beside the nodes. If we use traditional shortest path routing, the route from s to d will be fixed. Assuming that the chosen route is s! r1 ! d, the source node needs to retransmit the packets p3 and p4. On the other hand, if we allow the other nodes that received the packets p3 and p4 to forward them, the source node will not need to retransmit any packet. The main challenge in opportunistic routing is coordinating the intermediate nodes. To prevent redundant transmissions, the intermediate nodes need to send feedback or listen to the other nodes’ transmissions to find out if there is a neighbor that has received the transmitted packet. For this purpose, the intermediate nodes need to be able to overhear each other, which might not be possible, as shown in Figure 1.3. Network coding can solve this problem [8]. To this purpose, the source 4 1Pouya Ostovari,1Jie Wu, and2Abdallah Khreishah ݀ ݏ ͳܲ ǡ ܲʹ ǡ ܲ͵ ǡ Ͷܲ ʹݎ ͳܲ ǡ ܲʹ ͳܲ ǡ ܲ͵ 1 10.5 ͵ݎ 0.5 0.5 1 ܲʹ ǡ Ͷܲ ݎͳ Fig. 1.3 Opportunistic routing. node divides the packets to be sent in batches of k packets. The source keeps sending coded packets of the form åki=1aipi, where ai is a random coefficient chosen over a finite field. When an intermediate node receives a coded packet, the node checks if the coded packet is linearly independent to the previously received packets. If so, the node will add the packet to its buffer. Each intermediate node generates linear combinations of the packets in its buffer and sends the coded packets. The desti- nation node can decode all of the packets of the batch when it receives k linearly independent packets. In this case, the destination node sends feedback to the source to stop sending the packets. Cross-Layer Design. Using network coding methods in wireless protocols in- curs new challenges. For example, previous routing protocols are unaware of net- work coding. However, the routing protocol affects the coding opportunity. If two flows pass through relay nodes that are far from each other, there will be no coding opportunity. On the other hand, flows that are close to each other result in more inter- ference. Therefore, to increase the efficiency of the proposed protocols for wireless networks, cross-layer approaches are needed. In cross-layer approaches, the pro- tocols of different layers are independent. However, they communicate with each other to make decisions and perform more efficiently. Wireless Sensor Networks. Sensor networks differ from the general wireless networks in performance metrics, traffic patterns, and their amount of available memory and processing resources [9]. These differences make some of the net- work coding approaches proposed for general wireless networks inappropriate for WSNs. For example, in some of the network coding methods, the nodes should lis- ten to their neighbors and store the overheard messages in their buffers. However, in sensor networks, because of the memory limitation, sensor nodes cannot cache overheard packets that might not be useful [10]. WSNs’ protocols must be simple and easily implemented. Moreover, the links’ quality between the sensor nodes vary over the time, and nodes can fail or disconnect. Therefore, the dynamic environment 1 Network Coding Techniques for Wireless and Sensor Networks 5 ݌ͳ ݌ʹ ݌ͳ ݌ʹ ݌ͳ�ْ ݌ʹ (a) (b) ݌͵ ݌Ͷ ݌ͳ ݌ʹ ݏͳ ݏʹ ݎ ݀ʹ ݀ͳ ݏͳ ݏʹ ݎ ݀ʹ ݀ͳ ͵݌ͳ ൅ ʹ݌ʹ ʹ݌ͳ െ Ͷ݌ʹ ͵݌ͳ ൅ ʹ݌ʹ Ͷ݌ͳ ൅ ͵݌ʹ ʹ݌͵ ൅ ͷ݌Ͷ ͵݌͵ ൅ Ͷ݌Ͷ ͵݌͵ ൅ Ͷ݌Ͷ ͸݌͵ ൅ ͵݌Ͷ (c) ݌͵ ݌Ͷ ݌ͳ ݌ʹ ݏͳ ݏʹ ݎ ݀ʹ ݀ͳ ͷ݌͵ ൅ ͻ݌Ͷ ͷ݌ͳ െ ʹ݌ʹ ͹݌ͳ െ ͸݌ʹ ͹݌͵ ൅ ͳͶ݌Ͷ Fig. 1.4 XOR and random linear coding. should be considered, and the algorithms should be adaptive to reflect this dynamic nature [10]. The rest of this chapter is organized as follows. We provide our classifica- tion methodology in Section 1.2. In Section 1.3, we describe some of the well- known proposed methods for unicast application, and we categorize them. A discus- sion about multicast and broadcast network coding approaches is provided in Sec- tions 1.4 and 1.5, respectively. Section 1.6 concludes the chapter. Note that fountain codes (also known as rateless erasure codes), such as online codes [11], LT codes [12], and raptor codes [13], are beyond the scope of this chapter. 1.2 Classification of Network Coding Approaches From one perspective, network coding can be classified into XOR (binary) coding and Random Linear (RL) coding. In binary coding, XOR operations are performed between the packets. Take Figure 1.4(a) as an example; we have two flows: one of them between nodes s1 and d1 and the other between nodes s2 and d2. Without network coding, the relay node needs two transmissions to send the packets, one for each flow. However, the relay node r can exploit the broadcast nature of its output links and reduce the number of transmissions to one by XORing the two packets. The nodes d1 and d2 decode the coded packet by XOR-ing p1� p2 with the overheard packets, p2 and p1, respectively. In random linear coding, the relay nodes create coded packets of the form åki=1aipi, where ai is a random coefficient chosen over a finite field, and pi’s can be coded or uncoded packets. Assume that the delivery rate of all of the links in 1.4(b) is 0.5. Each source node generates four random linearly coded packets and sends them. Two linearly independent packets from each session are received by the relay node r. Then, the relay node generates four random coded packets for each session 6 1Pouya Ostovari,1Jie Wu, and2Abdallah Khreishah (a) Network coding Local Global RLXOR RLXOR Network coding Inter session Intra session (b) Fig. 1.5 Classification of network coding approaches. (1.4(c)). Each destination receives two linearly independent packets. The decoding process is similar to solving a system of linear equations. From another view, we can classify network coding as local or global coding. In local network coding, a relay node sends the coded packets such that the next hop nodes are able to decode the coded packets. Then, the next hop nodes decode the coded packets and use the same policy to code the packets. Therefore, in a multi-hop transmission, hop-by-hop coding and decoding is performed. In contrast, in global network coding, the intermediate nodes do not perform decoding; they just code the coded packets again. At the end, when the destination nodes receive enough packets, they will be able to decode them. Usually, local network coding protocols use XOR coding, and global protocols perform random linear coding. As described in the introduction, network coding can be inter-session or intra- session. Inter-session network coding allows the relay nodes to code packets from the same session (source) to solve the bottleneck problem, and to reduce the number of transmissions (1.4(a)). On the other hand, in intra-session network coding, the re- lay nodes code packets from the same session to make the importance of the packets the same. Intra-session network coding is a natural way to address the packet loss problem in wireless networks (1.4(b) and (c)). Figure 1.5 shows our classification of network coding methods. 1.3 Network Coding Methods for Unicast Applications In this section, we describe some of the proposed network coding approaches for unicast application. We categorize the methods based on their methodologies, which are inter or intra-session network coding. Then, we compare the methods and sum- marize their advantages and drawbacks in the following sections. 1 Network Coding Techniques for Wireless and Sensor Networks 7 1.3.1 Inter-Session Network Coding COPE. A practical forwarding architecture, called COPE, is proposed in [6] which increases the throughput of wireless networks. This paper addresses the case of uni- cast traffic: dynamic and potentially bursty flows. COPE incorporates three main techniques, opportunistic listening, opportunistic coding, and learning neighbors’ states. In COPE, the nodes snoop on all communications and store the overheard packets for a limited period of time. The nodes broadcast reception reports to tell their neighbors which packets they have in their buffers. On the other hand, in the network coding phase, a node may have multiple choices for coding. However, the goal is to maximize the number of packets delivered in a single transmission, while making sure that all next-hops are able to decode the coded packet, so that they re- trieve their respective packets. When it comes to learning a neighbor’s state, COPE does not rely solely on the reception reports, since they may get lost or arrive late. For this reason, the delivery rate of the links are computed and broadcasted period- ically. A forwarder node in COPE works as follows. First, it selects a packet at the head of the forwarding queue. Then, it sequentially selects another packet in the queue, and computes the decodability probability of the packets at the next-hops when the packets are coded together. If the decodability probabilities at all of the next- hop nodes are greater than a given threshold, the relay node will code the packets together. Assume that in Figure 1.6, the next-hops for the packets from nodes s1, s2, and s3 are nodes d1, d2, and d3, respectively. Also, assume that the delivery rate of the shown links is 1, but the overhearing probability between the s nodes and d nodes is 0.8. The node r has received packets p1, p2, and p3 from nodes s1, s2, and s3, respectively. First, the relay node selects packet p1. Then, it computes the decodability probability of the coded packet p1� p2 at the respective next-hops of packets p1 and p2, d1 and d2. This probability is equal to 0.8. Assuming that the coding threshold is equal to 0.8 (this is the default value in [6]), COPE allows these packets to be coded together. Then, the relay node checks the decodability probability when p3 is coded with p1 � p2. For all next-hops, this probability is equal to 0.64, which is less than the threshold. Thus, p3 cannot be coded with the packet p1� p2. With the current sensor nodes’ technology, COPEmight not much appropriate for sensor networks. First, the nodes in COPE should snoop on all communications and store the overheard packets in their buffer, which is not practical in WSNs, because of the power and memory limitations. Second, the reception reports of the packets and the delivery rate of the links should be broadcasted in COPE periodically; this results in large amounts of power consumption in WSNs. Centralized Approach. A network coding-aware routing method is proposed in [14] to achieve optimal throughput. In contrast with COPE, in which the routing and coding algorithms are separate, the proposed mechanism in [14] is a cross-layer approach. The authors argue that when the paths of two flows are far apart (the flows pass through nodes that are far from each other), the interference between them is minimized. On the other hand, choosing close flows paths increases the 8 1Pouya Ostovari,1Jie Wu, and2Abdallah Khreishah r ݀ʹ ݀ͳ ݀͵ ݏʹ ݏͳ ݏ͵ ݌ͳ ݌ʹ ݌͵ Fig. 1.6 COPE approach. coding opportunities. Therefore, a trade-off between coding opportunity and conflict should be performed. A conflict graph is used in this work to model the interference between the links, and linear programming is used to find the optimal solution for the joint routing and network coding problem. The main drawback of this work is that the authors do not consider all of the possible overhearing cases between the nodes. In the same way as the COPE approach, this approach is not suitable for sensor networks. Distributed Approach. The problem of energy efficient opportunistic network coding for multiple unicast flows is addressed in [15]. The proposed inter-sessions network coding method, which is referred to as COPR, decomposes multiple unicast sessions into a superposition of multicast and unicast sessions in wired networks, with coding within each session (note that these sessions are artificial, and they differ from the original sessions). The network is modeled as a directed hypergraph, and the achievable rate region of one-hop XOR network coding is determined under a primary interference model. To simplify the network operation, the authors propose a back pressure algorithm for dynamic scheduling that does not optimize overheard flows. Network coding opportunities are not fully exploited in TCP flows over wireless network coding, due to the bursty behavior of the flows. Rate mismatches between the flows reduce the coding opportunities since the intermediate nodes may not have enough packets from different flows to code together. [16] addresses this problem by proposing coding-aware queue management for unicast flows. The authors formu- late congestion control as a network utility maximization problem and solve it via a distributed scheme. Using the optimal solution, a network coding-aware queue man- agement scheme at intermediate nodes (NCAQM) is proposed, which stores coded