Multihop Wireless Networks: Opportunistic Routing

2.4 Conclusions

In this chapter, we generalized the definition of EPA for an arbitrary number of forwarding candidates in GOR. Through theoretical analysis, we first showed that the maximum EPA can only be achieved by following a relay priority rule—giving the forwarding candidates closer to the destination higher relay priorities when a forwarding candidate set is given. We gave the analytical result of the upper bound of the EPA that any GOR can achieve. We found that the node set achieving the maximum EPA with r nodes is contained in at least one node set achieving the maximum EPA with r + 1 nodes. We also showed that giving an available next-hop neighbor set with M nodes, the maximum EPA achieved by selecting r nodes is a strictly increasing and concave function of r and we showed how the candidates should be selected to achieve the maximum EPA. We further showed that increasing the maximum EPA is consistent with increasing the one-hop reliability. These unveiled properties of the local behavior of GOR will enable us to design efficient local routing metric and candidate selection and prioritization algorithms to approach the global optimum performance.

We further introduce the least cost opportunistic routing and important properties about it. Two polynomial algorithms that find shortest anypath for LCOR are described. These two algorithms are based on the proved properties.

 

 

1 For simplicity, we denote a node using its subscript in this proof.