Performance modeling of three-hop relay routing in Intermittently Connected Mobile Networks

A significant amount of works has been done to model the delivery performances in Intermittently Connected Mobile Networks (ICMNs). However, available works considered either the two-hop relay routing or the epidemic routing, which actually represent two extreme cases of the message delivery process in ICMNs. In this paper, we take one step ahead and focus on the three-hop relay routing where each message travels at most three hops to reach the destination. Under such a scheme, besides that the source can send a message copy to each node it meets, a relay which receives the message directly from the source can also replicate the message to other nodes, while a relay node which receives the message from another relay can only forward the message to the destination. In order to characterize the complicated message delivery process under the three-hop relay routing, a multidimensional Markov chain theoretical framework is developed. Based on the Markov chain framework and block matrix theory, closed-form expressions are further derived for the important message delivery delay and delivery cost. Extensive numerical results are also provided to explore the achievable delivery performances under the three-hop relay.