# «Chapter 3 Opportunistic Routing in Wireless Mesh Networks Amir Darehshoorzadeh, Lloren¸ Cerd`-Alabern and Vicent Pla c a Contents 3.1 Introduction ...»

3.4.2 Opportunistic Any-Path Forwarding (OAPF)

Cs,d ← Cs,d ordered by cost the best candidate is the one that reduces the most the expected number of transmissions from s to the destination (line 14). Node s adds the best candidate to its actual CS (Cs,d ) and removes it from its initial set. Note that to ﬁnd the best candidate in each iteration, candidates should be ordered according to their EAX. It tries again to ﬁnd the best node from its new initial CS. This process is repeated until there is not any other suitable node to be included in the candidates set of s, or the number of candidates in the Cs,d reaches the maximum number of candidates (ncand). Finally, the CS is ordered by EAX of each candidate.

Now assume that node S in ﬁgure 3.7 wants to ﬁnd its CS using OAPF. First, it creates ˆ its initial CS CS,D. Since the ETX of all its neighbors (A, B and D) to the destination D is ˆ less than ETX(S,D) (see table 3.2) then, the initial CS of S is CS,D = {A, B, D}. Note that, all nodes in the initial CS must select their CSs before S. In table 3.3 we summarize the CS and related expected number of transmissions for node A and B.

** Table 3.4 shows the process of selecting candidates for the source S using OAPF.**

In the ﬁrst iteration source selects B as its candidate. Because B is the one that reduces the expected number of transmissions from S to D the most. Then, node B is removed from initial CS. The CS of S in the ﬁrst iteration would be CS,D = {B}. In the section iteration of while-loop in algorithm 2 (line 12-24), source looks for the second candidate from the remaining potential Table 3.3: Candidates set of A and B in ﬁgure 3.7 using OAPF

ˆ candidates in CS,D = {A, D}. As we can see in table 3.4, the second candidates that reduces the expected number of transmissions from S to D the most is D. Therefore the ﬁnal CS for source using OAPF is CS,D = {D, B} with EAX equal to 3.46.

3.4.3 Least-Cost Opportunistic Routing (LCOR) The goal of this algorithm is to ﬁnd the optimal CSs. Recall that the optimal CSs are the sets that minimize the expected number of transmissions from the source to the destination.

LCOR [15] uses EAX as the metric to select candidates as shown in Algorithm 3. It works similar to the classical distributed Bellman-Ford algorithm.

The algorithm proceeds iteratively and at each iteration an exhaustive search over all possible CSs is carried out. It starts by initializing the cost (EAX) of each node v to reach the destination d (lines 1–4). Since in the initializing phase the CSs for all nodes are empty, the cost to reach the destination for all nodes is equal to ∞ (costcurr (v) ← ∞). Note that the cost for the destination d is always equal to 0 (costcurr (d) ← 0).

To ﬁnd the optimal CSs in each iteration, and for every node v except the destination, the algorithm runs an exhaustive search over all possible subsets of N (v) with cardinality not exceeding ncand (line 9). The algorithm terminates when the cost to reach the destination does not change for all nodes in two consecutive iterations (lines 12–17).

In each iteration the algorithm checks for all the nodes but the destination, all subsets of their neighbors with cardinality ≤ ncand. Therefore, for dense networks the computational cost of the algorithm increases extremely fast due to the combinatorial explosion of the exhaustive search of line 9. In section 3.9.8, we will carry out an experimental evaluation of the computational time.

Applying LCOR on the topology in ﬁgure 3.7 yields as a result CS,D = {D, A} with the expected number of transmissions equal to 3.36.

Algorithm 3: Candidate.selection.LCOR(s, d, ncand).

forall the v in the network \{d} do costcurr (v) ← ∞; costprev (v) ← ∞

until ﬂag == TRUE Cs,d ← Cs,d ordered by costcurr 3.4.4 Minimum Transmission Selection (MTS) MTS [29, 45] is another algorithm which selects the optimal CSs for any node to a given destination d that minimizes the total expected number of transmissions. Like LCOR, this algorithm proceeds iteratively and uses EAX as the metric for selecting the candidates sets.

The general idea of MTS consists of moving from the nodes closest to the destination d (in terms of the EAX) backwards to the source. Note that, the closest node to the destination has the least EAX. MTS uses the following principle: if u and v are neighbors and EAX(Cu,d, u, d) EAX(Cv,d, v, d), then adding u and its candidates to the CS of node v will reduce the expected number of transmissions from v to d, i.e. EAX(Cv,d ∪ {u} ∪ Cu,d, v, d) EAX(Cv,d, v, d).

Given a general wireless topology, for a given destination d initially let S be the set of all nodes except d. The MTS algorithm for computing the optimal CS from any source node v ∈ S to d is described in pseudo-code in algorithm 4. The algorithm starts by initializing the cost (EAX) of each node v to reach the destination d (lines 2–10 in Algorithm 4). If d is one of the neighbors of v, then v adds the destination to its CS and the cost to reach the destination (cost(v)) is set to qvd, where qvd is the delivery probability of link between the two nodes v and d (note that EAX(Cv,d, v, d) = qvd when Cv,d = {d}).

At each subsequent iteration while S is not empty the algorithm looks for the node minnode with minimum cost in terms of the expected number of transmissions to the destination (line 12). The neighbors of minnode, N (minnode), add minnode and its candidates to their CS and minnode is removed from S. This process is done by means of the function merge, which combines both CSs and order them in increasing order of their cost (EAX).

Algorithm 4: Candidate.selection.MTS(S, d,ncand).

Data: S is the set of all nodes except d.

cost(d) ← 0 forall the v ∈ S do if v ∈ N (d) then cost(v) ← qvd

Note that proceeding this way, MTS ﬁnishes in N − 1 iterations, where N is the number of nodes in the network.

In the description of MTS given above, the optimal CSs for all the nodes in the network are computed assuming there is not any limitation in the number of candidates, as proposed in the original version of this algorithm.

In order to limit the maximum number of candidates, maintaining the optimality of the algorithm, we have added the lines 19–22. Here the nodes are visited in increasing order of their cost, and an exhaustive search is done over all subsets of the CSs with cardinality ≤ ncand. Since MTS ﬁrst ﬁnd the optimal CSs in the case of inﬁnite candidates (i.e. all possible nodes can be selected as candidates), and then we look for the best subset of candidates sets with at most ncand elements, the ﬁnal CSs will be the optimal CSs.

Like the previous algorithms, we apply MTS in the example of ﬁgure 3.7 to ﬁnd the CSs. According to MTS algorithm S = {S, A, B}. The cost of nodes S, A and B to the destination D is 1/0.15, 1/0.4 and 1/0.31, respectively. The result of each iteration of the MTS algorithm is shown in table 3.5, where the ﬁrst item in each cell is the current best CS for the corresponding node, and the second item is the current smallest expected number transmissions using that set. In the ﬁrst iteration since the EAX of A is the minimum (EAX({D}, A, D) = 2.5), it removes from S. Then, MTS adds A and its candidates (CA,D = {D}) to the CSs of all neighbors of A, i.e, nodes S and B (see iteration 1 in table 3.5).

Note that in each iteration the EAX of each node is updated according to the new CS. In Table 3.5: Candidates Set selection for the ﬁgure 3.7 using MTS

the second iteration the node with the minimum EAX is B (EAX({D, A}, B, D) = 2.79);

it is removed from S and its candidates CB,D = {D, A}, and B are added to the CSs of all neighbors of B which are still in S, i.e, node S. Now, each node has a set of candidates to reach D. Note that, until this step there is not any limitation on the number of candidates.

Doing an excursive search with constraint ncand = 2 over the sets which are found by the original version of MTS results in the optimum CS with length at most equal to 2.

We summarize the CSs and EAX of each node in ﬁgure 3.7 using diﬀerent algorithms under study in table 3.6. The ﬁrst item in each cell is the CS for the corresponding node, and the second item is the expected number of transmissions (EAX) of the corresponding node using the said set. As we can see in table 3.6 the algorithms that use EAX to select CSs have better expected number of transmissions than ExOR which uses ETX for selection of candidates.

**3.5 Network Coding Opportunistic Routing**

MORE [11] is an OR protocol that can be used in both unicast and multicast scenarios. It deploys the advantages of network coding to improve performance of OR in wireless multicast networks. Duplicate transmissions are avoided by randomly mixing packets before forwarding.

The sender creates a linear combinations of packets and broadcasts the resulting packet after adding a MORE header containing the CS. Each receiving node discards the packet if it is not linearly independent from the other packets received before, or if its ID does not appear in the candidates list. Otherwise, it linearly combines the received coded packets and rebroadcasts the new packet.

COPE [20, 21] is a practical network coding mechanism for supporting eﬃcient unicast communication in a wireless mesh network. It employs opportunistic listening to enable each node to learn local state information and encoded packet broadcasting to improve the network throughput. It exploits the shared nature of the wireless medium which broadcasts each packet in a small neighborhood around its path. Each node stores the overheard packets for a short time [20]. It also tells its neighbors which packets it has heard by annotating the packets it sends. When a node transmits a packet, it uses its knowledge of what its neighbors have heard to perform opportunistic coding; the node XORs multiple packets and transmits them as a single packet if each intended next-hop has enough information to decode the encoded packet. Motivated by COPE, several other coding-aware routing mechanisms have been proposed [41, 27], which are aimed at improving the network throughput by combining routing with inter-ﬂow network coding. However, neither COPE nor its variants consider the opportunistic characteristic of a wireless channel in packet delivery and the dynamic availability of network coding opportunities at a network node, which can be caused by traﬃc and network dynamics. This largely limits their capabilities for improving network throughput.

CORE [43, 42] is a coding-aware OR mechanism that combines opportunistic forwarding and localized inter-ﬂow network coding for improving the throughput performance of a MWN network. Through opportunistic forwarding, CORE allows the next-hop node with the most coding gain to continue the packet forwarding. Through localized network coding, CORE attempts to maximize the number of packets that can be carried in a single transmission. When a node has a packet to send, it simply broadcasts the packet, possibly encoded with other packet(s), which may be received by some of the candidates in its CS. The candidates receiving the packet collaborate to select the best candidate among them in a localized manner, which is the one with the most coding opportunities. This forwarding process is repeated until the packet reaches its intended destination. In CORE, geo-distance metric and timer-based coordination have been used to select and coordinate the candidates, respectively.

**3.6 Geographic Opportunistic Routing**

Geographic Random Forwarding (GeRaF) [50] is a forwarding protocol which selects set of candidates and prioritizes them using geographical location information. Only those neighboring nodes closer to the destination than the sender can be candidates. The priority of selected candidates is based on their geo-distances to the destination. The CS and prioritization can easily be implemented via an RTS-CTS dialog at the MAC layer, which also ensures that a single forwarder can be chosen.

GOR [47] is used in geographic routing scenarios and adopts timer-based coordination with local candidates order. Authors showed that giving the nodes closer to the destination higher priority is not always the optimal way to achieve the best throughput. They proposed a local metric named expected one-hop throughput (EOT) to characterize the local behavior of GOR in terms of bit-meter advancement per second. Based on EOT, which considers the coordination overhead, they proposed a candidate selection scheme.

S.Yang et. al. [44] proposed a protocol called Position Based Opportunistic Routing, POR. In POR, when a source wants to send data packet to the destination, it ﬁnds its CS according to the distance between its neighbors and the destination. The neighbor which the nearest to the destination will have the highest priority. They ﬁxed the maximum number of candidates in each node to 5. When a candidate receives a packet, it checks its position in the CS and waits for some time slots to forward the packet. If it hears the same packet being sent by the other nodes, it will simply discard the packet.

3.7 Multicast Opportunistic Routing Multicast is an important communications paradigm in wireless networks. The availability of multiple destinations can make the selection of CSs and the coordination between candidates complicated. There are few works that have tried made to adapt OR for multicast scenarios.

In [22] the source ﬁrst creates the shortest path tree to reach all destinations based on the ETX of each link. Then the nodes not only receive packets from their father in the tree, but also can overhear packets from its sibling nodes. It uses random linear network coding to improve multicast eﬃciency and simplify node coordination.

The authors in [38] used a Steiner tree based on ETX and data packets were forwarded through the links using OR. Their protocol constrains the nodes involved in routing a packet to be near the default multicast tree. The average EAX of each candidate to reach a sub-group of destinations is used as the cost of reaching to multiple destinations.