Energy-Efficient Routing In Sparse Networks

Routing in sparse networks results in relatively long packet delivery delays and is unreliable. Thus, sparse networks are not an appropriate networking solutions for applications in which delay delivery is of critical importance. However, some applications can tolerate substantial amount of delay. Networks which can support communication for such applications are referred to as the Delay-Tolerant Networks (DTNs). Epidemic Routing Protocol (ERP) has been proposed and widely used for routing in DTNs. ERP is based on the concept of packet flooding - a node that carries a packet transmits (i.e., replicates) the packet to every node that it encounters. Thus, the numbers of copies of the packet rapidly increases. This type of routing results in the shortest possible packet delivery delay and in high packet delivery probability. However, these results come with strict assumptions that the network nodes have sufficiently large amount of energy and storage. In case where the network sequentially routes multiple packets, increasing the number of copies of the packet has its disadvantages. First is the excessive amount of energy used for transmissions. When nodes have limited amount of battery energy, increased number of copies eventually results in faster depletion of the batteries of the network nodes, reduction in the number of active nodes, and in reduced network lifetime. Second is the amount of memory used for packet storage. A node is likely to receive many different packets which will pile up the memory before the node encounters the sink. When its memory is full, the node should either remove a packet from its memory, or not receive another packet. Either way, this results in less packet copies and decrease of packet delivery probability. This study analyzes the ERP for two different cases and shows how to overcome the disadvantages by modifying the ERP. In case when the nodes have limited battery energy, minimizing and equalizing the energy expenditure at the nodes efficiently increases the network lifetime. In case when the nodes have limited storage, using linear combinations of multiple packets increase the packet delivery probability without any major cost of energy or storage