{'fraction_non_alphanumeric': 0.023727516264829697, 'fraction_numerical': 0.0077087092012465145, 'mean_word_length': 4.517948717948718, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
CORMEN: Coding-Aware Opportunistic Routing in Wireless Mess Network

These Network Coding improves the network operation beyond the traditional routing or store-and-forward, by mixing of data stream within a network. Network coding techniques explicitly minimizes the total no of transmission in wireless network. The Coding-aware routing maximizes the coding opportunity by finding the coding possible path for every packet in the network. Here we propose CORMEN: a new coding-aware routing mechanism based on opportunistic routing. In CORMEN, every node independently can take the decision whether to code packets or not and forwarding of packets is based on the coding opportunity available.


INTRODUCTION
Network Coding [1] has emerged as promising method to increase the network throughput and reliability. Network Coding breaks the conventional store and forward approach of transmission in packet based network. Network coding offers the flexibility of encoding different packets at the intermediate node and transmits it in a single transmission. The receiver node can decode it and extract the specific packet destined for it. The basic idea of network coding is illustrated in Fig. 1 where nodes A, B and C share the common wireless medium. Consider a scenario where nodes A and node C have to exchange some information. Due to the channel constraints only one node can transmit at any given time. The traditional way of accomplishing this information exchange is as follows. Node A sends its packet p1 to the relay node B. The node B forwards this packet to node C. Similarly, node C sends its packet p2 to node B which in turn forwards it to node A as shown in the Figure 1(a). This involves a total of four transmissions. Now, consider the scenario where network coding is applied to reduce the number of transmissions. The node A and node C transmit packets to central node B sequentially (two transmissions). The node B, instead of directly forwarding each packet to its destination, XOR's the two packets and broadcasts the result as a single packet in the shared medium as shown in the Figure 1(b). Both nodes A and C know their own packet (p1 and p2, respectively) that originated from them. They can therefore retrieve the unknown packet by XORing the known packet with broadcast packet. For example, node A on receiving (p1⊕ p2) performs the operation p1⊕ (p1⊕ p2) to obtain p2. Similarly, node C retrieves packet p1. This entire process takes three transmissions as opposed to four transmissions as is the cse in traditional routing.
Opportunistic Routing differs from traditional routing. It exploits the broadcast nature of wireless medium and differs the route selection after packet transmission. Each packet holders chooses a subset of its neighboring nodes as a potential next hope and among those which one have the best node to the destination will be selected as next sender. The main benefits of opportunistic routing is that it can combine multiple weak link into strong link and reduces the retransmission rate especially in wireless medium In this paper, we are presenting a new routing algorithm which is based on opportunistic routing as well as network coding. The main idea of this algorithm to find a path with minimum delay to the destination which is coding-aware. multicast communication. The Fragouli et. al. [2] provides the brief introduction, benefits and applications of network coding in different areas. The Fragouli et. al. [3] describes the various problems of traditional wireless network and explores to solve these problems by network coding. The Li et. al. [4] discuss Linear Coding , which consider a block of data as a vector over a certain base field and allows a node to apply a linear transformation to vector before passing to it on. They develop a greedy algorithm for code construction. For wireless networks the Katti et. al. [5] proposes COPE, the first practical XOR coding system and demonstrates the throughput gain via implementation and measurement. In COPE every node is in promiscuous mode and overhears the transmission of all other nodes. It uses reception report in their neighborhoods to let the neighbors learn about the packets they currently have. However routing in COPE is independent of coding opportunity. Sengupta at. el. [6] theoretically showed that further coding gain as well as throughput can be achieved if routing is coding dependent.
COPE uses expected transmission count metric (ETX) [7] as its routing function .The ETX [7] metric incorporates the effects of link loss ratios , asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. The ETX of link measures by expected number of transmissions and retransmissions required by to reliably send a packet across the link. Let d f be the forward delivery ratio, is the measured probability that a data packets successfully arrives at the recipient and d r the reverse delivery ratio, is the probability that ACK packet successfully received. The expected probability that a transmission is successfully received and acknowledged is d f xd r . Each node measures the delivery rate of its link to and from its neighbor by broadcasting one probe packet every second and counting the number of probes received in the last 10 seconds .The ETX metric is calculated by ETX = 1 / (d f xd r ). The ETX of a route is sum of the ETX for each link in the route. Opportunistic routing is introduced in [8,9] The Extremely Opportunistic routing protocol ExOR [8] introduced the concept of being opportunistic when the wireless link are lossy. However it requires lots of coordination among the nodes.
Coding-aware routing was proposed in [6,10,11] In [6] authors provide a theoretical framework for investigating the relation between the coding and routing. A localized coding-aware routing algorithm was proposed in [11]. MORE [12] coding-aware routing in Intra-Flow network coding. DCAR [10] is a distributed approach to codingaware routing. But it chooses a pre-established path i.e. route is selected before sending of packets. But the coding opportunity is depend on traffic flows and at initial stage there is no way to predict the traffic pattern in most wireless networks. CORMEN dynamically select the path in a node-by-node manner during packet forwarding phase.
As a result it maximizes the coding opportunity as well as overall network throughput.

PROPOSED ROUTING ALGORITHM
The routing algorithm in network coding face challenges in finding route which have the highest coding opportunity. The main problem is to determine the exact coding capability at each node in the network. This allows identification of the regions in the network that are more suitable to deploy network coding. This information then can be used in the design of the routing scheme to optimize the network performance. The goal of coding-aware routing is to find out the coding opportunity while forwarding the packet to shortest coding possible path. Design of this algorithms is based on opportunistic routing and the routing metric is depend upon the coding opportunity arises in the intermediate node.

Routing Metric Selection:
The routing metric must be aware of coding opportunity available at intermediate node. It must choose the best coding possible path. It should not be like that it only chooses the path which has coding opportunity but the route is very long to the destination as well as chooses the shortest path ignoring the coding opportunity.
For Example: consider the case in Fig 2. In this scenario there are two packets P1 and P2 .Packet P1 has source A and destination E. P2 has source C and destination A. If we consider the all links have equal good quality for Packet P2 have two paths CBA and CDA to reach the destination. But P2 shouldn't choose the path CBA as A path have the coding opportunity at node D. Now consider the second scenario in Fig 3. Packet P1 has source A and destination D. P2 has source E and destination A. Here for packet P2 the EDCBAH path is coding possible but this path is much longer than the noncoding path EFGH. In this case the non-coding path has less delay and more throughputs.
So, the routing metric should select the path in such a way that it not only select the coding possible path but also select the shorter coding impossible path which have higher throughput.

Forwarding Node Selection:
Forwarding nodes are the nodes that will accept the packet broadcasted by the sender and among those nodes one will further forward the packet. Forwarding nodes should be selected in advance. This is necessary because the numbers of duplicate transmission and co-ordination overheads tend to increase with number of forwarding nodes. The information of the forwarding nodes store in each packet.

Duplicate Transmission Avoidance:
When a sender sends a packet multiple nodes hear the packet. So it must ensure that only the best forwarding node will send the packet to the destination, others will drop the packet.

Coding Correctness:
The throughput of the algorithm mainly depend upon the how efficiently and correctly an intermediate node code packets. A node only codes those packets which are decodable at the destination. One most important thing is that the intermediate node must take the coding decision independently without doing any interaction with the neighboring nodes.

Forwarding Node Selection:
A sender selects the forwarding nodes for every packet individually. Selection of the forwarding nodes must obey following conditions.  The ETX between the sender and forwarding nodes must be below threshold limit to ensure of good quality link.
 The forwarding nodes must be adjacent to the shortest path to avoid diverging of path. So each forwarding nodes is close to at least one node on the shortest path.
 The ETX of link between any pair of forwarding nodes within a threshold. This ensures that the forwarding nodes have good connectivity among themselves and to the nodes on the shortest path.

Shortest Path Selection:
The shortest path is selected between the source and destination in terms of ETX [5] Metric. This shortest path may or may not be the actual path of a packet. But actual path whether it is coding possible or not must be near to the shortest path. This is required not to diverge the path and avoiding unnecessary duplicate transmission.

Coding of Packets:
The overall throughput of the algorithm is depending upon the how efficiently and correctly the node codes the packets. To ensure that the intermediate node code only the proper packets i.e. packets which are decodable at the next hop, it must check the following conditions before coding packets.
Let F(c,p) = List of Forwarding nodes for packet 'p' at node 'c'. T(c,p) =Node traveled by packet 'p' to reach node 'c'. O(c,p)}=List of overhearing node of packet 'p' as it reaches to node 'c'. (Overhearing Nodes are the list of nodes who listen and stores the packet when a sender sends it . It is actually the sender's Forwarding Nodes.).
Two packets p1 and p2 will be coded at a node 'c' if anyone of the following conditions holds.

Setting Forwarding Timer:
Forwarding timer is the most important aspect of CORMEN. The timer is used to avoid duplicate transmission, but it affects the overall throughput of the algorithm. After receiving a packet every node sets a timer for each packet. The value of the timer is depend upon the coding opportunity at that particular node at a particular instant as well as the best route in terms of ETX [7] to the source and destination.
Let 'n' be the no of packets that can be coded at the node and 'i' is the order of the node in the forwarding node set. Then the forwarding timer t f will be JOURNAL OF COMPUTING, VOLUME 2, ISSUE 6, JUNE 2010, ISSN 2151-9617 HTTPS://SITES.GOOGLE.COM/SITE/JOURNALOFCOMPUTING/ WWW.JOURNALOFCOMPUTING.ORG 74 t f = i/n 2 * ETX destination

Forwarding of Packets:
Every node maintain two different output queue one is for sending packet originated from the node itself and other is for forwarding of packet received from other node. CORMEN applies two different methods because packets at the source node need not to be coded. So checking coding opportunity is irreverent. While packets received from other node we must check coding options.
When a source is sending a packet, it simply first select Then it sends the packet as in traditional network and store the packet in a packet pool for some amount time.
When an intermediate node receives a packet it first checks whether it is a coded packet or not. If it is coded packet it checks whether it is one of the recipient by seeing the recipient list. If it is not in the recipient list it discards the packet. By doing this it will reduce the unnecessary computation overhead in the node. If this node is in the recipient list, it decodes the packet and checks if it is the destination node for these packets. For which packet it is destination node it sends the acknowledgment. If it is not the destination node, it en-queue the packet in the output queue and sets forwarding timer for the packets. Now updates the forwarding node set and shortest path to the actual destination. It the waits for a probe packets to receive i.e. if there is some other node which have more coding opportunity then that node have a smaller timer. So it will send the probe packet earlier. If the node receives probe packet it will remove the packet from the queue and store the packet in the packet pool. If the timer expires and it will not receive any probe packet, the node sends a probe packet. It the coded the all possible packets and forward it.

SIMULATION AND PERFORMANCE EVALUATION
We simulate our proposed routing algorithm in NS2 [13] and compare the result with COPE. We simulate COPE from [5]. For simulation of CORMEN, we use IEEE 802.11 MAC, UDP implementation from standard NS distribu-

Fig 5: Flowchart: Intermediate Node forwards a packet
tion. We keep the physical layer bit rate 1 Mbps and use two-ray ground propagation model. We set the transmitting rate interval to 0.05 seconds. Each node has 250 meters radio range and 550 meters carrier sense radius. Each data packet carries 1000 bytes of payload. The RTS/CTS mechanism of 802.11 is switch off in all our simulations.

Coding Header
A network coding header is constructed to keep necessary information in order to perform coding and decoding properly. We are integrating this header with the IP header. The parameters for these headers are  NC: It checks whether a packet is native or coded packet. If NC=0, 1 then its native packet. Either if NC = n (n! = 0, 1) then there is n nos of packet coded together.

Reference Scenario and Performance Metrics
We consider only grid topologies of different no of nodes for our performance evaluation. Nodes are placed at equal distance of 200 meters apart from each others. All the links between the nodes are considered to be lossless. We take 3 grid structures, 9 nodes of size 3x3, 15 nodes of size 5x3 and 25 nodes of size 5x5. Each grid structure have different traffic load. Following are the performance metric that is used to comparing our algorithm with COPE.
 Packet Delivery Ratio (PDR): Packet Delivery Ratio (PDR) is the quotient resulting from the number of successful delivered packets to those generated by sources within the simulation period. It is an important metric which indicates congestion level of the network. PDR measures the protocol performance from loss ratio experienced at the network layer that is affected by factors such as packet size, network load and effects of movement resulting in frequent topological changes. Higher PDR implies that packet loss rate is lower and protocol is more efficient from the perspective of data delivery. A point to note is that late packet received could be deemed useless even with high PDR.
 Average End-to-End Delay: There are lots of possible delays caused by buffering during route discovery latency, queuing at the interface queue, and delay due to coding of packets at the node, retransmission delays at the MAC and propagation and transfer time. End-toend delay is the overall time difference from transmitting packets from a source to the arrival of packets at the destination node. Average end-to-end delay can be computed as time difference between every packet sent and received, dividing by the total no of packets received at the destination. This metric describes the packet delivery time: the lower the end-toend delay the better the application performance.
 Average Throughput: Network throughput determine the amount of data successfully received at the destination per unit time. Average network throughput can be calculated by the following

Result Analysis
In 3x3 grid structure there are total 9 nodes and 7 nos of CBR data flows starting at different simulation time. First data flow was started at 30 seconds of simulation time and others are starting at an interval of 20 seconds. So, as the time increases the load of the network also increases. Our main aim is to see the behavior of the network at light traffic as well as heavy traffic. We observed that the coding opportunity increases in heavy traffic. As a result, both CORMEN and COPE achieve higher throughput with increase of traffic. But as the traffic increase in the network due to coding of packets at node the end-to-end delay also increases. In Fig.5 (a) we showed the throughput of COPE and CORMEN. Graph shows that the CORMEN has higher throughput than COPE. Packet delivery ratio Fig.5 (b) is also slightly better than COPE. Average end-to-end delay is also lesser than COPE. Fig. 5(c) shows this. In 3x5 grid structure total 11 nos of CBR flow and in 5x5 grid structure 14 nos of CBR data flow is there. The result of these scenarios is shown in Fig. 6 and Fig. 7.
Here also CORMEN is performing better than the COPE.

CONCLUSION
In this paper, we propose CORMEN, a coding-aware routing algorithm for wireless network. It searches the possible coding opportunity in the route selection process and forwards the packet through the best route. Coding decision can be taken by each node individually, not much synchronization is required among nodes.