Trajectory Optimization of Packet Ferries in Opportunistic Social-Based Machine-to-Machine Networks

Abstract

Machine-to-machine (M2M) communication is an emerging paradigm to connect a large number of devices through wireless technologies. In recent application scenarios, devices are normally carried by people in social contexts. Like the behavior of people, the moving activity of devices always happens in a specific area, which corresponds to some specific communities. How to guarantee the higher packet delivery ratio while reducing forwarding delay in such M2M networks is a challenging issue and has not been well addressed yet. In this paper, we put some special mobile devices (called postmen) in the opportunistic social-based M2M networks and their main responsibility is to carry packets for normal devices which belong to specific communities. Our work focuses on the optimization of the moving trajectory by considering the minimum transmission delay. We formulate the optimal issue into semi-Markov Decision Process model. The decision process includes two parts: packets-choosing strategy and trajectory of packet-ferrying determination strategy. By maximizing the individual reward of a postman, its optimal trajectory will be found. Furthermore, the proposed solution guarantees the packet delivery ratio and delay for isolated communities. Simulation results show that the proposed packet-ferrying solution outperforms the two existing ferrying solutions in terms of packet delivery ratio.

1. Introduction

With the development of wireless technology [1–3], the progress in short range networking, growth of wireless mobile networks, and advances in device networking have allowed the development of a new technology, machine-to-machine (M2M) communications [4], which has recently received considerable attention [5, 6]. Features such as self-organization, ease of deployment, low cost, and infrastructurelessness bring to wireless M2M networks the advantages of robustness, easy maintenance, economy, and flexibility. Therefore, M2M networks are envisioned to be the key technology for next generation wireless networks [7]. An M2M network consists of a large number of self-organized and self-configured nodes. In some real application scenarios, nodes are carried by people; the behavior of human being reflects on the node. Then, these nodes which are carried by people have the social property.

As we know, mobile social network belongs to a typical application branch of M2M network, so, we call it social-based M2M network. Due to the sparse distribution of nodes, it is difficult to guarantee permanent forwarding path between the source and destination nodes [8]. In such case, nodes need to cooperate with each other to achieve the task of multihop forwarding. In mobile social networks, normally, mobile nodes are carried by people [9]. Therefore, the behavior and moving activity of nodes are similar to human activities, which are usually in specific areas [10]. For instance, university students always move around the university campus. From a sociological point of view [11], we call the activity area community.

In a network which is composed by some communities, the communities are typically isolated from each other. For example, the source and destination nodes belong to the same community; it is easy to achieve the goal of packet delivery, so this issue is not discussed in our work. This paper only considers the situation where the source and destination nodes belong to the different communities. In most existing solutions, source node prefers to choose the neighbor node which has higher probability to reach the destination [12] or the nodes which have higher cluster coefficient [13]. However, there are some instinct limitations in these solutions, and the delivery ratio is difficult to be guaranteed.

Some researchers proposed to set particular mobile nodes (i.e., supernodes) to finish the forwarding task among the isolated communities [14, 15]. These supernodes do not belong to any community and they only need to take packets from different communities [16]. However, these solutions only consider the scenario of stationary nodes [17] or assume the supernodes move according to fixed routes. Packet ferry issue was first proposed in [17]; the authors only considered one ferry node works in sparse mobile wireless networks. The main idea of [17] is to introduce nonrandomness in the movement of nodes and exploit such nonrandomness to help forward packet between isolated communities for social M2M networks. In [18], ferry calculates the fixed trajectory which follows TSP algorithm according to the parameters of community such as coordinate. Then ferry moves along the concluded trajectory and forward packets. Since in different time slot community has different packet generate rate, the request of forward service is dynamic in each community. However, ferry only moves along the concluded trajectory neglecting the dynamic request. Thus, this algorithm wastes a lot forwarding ability of ferry and has very low efficiency. The authors of [19] start with a Markov Decision Problem (MDP) formulation which produces the optimal ferry route that minimizes the average data delivery delay. While this formulation, in principle, enables optimal ferry route design, it is numerically intractable for moderate to large size problems.

In this paper, we call a supernode as postman. Then, how to optimize the moving trajectory for a postman to forward packet efficiently is a key issue. Our basic idea is that, given a packet delivery ratio objective, we minimize the delivery delay as the basis of optimizing the moving trajectory of the postman. In our work, we assume the postman is rational. Towards the forwarding task, the only goal of a postman is to obtain the maximum reward. That is, when the postman forwards packets to a destination between communities, reward can be obtained. Meanwhile, we assume all packets have expired time (TTL) and the forwarding reward and the residual time of packet exist with linear and proportional relationship. It means, within packet TTL, if the postman delivers packet earlier, more reward can be obtained. Otherwise, the postman obtains nothing for a expired packet. To maximize the reward, postman would try to forward packets as soon as possible and reduce the delivery delay. When postman has taken several packets and some destinations are different, how to order the delivery sequence and further optimize the moving trajectory are the main goals in this paper. As we know, in sparse social-based M2M networks, the permanent link between isolated devices is hard to achieve. In such case, some researchers proposed the ferry based solution for packet delivery. And this approach has been proved that it is useful in the real application scenario. As for our proposed solution, the postman device makes moving decision based on the status of the isolated communities; it is fully distributed algorithm. There is no need to introduce any additional centralized algorithm or equipment. From these points, we can see that our proposed solution is useful and practical.

We formulate the optimal trajectory issue as a semi-Markov Decision Process to maximize the reward. The decision process is divided into two decision strategies. Firstly, when a postman arrives at a community, there are several packets that need to be forwarded in this community. Due to the buffer limitation and the requirement of successful delivery, the postman needs to make decision on which packets it would carry according to the attributes of packets. Secondly, after the above decision was made, the postman needs to decide how to move among the different destination communities, and optimize the packets delivery sequence and the moving trajectory. By optimizing the moving trajectory, our solution ensures the packet delivery ratio while reducing the delivery delay.

The remainder of this paper is organized as follows. Section 2 describes the problem formulation of our proposed packet ferry protocol and introduces our network model. In Section 3, we present the optimal model of postman mobility trajectory by using semi-Markov Decision Process. Section 4 models the multiple postman working scenario and concludes the optimal number of postmen which are working in the same network area. Section 5 provides our simulation results. We conclude our work in Section 6.

2. Problem Formulation

In this paper, we adopt the university campus as network model. According to the activity area of the people who belong to the university campus, we divide the entire campus into several subareas or communities, for example, library, dormitory, and so forth. In [14], the authors assume that in each community, there exists at least one mobile node which is appointed as gateway node. Furthermore, gateway nodes never move to the outside of the community. In practical scenario, it is difficult to find such special node to be gateway for the community. Furthermore, the buffer requirement and bandwidth overhead become too heavy for gateway node, since all the nodes within the same community send packets to it. Normally, in mobile social networks, mobile devices are carried by people, it is difficult to find such people who like to do such kind of voluntary job unselfishly. In comparison, this paper introduces one gateway with fixed position for each community. Its only mission is to store the packets which come from other nodes and forward the packets to the packet ferry. We assume that the gateway has the same communication ability as normal mobile node. In addition, each gateway is equipped with finite buffer. Since the number of communities is limited, the implementation of gateway node would not lead to too much additional cost for the entire network. I set one fixed position device for each community. All devices which are in the same community send the packets to this fixed position device. Ferry device only needs to know the location information of fixed position device; it also means the location of community is known for all ferry devices.

Regarding the normal mobile nodes in community, the communication radius is r  and the buffer size is b. Mobile node generates packet to the random destination within a fixed time interval (e.g.,  $\mathrm{\Delta }T$ ). In order to achieve the goal of packet transportation between different communities, we exploit some ferry nodes in the network. Since ferry node has only one mission of packet delivery, we call it as postman which moves among the communities. In the following section, we optimize the moving trajectory for postman by using semi-Markov Decision Process. By considering the real application scenario, we assume the buffer of postman is finite and the communication radius is r.

In order to describe our work more clearly, we make the following constraints for our network model.

First, all the packets are sent to the gateway of each community. In our work, we ignore the community-detection issues, which means each node knows its belonging community. Secondly, a postman knows the community that the packet should be ferried to. Note that this assumption needs a unique ID for each node. Within time interval  $\mathrm{\Delta }T$ , mobile node generates a packet and assigns destination randomly. In order to save buffer and bandwidth, we initialize active time for each packet, which is denoted by time to live (TTL). If the packet reaches destination before deadline, it is deemed as a positive transmission. In contrast, the transmission is negative and the packet would be erased without retransmission. When a postman reaches a gateway node, it communicates with the gateway node to exchange information. The moving velocity of postman is constant, and its buffer size is fixed and limited.

3. Optimized Trajectory for Postman

3.1. Design Framework

In this section, we discuss how to formulate the moving trajectory of individual postman into semi-Markov Decision Processes (SMDPS). By using the expected discount criterion of SMDPS, we conclude the optimal expression of decision function. Furthermore, based on the optimal expression, we conclude the optimal moving trajectory of postman. Our main goal is to minimize transmission delay of packet and, meanwhile, guarantee the required packet delivery ratio. Here, the optimal trajectory for postman is defined as the route by which the corrected packet is distributed to the destination gateway as quick as possible. We assume that postman is pursuing reward by ferrying packets. By combining packet TTL and reward of postman into consideration, the linear relationship exists between TTL and reward. That is, the less time a postman spends on delivering packet to the destination gateway before TTL, the more reward it would obtain. If the packet is expired, the postman gains nothing. In such case, we conclude the optimal moving trajectory of postman by maximizing the reward, which also means the packets are transmitted with the minimum delay.

3.2. Overview of Proposed Protocol Modeled by SMDP

Since the decision-making process of postman only relies on the current state of the networks, independent from the previous state, postman with the same current states would make the identical decisions to determine what it should do in the next state. Therefore, we formulate this issue as a semi-Markov Decision Process (SMDP), which is composed by the the following six tuples:  $\{S,A(i),P_{ij}(a),T(·\hspace{0.17em}|\hspace{0.17em}i,a,j),r(u,i,a,j,t),V,i,j\in S,a\in A(i)\}$ . Here, S  means the state set. Towards the state  $i\in S$ , at time point i, the available decision set is  $A(i)$ . When the system model is in the decision-making time point i  and adopts the decision a, its transition probability from state i  to j  is  $P_{ij}(a)$   and the transition time from i  to j  is the nonnegative random variables of distributed function  $T(·\hspace{0.17em}|\hspace{0.17em}i,a,j)$ . Under the condition of locating in transition state j  and transition time is t, the system would gain  $r(u,i,a,j,t)$   as reward. The reward function is shown by

$$\begin{array}{l}r\left(u,i,a,j,t\right)=r_{\mathrm{1}}(i,a,j)+{\delta }_t\left(u\right)r_{\mathrm{2}}(i,a,j)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+r_{\mathrm{3}}\left(i,a,j\right)u.\end{array}$$

(1)

Towards the given function  ${\delta }_t(u)$ , only in case  $u=t$ , the value of given function is 1. Otherwise, in case  $u\ne t$ , the value of given function is 0. Equation (1) denotes that, when the current state is i  and the decision maker adopts the decision a; in the next decision time, the state would transfer to j  and transition time is t. Decision maker gains the instantaneous reward  $r_{\mathrm{1}}(i,a,j)$   at the beginning of transition. In the process of transition, decision maker gains reward  $r_{\mathrm{3}}(i,a,j)$   at the transition finishing time point  $(u=t)$ ; it gains the instantaneous reward  $r_{\mathrm{2}}(i,a,j)$ . V  means criterion function of SMDP model.

We adopt the total reward discount criterion in our SMDP model, where time continuously changes and the discount factor is a nonnegative real number (denoted by α). It means that, at time t, the unit reward is only equivalent to  $e^{-\alpha t}$   times of time 0. Towards  $(i,a)\in \mathrm{\Gamma }$ ,  $j\in S$ ,  $t\ge \mathrm{0}$ ,  $\alpha >\mathrm{0}$ , we have

$$\begin{array}{cc}& r_{\alpha }\left(i,a,j,t\right)={{\displaystyle \int }}_{\mathrm{0}}^t‍e^{-\alpha u}{d}_{u}r\left(u,i,a,j,t\right).\end{array}$$

(2)

Equation (2) means if the current state is  $(i,a)$ , the next state would be in j. In such case, under the condition which the sojourn time is t, decision maker would gain the reward which is shown by the following equation:

$$\begin{array}{l}{r}_{\alpha }\left(i,a,j,t\right)=r_{\mathrm{1}}(i,a,j)+r_{\mathrm{2}}(i,a,j)e^{-\alpha t}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+r_{\mathrm{3}}\left(i,a,j\right)\frac{\mathrm{1}-e^{-\alpha t}}{\alpha }.\end{array}$$

(3)

When the decision maker is in the nth decision cycle, the reward should be counted from the beginning of nth cycle; it is denoted by  $r_{\alpha }(X_n,{\mathrm{\Delta }}_n,X_{n+\mathrm{1}},t_n)$ . Furthermore, when time goes from the beginning of nth to the end (0 point), the reward would be denoted by  $e^{-\alpha T_n}{r}_{\alpha }(X_n,{\mathrm{\Delta }}_n,X_{n+\mathrm{1}},t_n)$ . As for any strategy π  and state  $i\in S$ , in case the decision maker adopts strategy π  and in the state i, we can conclude the expected reward from the beginning to the end time point of nth cycle. It is denoted by  $E_{\pi ,i}\{e^{-\alpha T_n}{r}_{\alpha }(X_n,{\mathrm{\Delta }}_n,X_{n+\mathrm{1}},t_n)\}$ .

Thus, we conclude that, under the strategy π, the expected discount total reward of N  stages starting from the initial state i  is shown by

$$\begin{array}{cc}& V_{N,\alpha }\left(\pi ,i\right)={\displaystyle \sum }_{n=\mathrm{0}}^{N-\mathrm{1}}‍E_{\pi ,i}\left\{e^{-\alpha T_n}{r}_{\alpha }\left(X_n,{\mathrm{\Delta }}_n,X_{n+\mathrm{1}},t_n\right)\right\},\hspace{1em}i\in S.\end{array}$$

(4)

The optimal function of expected discount total reward of N  stages is shown by

$$\begin{array}{cc}& V_{N,\alpha }\left(i\right)=\sup \left\{V_{N,\alpha }\left(\pi ,i\right)\pi \in \Pi \right\}.\end{array}$$

(5)

3.3. Optimal Model of Postman Mobility Trajectory

Since users in mobile social networks are always located in the specific communities which depend on their living styles or the personal hobbies, the guaranteed delivery means that the packet is distributed within TTL, and we introduce postman to forward packets between different communities. In our work, to avoid the additional cost caused by the postmen, we need to control the number of postmen and their buffer sizes in a limited level. In such case, it is difficult to guarantee the immediate delivery service by a postman when a packet is just generated. We assume that the postmen are working for pursuing maximized rewards. First of all, before a postman takes packet, it needs to ensure the packet could reach the destination community within TTL. Otherwise, they cannot obtain the reward. Also, there exists linear relationship between reward and TTL, which means the more residual time is spent, the higher reward will be obtained. In this way, by maximizing the reward of postman, we conclude the minimum packet transmission delay and also optimize the packet ferry trajectory of the postman. The semi-Markov Decision Process includes two steps. Firstly, when a postman is meeting the gateway of a specific community, the number of packets which are waiting to be delivered is larger than the residual buffer size of the postman; the postman needs to select which packets it should take. The decision is based on the destination and residual alive time of the packet. Secondly, since packets have their individual destinations, the postman needs to optimize its moving trajectory by the use of semi-Markov Decision Process.

To make the optimizing process more clearly, we choose one postman to express our semi-Markov Decision Process. We assume this postman has taken m  units packets and the initial buffer size is $n\hspace{0.17em}\hspace{0.17em}(n>m)$ . It is located at $x_{\mathrm{0}}$ . The attributes of m packets are denoted by $X_{\mathrm{1}},X_{\mathrm{2}},\dots ,X_m$ , respectively. Here, $X_i$ means the attribute vector $(x_i,t_i)$ of ith packet, $x_i$ is the destination community of packet i and $t_i$ is the residual alive time of packet i. Regarding the gateway of $x_{\mathrm{0}}$ , there are s candidate packets in its buffer and their attributes are denoted by $Y_{\mathrm{1}},Y_{\mathrm{2}},\dots ,Y_s$ . Here, $Y_i$ means the attribute vector $(y_i,t_i^{\prime })$ of ith packet and $y_i$ is the destination community of packet i,  $t_i^{\prime }$ is the residual alive time of packet i. By combining attributes of postman and gateway, we define the state vector as $(n,m,s,x_{\mathrm{0}},X_{\mathrm{1}},X_{\mathrm{2}},\dots ,X_m,Y_{\mathrm{1}},Y_{\mathrm{2}},\dots ,Y_s)$ for our semi-Markov Decision Process. Each state corresponds to a vector; all the state vector are included in set S. We denote the parameter a of state i as $i\to a$ .

In our model, each decision step leads the postman to transfer from the current state; we define $a:=(i,j)$ as one decision. Also, let $A(i)$ denote all of the decisions coming from i. Towards the transfer probability $P_{ij}(a)$ , in case the subscript of i and j is one to one correspondence with the two components of a, $P_{ij}(a)=\mathrm{1}$ ; otherwise $P_{ij}(a)=\mathrm{0}$ . Towards time distribution function $T(·\hspace{0.17em}|\hspace{0.17em}i,a,j)$ , a corresponds to i and j. Therefore, $T(·\hspace{0.17em}|\hspace{0.17em}i,a,j)$ represents the time interval for the postman to move from i to j. We assume the velocity of postman is constant; then, $T(·\hspace{0.17em}|\hspace{0.17em}i,a,j)$ is only related to $x_{\mathrm{0}}$ . As mentioned in previous section, reward function $r(u,i,a,j,t)$ is composed by three terms. In our decision model, the reward is only payed in the time point when packet reached destination. It is shown by

$$\begin{array}{cc}& r\left(u,i,a,j,t\right)={\delta }_t\left(u\right)r_{\mathrm{2}}\left(i,a,j\right).\end{array}$$

(6)

Furthermore, we have

$$\begin{array}{cc}& r_{\alpha }\left(i,a,j,t\right)=r_{\mathrm{2}}\left(i,a,j\right)e^{-\alpha t}.\end{array}$$

(7)

Substitute (7) into (4) and (5), respectively; we have the following two substitution equations:

$$\begin{array}{cc}& V_{N,\alpha }\left(\pi ,i\right)={\displaystyle \sum }_{n=\mathrm{0}}^{N-\mathrm{1}}‍E_{\pi ,i}\left\{e^{-\alpha \left(T_n+t_n\right)}{r}_{\mathrm{2}}\left(X_n,{\mathrm{\Delta }}_n,X_{n+\mathrm{1}}\right)\right\},\hspace{1em}i\in S,\\ V_{N,\alpha }\left(i\right)=\sup \left\{{\displaystyle \sum }_{n=\mathrm{0}}^{N-\mathrm{1}}‍E_{\pi ,i}\frac{\left\{e^{-\alpha \left(T_n+t_n\right)}{r}_{\mathrm{2}}\left(X_n,{\mathrm{\Delta }}_n,X_{n+\mathrm{1}}\right)\right\}}{\pi \in \Pi }\right\}.\end{array}$$

(8)

Here, $t_n$ is the sojourn time of nth decision; $T_n={\sum }_{i=\mathrm{1}}^{n-\mathrm{1}}‍t_i$ . We use $V_{N,\alpha }(i)$ as the decision criterion function for our model. Since the transfer probability is 1, we have

$$\begin{array}{cc}& V_{N,\alpha }\left(i\right)=\sup \left\{{\displaystyle \sum }_{n=\mathrm{0}}^{N-\mathrm{1}}‍\frac{\left\{e^{-\alpha \left(T_n+t_n\right)}{r}_{\mathrm{2}}\left(X_n,{\mathrm{\Delta }}_n,X_{n+\mathrm{1}}\right)\right\}}{\pi \in \Pi }\right\}.\end{array}$$

(9)

In our model, sojourn time is the moving time between two gateways of postman. Due to the moving velocity is a constant, we assume the velocity of postman is V. In such case, the moving time between $i\to x_{\mathrm{0}}$ and $j\to x_{\mathrm{0}}$ is the sojourn time when the postman is at i:

$$\begin{array}{cc}& t=\frac{\left|\left(i⟶x_{\mathrm{0}}\right)-\left(j⟶x_{\mathrm{0}}\right)\right|}{V}.\end{array}$$

(10)

When the postman is moving among $a_{\mathrm{0}},a_{\mathrm{1}},a_{\mathrm{2}},\dots ,a_n$ continuously, we conclude the total sojourn time; it is shown by

$$\begin{array}{cc}& T={\displaystyle \sum }_{i=\mathrm{1}}^{n-\mathrm{1}}‍t_i.\end{array}$$

(11)

As we mentioned previously, if  $x=y$ , $\delta (x,y)=\mathrm{1}$ . Otherwise, if  $x\ne y$ , $\delta (x,y)=\mathrm{0}$ . We have

$$\begin{array}{cc}& r_{\mathrm{2}}(X_n,{\mathrm{\Delta }}_n,X_{n+\mathrm{1}})={\displaystyle \sum }_{i=\mathrm{1}}^m‍\delta (X_n⟶x_i,X_{n+\mathrm{1}}⟶x_{\mathrm{0}})\\ \left(X_n⟶t_i-\frac{\left(\left(X_{n+\mathrm{1}}⟶x_{\mathrm{0}}\right)-\left(X_n⟶x_{\mathrm{0}}\right)\right)}{V}\right).\end{array}$$

(12)

Here,  $r_{\mathrm{2}}(X_n,{\mathrm{\Delta }}_n,X_{n+\mathrm{1}})>\mathrm{0}$ . Then, we conclude  $[X_n\to t_i-(((X_{n+\mathrm{1}}\to x_{\mathrm{0}})-(X_n\to x_{\mathrm{0}}))/V)]>\mathrm{0}$ . In this section, we introduce the packet choosing strategy. We assume a postman has taken p units packets. In a specific gateway, there are q candidate packets that are waiting for forwarding. Currently, the postman is in state H. In case, $p<n$ , where n is the initial buffer size, the postman would try to take each candidate packet sequentially. When the postman is trying to take ith packet, we calculate the maximum expected discounted total reward as

$$\begin{array}{cc}& V_{p+\mathrm{1},\alpha }\left(H\right)=\sup \left\{{\displaystyle \sum }_{j=\mathrm{0}}^p‍\left\{e^{-\alpha \left(T_j+t_j\right)}{r}_{\mathrm{2}}\left(X_j,{\mathrm{\Delta }}_j,X_{j+\mathrm{1}}\right)\right\}\right\}.\end{array}$$

(13)

In this time, we assume the postman has only taken  $Y_i$   and the current state is  $X_{\mathrm{0}}$ . According to specific order, the packets will be forwarded to the different destinations and the state sequence is  $X_{\mathrm{1}},X_{\mathrm{2}},\dots ,X_{p+\mathrm{1}}$ . Towards the total reward function, if each term is greater than 0, we define this expected reward as effective. Meanwhile, we conclude one expected discounted total reward  $V_{i,\mathrm{1}}$ . Then, we change the packet forwarding order to calculate the expected reward for the second time. If this order is also effective, we have the expected discounted total reward  $V_{i,\mathrm{2}}$ . According to this ergodic rule, we calculate the correspondence expected reward of u  effective order,  $V_{i,\mathrm{1}},V_{i,\mathrm{2}},\dots ,V_{i,u}$ . Then we have

$$\begin{array}{cc}& V_{p+\mathrm{1},\alpha }{\left(H\right)}_i=\max \hspace{0.17em}\left\{V_{i,\mathrm{1}},V_{i,\mathrm{2}},\dots ,V_{i,u}\right\}.\end{array}$$

(14)

We let all the candidate packets fitting to be taken and calculate every maximum expected discounted total reward, they are shown by  $V_{p+\mathrm{1},\alpha }(H{)}_{\mathrm{1}},V_{p+\mathrm{1},\alpha }(H{)}_{\mathrm{2}},\dots ,V_{p+\mathrm{1},\alpha }(H{)}_q$ . If every value of the given  $V_{p+\mathrm{1},\alpha }(H{)}_i$   is 0, the postman cannot choose any candidate packet. Otherwise, the postman chooses the packet  $Y_c$   which corresponds to the maximum  $V_{p+\mathrm{1},\alpha }(H{)}_c$   to be taken. In this time, the postman has taken  $p+\mathrm{1}$   units packets. We change the order of  $Y_{\mathrm{1}}$   and  $Y_c$   in the state vector; the state vector is shown by  $(n,m,s,x_{\mathrm{0}},X_{\mathrm{1}},X_{\mathrm{2}},\dots ,X_m,Y_{\mathrm{1}},Y_{\mathrm{2}},\dots ,Y_s)$   and also m  plus 1. If  $m=n$ , the packet choosing process is done. Otherwise, the postman repeats the choosing process in the rest of the candidate packets.

When the postman finishes the packet choosing process, it has taken m  packets and the state is shown by  $X_{\mathrm{1}},X_{\mathrm{2}},\dots ,X_m$ . We substitute them into  ${\sum }_{j=\mathrm{0}}^m\{e^{-\alpha (T_j+t_j)}{r}_{\mathrm{2}}(X_j,{\mathrm{\Delta }}_j,X_{j+\mathrm{1}})\}$   according to the specific order when they are forwarded to the destination. If this specific order can obtain the ordered expected discounted total reward  $V_{\mathrm{1}}$ , the postman ergodic all the orders to calculate the effective ordered expected discounted total reward  $V_{\mathrm{1}},V_{\mathrm{2}},\dots ,V_u$   and further obtain the maximum value  $V_c$   as the optimal ordered expected discounted total reward to adjust state vector  $(n,m,s,x_{\mathrm{0}},X_{\mathrm{1}},X_{\mathrm{2}},\dots ,X_m,Y_{\mathrm{1}},Y_{\mathrm{2}},\dots ,Y_s)$   to match the specific order to obtain  $V_c$ . In this way, we determine order of the packets which are taken by the postman. From the packet point of view, this order is the forwarding priority. From the postman point of view, this order is the optimal moving trajectory for the packet ferrying.

4. Optimal Number for Multiple Postmen Working Together

As we know, the capability (e.g., buffer size and bandwidth) of each postman is limited, and in the given time, it only can forward the fixed number of packets by using its maximum capability. Therefore, when large number of nodes distributed in the sparse wireless networks, or the packet generation ratio is too high of each node, single postman is hard to guarantee the effective packet forwarding. In such case, multiple postmen should be implemented into the networks. Based on this aspect, under the scenario of given network scale and parameters, how to conclude the optimal number of postmen is an important issue for multiple postmen working in the same area. By using the optimal number of postmen, every postman can work under the condition of optimal packet forwarding load.

As for the given sparse network scale, we define the following necessary parameters for calculating the optimal number of postmen. We set the network running time as t  and the TTL packet as T. The moving velocity of postman is V  and the initial buffer size is n. There are N  communities in our network model and M  nodes are distributed in the different communities. We denoted by  $X_i$   the ith node and by X  the set which includes all nodes.  $Y_i$   is the ith community and also denoted the set of nodes which belonged to community  $Y_i$ . Y  is the set which including all communities. We denoted  $\rho (Y_i,Y_j)$   the shortest path from  $Y_i$   to  $Y_j$ , especially when  $i=j$   and  $\rho (Y_i,Y_j)=\mathrm{0}$ . Towards for all  $X_m\in Y_i$ , $X_l\in Y_j$ , we have the following:

$$\begin{array}{cc}& \rho \left(X_m,X_l\right)=\rho \left(Y_i,Y_j\right).\end{array}$$

(15)

In order to describe the different scenarios of shortest path existing, we have the following:

$$\begin{array}{cc}& \delta \left(Y_i,Y_j\right)=\{\begin{array}{c}\mathrm{0},\\ \mathrm{1}.\end{array}\end{array}$$

(16)

In equation (16), in case  $i=j$   or there are other communities between the shortest path of  $Y_i$   to  $Y_j$ , we have  $\delta (Y_i,Y_j)=0$ . Otherwise, in case  $i\ne j$   and there is no other community between the shortest path of  $Y_i$   to  $Y_j$ , we have  $\delta (Y_i,Y_j)=1$ . As for all  $X_m\in Y_i,X_l\in Y_j$ , we have  $\delta (X_m,X_l)=\delta (Y_i,Y_j)$ .

Here, we assume that  $S_X$   is the σ  algebra of X. As for all  $D\in S_X$ ,  $|D|$   denotes the number of nodes of D. In D, we assume one arbitrary node  $X_m$ , it generates one packet. Then the probability of this packet is  $P(X_m,X_k)$ , which the destination is  $X_k$ .  $r(D)$   is the sparseness measure of field D. We have

$$\begin{array}{cc}& r\left(D\right)=\frac{{{\displaystyle \sum }}_{i\ne j}^{Y_i\in D,Y_j\in D}\delta \left(Y_i,Y_j\right)\rho \left(Y_i,Y_j\right)}{{{\displaystyle \sum }}_{i\ne j}^{Y_i\in D,Y_j\in D}\delta \left(Y_i,Y_j\right)}.\end{array}$$

(17)

In our work, we consider the packet generation time interval of each node according to poisson distribution. In the network, node  $X_m$   generates packet according to poisson distribution with the intensity  $\lambda (X_m)$ . We consider  ${\lambda }_m$   as the packet generation intensity for node  $X_m$ . In network field D, we conclude that within system running time t, the mathematical expectation of total number of packet generation is shown by the following equation:

$$\begin{array}{cc}& E\left(D,t\right)={\displaystyle \sum }_{X_m\in D}‍\lambda \left(X_m\right)t.\end{array}$$

(18)

Especially, as for all  $m,l$ ,  $m,l\in \{\mathrm{1},\dots ,M\}$ ,  ${\lambda }_m=\lambda l=\lambda$ . Since  $E(D,t)=|D|\lambda t$ , we assume in field D  the probability of arbitrary node  $X_m$   generates the packet whose destination is  $X_k$   is  $P(X_m,X_k)$ . Within time interval t, the total number of packet generation is shown by the following equation:

$$\begin{array}{cc}& W\left(D\right)={\displaystyle \sum }_{X_m\in D,X_k\in X}‍P\left(X_m,X_k\right)\rho \left(X_m,X_k\right)\lambda \left(X_m\right)t.\end{array}$$

(19)

Especially, when D  is the complete set of X. We have

$$\begin{array}{cc}& W={\displaystyle \sum }_{X_m\in X,X_k\in X}‍P\left(X_m,X_k\right)\rho \left(X_m,X_k\right)\lambda \left(X_m\right)t.\end{array}$$

(20)

Equation (20) denoted the total working load within time interval t. We also conclude the average update number of hops for each packet and it is shown by the following equation:

$$\begin{array}{cc}& u=\frac{\mathrm{1}}{r\left(D\right)}{\displaystyle \sum }_{X_m\in D,X_k\in D}‍P\left(X_m,X_k\right)\rho \left(X_m,X_k\right).\end{array}$$

(21)

As for each packet, the average transmission delay is shown by

$$\begin{array}{cc}& \bar{t}=\frac{\mathrm{1}}{v}{\displaystyle \sum }_{X_m\in D,X_k\in D}‍\rho \left(X_m,X_k\right)P\left(X_m,X_k\right).\end{array}$$

(22)

Further, we have the packet carrying time and it is denoted by  $t_s=(T-t_w-\bar{t})/\mathrm{2}$ ; the packet carrying redundancy is  $r_t=\bar{t}/t_s$ . In the running time interval t, the maximum ferrying capability of postman is  $P_w=r_t{r}_s{v}_t$ . In such case, in network field D, the optimal number of postmen is shown by the following equation:

$$\begin{array}{cc}& N_r\left(D\right)=\frac{W\left(D\right)}{P_w}.\end{array}$$

(23)

Especially, during the above process, when D  is always the complete set of X,  $N_r=W/P_w$   is the perfect state of optimal number of postmen. We substitute (23), we conclude the unary function whose unknown number is  $N_r$ . In such case, by solving the  $N_r$ , we can conclude the optimal number of postmen in our proposed network. The expression is shown by

$$\begin{array}{cc}& t_w=\frac{E\left(D,t\right)r\left(D\right)}{N_r{r}_{s}u{v}_t}.\end{array}$$

(24)

In (24),  $N_r$   is the number of postmen and  $r_s$   is the expected buffer occupation of postman. In the ideal state, we assume that and under the situation of optimal number of postmen working in the given network field, each postman would work with full load. We have  $r_s=n$ . However, most of the time, postman cannot work under the condition of full load; in such case, we set a tolerable space occupancy rate and it is denoted by  $\mathrm{0}<\epsilon <\mathrm{1}$   and  $r_s={\epsilon }_n$ . Based on these descriptions, we have the following equation to show the result of optimal number of postmen:

$$\begin{array}{l}{N}_r=({\displaystyle \sum }_{X_m{X}_k}‍\left(P(X_m,X_k)P(X_m,X_k)\lambda \left(X_m\right)\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\times \left(\frac{T}{\mathrm{2}}-\frac{E\left(X,t\right)r\left(D\right)}{N_r{r}_{s}u{V}_t}\right)\phantom{{\displaystyle \sum }_{X_m{X}_k}‍})\\ \hspace{1em}\times {\left(r_s{\displaystyle \sum }_{X_m{X}_k}‍\rho \left(X_m,X_k\right)P\left(X_m,X_k\right)\right)}^{-1}.\end{array}$$

(25)

5. Performance Evaluation

In this section, we compare our proposed solution with other three existing packet ferry forwarding protocols. In Section 2, we have overviewed the existing packet ferry protocols which we compared with our proposed solution. In order to obtain the simulation results which are close to the real application scenario, we use the Reality Mining which comes from MIT as our simulation dataset [20]. Furthermore, we use the ONE [21] as our platform for simulation. The ONE is a simulation environment that is capable of generating node movement using different movement models, routing messages between nodes with various DTN routing algorithms and sender and receiver types, and visualizing both mobility and message passing in real time in its graphical user interface. In our simulations, we focus on delivery ratio and the average delivery delay as the key metrics to evaluate the proposed packet-ferrying solution. We define the delivery ratio as the ratio of the number of delivered packets to the total number of packets in our simulation process.

5.1. Reality Mining Data Analysis

Reality Mining comes from MIT Media Laboratory which collected data from 94 volunteers. The dataset contains the following items. Call logs, bluetooth devices (the distance between any two close devices is 5 meters), cell tower IDs, application usage, and phone status. The Reality Mining was collected using mobile phones preinstalled with several pieces of software that recorded and sent the researcher data during the months between September 2004 and June 2005.

Since our main focus is on the scenario in which the nodes have different belonging communities and how to make the ferry forwards packets more effectively, we filter the encountering time and cellular tower IDs which are recorded by subjects between all cellular towers and subjects. Through the location of cellular towers, we can obtain the location information of subjects. Unfortunately, in Reality Mining only the cellular towers that are associated with MIT have location information. Therefore, we choose the areas which are covered by the cellular towers and these areas location information is known for our work.

5.2. Simulation Parameter Setting

In MIT Reality Mining, our simulation runs for 24 hours to collect data. We choose 50 subjects which have the complete information and typical community character as the normal mobile nodes among all 94 subjects. According to the locations of cellular towers in campus map, we divided the whole map into 7 communities. By using the information of contacts with cellular towers of Reality Mining, we obtain the belonging relationship for different communities in the given time period. In our simulations, we set one gateway for each community and the buffer size of gateway has no limitation. We put 5 ferries working in the network to forward packets between 7 isolated communities. Since the moving activity is unknown in community for us, we assume that the normal node is adopted by the Random Way point model as its moving rule. When normal nodes encounter the gateway, they send their packets to the gateway. If some nodes move to another community, they execute the same packet sending action after determining the community belonging. The packets are generated randomly, and the destinations of packets are also randomly assigned. The total simulation time is 24 hours (86900 seconds). We set the initial 400 seconds as the warming-up time period and the last 500 seconds as the terminal time period. In these two special time periods, we do not collect data for final simulation results. The detailed simulation parameters are shown as follows: the velocity of normal node is 5 meter/second; the velocity of ferry node is 15 meter/second; the communication range of normal node, ferry, and gateway is 150 meter. Firstly, we simulate all the protocols under the condition in which the buffer size is 10 units and the packet expired time is 60 minutes. Secondly, based on the different buffer size and packet expired time, different packets distribution model, we compared the performance of all packet forwarding protocols.

5.3. Impacts of Different Packet Generation Rate

In order to observe the different performance under the condition of different packet generation rate, we simulate all packet forwarding protocols in which the number of packet is from 100 to 2000 packets and the packet generation interval is uniform. The simulation results are shown by Figures 1 and 2. In these two figures, since our proposed protocol and HRC protocol are all based on the social characteristic and the distribution of nodes also corresponds to the social networks, from Figure 1, we can see that, under the condition of different packet generation rate, our proposed protocol and HRC show better performance of packet delivery ratio than that of DRR. When the number of packets is larger than 400, our proposed protocol and HRC are all better than FIMF in terms of packet delivery ratio. Furthermore, when the number of packets is larger than 600, the performance of our proposed protocol is also better than that of HRC, and according to the increasing of packet generation ratio, our protocol shows better performance evidently. The main reason is that our proposed protocol optimizes the trajectory of postman for packet ferrying. On the contrary, the trajectory of ferry node of HRC is moving according to the fixed routine. This is also the reason why our protocol shows better performance than that of others in terms of packet delivery delay in Figure 2. In Figure 2, we can see that the packet delivery delay is the highest compared with other three protocols. This is because DRR prefers to provide service for the nodes which have the larger packet generation ratio instead of the nodes whose buffers have more packets. Since the ferry node of HRC protocol moves according to the fixed trajectory, the movement cycle is fixed. In such case, the influence of packet generation ratio is lower in terms of packet delivery delay for HRC protocol. It leads to the result that when the number of packet is less than 500, packet delivery delay of HRC is higher than that of FIMF. On the contrary, when the number of packet is larger than 500, HRC is lower than FIMF. In the traditional scenario, packet delivery delay should increase according to the packet generation ratio increasingly. For example, in Figure 2, the curves of DRR and FIMF are obtained under the condition that, when the number of packet is less than 600. However, in Figure 2, besides our proposed protocol, the packet delivery delay of other three compared protocols is going down according to the packet generation ratio increasingly when the number of packets is larger than 700. This is because when we count up the average delivery delay, we only consider the packet delivery delay which is successful forward to the destination. However, when the number of packet is larger than 700, delivery ratio of other three compared protocols have decreased rapidly according to the increase in packets. It leads to the results that as for the packets which have the predominance of space and time, they can be forwarded by lower delivery delay. On the contrary, the packets which have no predominance would expire before the TTL and cannot be counted. Towards our proposed protocol and HRC, postman provides forwarding services for the whole community. Therefore, the increase in packet generation would not impact the delivery delay evidently.

Figure 1

Comparison of delivery ratio under different message number.

Figure 2

Comparison of average delay under different message number.

5.4. Impacts of Buffer Size

In Figure 1, we can see that, when the number of packets is less than 500, the delivery ratio of all the four simulated protocols is stable. In order to obtain the comprehensive result of buffer size influence, we choose 600 as the number of packets to simulate the impacts under different buffer size scenarios. We set the buffer size as changing from 5 to 14 units and also, 1 unit means one packet buffer occupation. Figures 3 and 4 show the performance of delivery ratio and delay, respectively, under the changing of buffer size. From these two figures, we can see that, when the number of packets is 600, as for our proposed protocol, the delivery ratio is the highest compared with other ferrying protocols. When buffer size is less than 10 units, the delivery ratio of other three protocols becomes dropping down evidently. The delivery ratio of FIMF is lower than those of HRC and DRR. Since as for FIMF, the ferry node provides forwarding service until normal nodes collect enough packets. In this way, if the buffer size of ferry node is small, the delivery ratio of FIMF is becoming lower. Towards HRC and DRR, they provide forwarding service based on the periodic mode; therefore, their dropping down magnitude is almost the same. Specially, since HRC provides forwarding service based on community structure, its delivery ratio is higher than that of DRR protocol.

Figure 3

Comparison of delivery ratio under different buffer size.

Figure 4

Comparison of average delay under different buffer size.

From Figure 3, we can see when buffer size of postman is larger than 10 units, besides our proposed protocol, delivery ratio of other three protocols is becoming stable. Meanwhile in Figure 4, the average delivery delay of these three protocols is also becoming stable. It means that besides our proposed protocol, when buffer size is 10, these three compared protocols are in the buffer saturation status. However, as for our proposed protocol, when the buffer size is 4 units, it has fall in the saturation status and enough buffer for packet forwarding.

5.5. Impacts of Packet Expired Time (TTL)

From Figure 3, we can see that when buffer size is larger than 9 units, all protocols are becoming stable in terms of delivery ratio. In order to show the influence of packet expired time (TTL) more clearly, we set the buffer size as 8 units and the number of packets as 600. we simulate all protocols under the condition of TTL to be 30 minutes to 120 minutes to show the performance in terms of packet delivery ratio and delivery delay; the results are shown in Figures 5 and 6.

Figure 5

Comparison of delivery ratio under different TTL.

Figure 6

Comparison of average delay under different TTL.

In Figure 5, we can see that our proposed protocol and HRC show better performance since they are designed based on social community. When TTL is less than 50 minutes, the delivery ratio is in the worst case for these two social-based protocols. In our proposed protocol, we optimize the trajectory of postman; it makes better performance compared with HRC in terms of delivery ratio under the different TTL. As for FIMF and DRR protocol, when TTL is lower than 100 minutes and 70 minutes, respectively, the delivery ratio of them is becoming lower. Meanwhile, when TTL is larger than 70 minutes, DRR shows better performance than FIMF. This is because FIMF needs to wait for normal nodes to collect enough packets to start the forwarding process.

From Figure 6, we observe that as for DRR protocol, under the different TTL, it always in the higher delivery delay. And our proposed protocol is still lower than the other three compared protocols. Furthermore, the TTL changing from 30 to 120 minutes almost cannot impact the performance of our proposed protocol.

5.6. Impacts of the Distribution for Packet Destination

In order to make our simulation results much closer to the real application scenario, we make the destination of packet obey the normal distribution and according to the changing of parameter δ  to simulate the proposed protocols. In the simulation process, we set the parameter δ  changing from 1 to 10. According to the probability density function of normal distribution, we know that if δ  is smaller, the destination of packets is more concentrated. The simulation results are shown by Figures 7 and 8.

Figure 7

Comparison of delivery ratio under different parameter δ.

Figure 8

Comparison of average delay under different parameter δ.

In Figure 7, we can observe that parameter δ  almost cannot impact the performance of our proposed protocol in terms of packet delivery ratio. When δ  is larger than 6, delivery ratio of FIMF is becoming lower according to the increase in δ. This is because FIMF provides forwarding service for normal node; when there are several nodes which are located in the network and have much more packets than other normal nodes, FIMF prefers to provide all forwarding services to these special nodes. This also is the reason why DRR has the lower delivery ratio when δ  is larger than 7. As for HRC protocol, when δ  is less than 4, its delivery ratio increases according to the increase in δ. When δ  is larger than 4, the delivery ratio of HRC is tending to be stable. This is because the postman of HRC is moving according to the periodic mode. Towards our proposed protocol, we optimize the trajectory of postman; it leads to the results that before the moving activity, postman determines the optimal traveling trajectory. Therefore, the distribution parameter δ  has hard impact on the delivery ratio performance of our protocol.

From Figure 8, we observe that as for all four compared protocols, the packet delivery delay is hard to be impacted by distribution parameter δ. DRR protocol still has the highest delivery delay. Our proposed protocol shows the best performance in terms of delivery delay. However, when δ  is less than 4, since the destination of packet is too concentrated, it makes the delivery delay higher according to the decrease in δ.

6. Conclusion

Packet routing and forwarding is one of the most important issues for opportunistic social-based M2M networks. In this paper, we focus on the scenario that nodes are distributed in the sparse area. This scenario is a real application case for social-based M2M networks. By analyzing the moving behavior of supernode (called postman in this paper), we optimize the moving trajectory of postman for opportunistic social-based M2M networks. We formulate the optimization issue as a semi-Markov Decision Process model to produce the delivery sequence and conclude the optimal moving trajectory of postman. We combine the pursuing reward attribute of postman and the TTL of packet into one reward function. We achieve the goal of minimizing delivery delay while improving the delivery ratio of packets. Simulation results show our ferrying solution performs better than other existing schemes in opportunistic social-based M2M networks.