Printer Friendly

FARS: A Fairness-aware Routing Strategy for Mobile Opportunistic Networks.

1. Introduction

Due to the popularity of mobile intelligent terminal and the rapid development of short distance wireless communication technology, mobile devices (mobile phones, tablet PCs, etc.) carried by the ordinary users can be easily used to form a new typical of mobile ad hoc network, which is called Mobile Opportunistic Networks(MONs) [1,2,3]. MONs breaks the constraint of full connectivity in traditional network, which is more suitable for the actual demand for self-networking. MONs has broad application prospects in sensor networks, wildlife tracking, vehicle network and network services of underdeveloped areas, which has greatly improved the people's production and life style and attracted the close attention of academia in recent years.

In MONs, due to the frequent movement of nodes and constant change of network topology, it is difficult to find a stable end-to-end path between nodes in the network [4]. Therefore, "store-carry-forward" mechanism is usually be used to handle intermittent connectivity in most existing opportunity-based routing methods for MONs [5], and each node should independently make forwarding decisions under this mechanism.

At present, although there have been a lot of researchers on the issue of opportunities routing, most of them adopt the greedy transmission mode to pursue a higher delivery efficient, and choose the nodes with higher-utility values as the relay node, which may easily result in the small part of nodes bear most of the forwarding task, and cause the unfairness of data delivery amount among nodes. Especially in selfish environment, this type of routing will eventually lead to sabotage and cooperation due to the unfairness of nodes, resulting in a decline in network performance.

In this paper, we take into account of various factors that would cause unfairness among nodes, and model the routing problem as a multiple attribute decision making (MADM) problem, which make the selection of the relay nodes more reasonable. Extensive experiments are made to evaluate the performance of our protocol and other classic protocols based on Infocom05[27] and TVCM model[26], and the results are discussed and analyzed in many aspects.

In summary, the main controbution of this paper are outlined as follows.

* The main factors that reflect the fairness of the nodes are analyzed, and the routing selection is modeled as a MADM problem.

* A novel Fairness-aware routing strategy, named FARS, is proposed, which can greatly inprove the fairness of data deliver amount of nodes when ensuring the overall delivery performance of the network.

* Extensive experiments are made to evaluate the performance of our protocol and other classic protocols based on a real-life mobility trace of Infocom05 and a synthetic trace, and the results are discussed and analyzed in many aspects.

The rest of the paper is organized as follows: we survey the related work in Section 2. Section 3 introduces network model, and further presents our LBRS in Section 4. We show simulation and evaluation in Section 5, simulation results and discussion in Section 5.5, followed by the conclusion and future work in Section 6.

2. Related Work

In order to seize the fleeting opportunity and improve the success delivery rate, multiple replication is common used to maximize the number of successful delivered packets. A typical routing protocol is Epidemic [6], which uses flooding pattern to diffuse the copies of a message in networks. It can obtain the highest success delivery rate, the largest cost and leads to relatively better fairness among nodes in the case of unlimited resources, such as device energy, node buffer, link bandwidth, and so on. But in practice, resources are limited, and too many copies will expend a lot of network resources and lead to network congestion easily, which can in turn inhibit the performance of network delivery.

In order to reduce the number of copies of packets, utility function is usually used to indicate the delivery probability of a node in the network, and nodes with higher utility values are usually selected as relay nodes, which can increase the probability of successful packet delivery while reducing the number of message copies. In Prophet [7], the utility value of a node is defined as the contact probability between this node and the destination node, and the packets is only forwarded to the encounter node that has a higher encounter probability with the destination node. The authors of [8] modeled data delivery as an online knapsack problem, and designed a user context-based message replication scheme that achieved efficient data delivery with deterministic cost, which had the goal to maximize the overall delivery probability of each datum using a constant number of message replications. The delivery probability is not a probability of two nodes meeting each other, but a probability that two nodes encounter each other within a given time. According to the temporal and spatial context information of node (meeting time, meeting time duration), the authors of [9] proposed a social context-based routing scheme named CIPRO, in which a BP Neural Network model is used to predict the context of nodes. Thus, the source device knew when and where to start the routing process to maximize the transmission delay and minimize the network overhead.

In recent years, the sociality is used to design routing strategy. The authors of [10] designed a friend-oriented forwarding strategy, which defined a utility function of friend relationship strength between the nodes based on contact frequency and contact time-duration. In literature [11], the authors defined the PeopleRank utility of each node to calculate node centrality. The authors of [12] introduced a utility function named SimBet based on the centrality and similarity of nodes. And in literature [13], the authors further merged the tie strength relationship into SimBet and named it SimBetST, which can avoid high load of central node. The authors of [14] proposed a forwarding strategy named BubbleRap, which considered global centrality, local centrality of a node, and node community label at the same time. In the literature [15], the authors used the information entropy theory to estimate centrality and similarity of the nodes and fused centrality and similarity at the stage of relay node selection.

All the algorithms above are based on a certain utility function, and the nodes with higher utility value are selected as relay nodes when designing routing strategy. Compared with Epidemic, they have improved in performance more or less, while the number of copies of the message is greatly reduced.

However, among the routing protocols above based on utility function, utility function of ndoe is always related to some global or local 'status' in the network. Those selected relay nodes in such routing protocols always bear the function of router of traditional network, and transfer the majority of the network traffic, which can easily lead to network congestion and unfairness among nodes. And the performance has not much improved. In actual, each individual user in mobile opportunistic network would pay more attention to its own data delivery amount than the average performance of the whole system. One would feel unfairly if its own data delivery amount is far different from others around him. Thus, the unfairness among nodes would trigger the dissatisfaction of users whose data delivery amount is very different from the surrounding nodes.

Therefore, we should take full account of the fairness when pursuing higher delivery performance. There are some researches on fairness in ad hoc networks, delay tolerant network and opportunistic networks. In literature [16], the authors proposed an on-demand multipath routing protocol with load balancing, and chose the nodes with higher energy than threshold value as relay nodes to distribute the traffic evenly in ad hoc network. The authors of literature [17] were aware of the problem of the fairness issues on the successful delivery rate among users brought about by multicopy utility-based routing protocol in MONs, and proposed fair packet forwarding strategy based on packet priority. In Literature [18], fairness issue was considered critical in disaster areas. Extensive simulation in terms of the fairness were carried out and the results of performance comparison shew that the development of advanced routing algorithm is now still an open issue. In literature [19], Mtibaa and his companion analyzed the trade-offs between fairness and efficiency in mobile opportunistic networks, proposed a FOG framework to ensure efficiency-fairness trade-off using local information, and implemented two real-time distributed fairness algorithms: PFA and MCFA. The authors of literature [20] introduced FairRoute, a routing algorithm inspired by the social processes of perceived interaction strength and assortativity, to overcome unfair load distribution and inefficiencies. In literature [22], SCGR was proposed to optimize both fairness and throughput. A node would be selected as relay nodes based on the multi-hop delivery probability and its queue length.

Although the fairness issue was taken into account in protocols above in some degree, in essence, the 'status' of the node was still used to make routing, and the fairness index has not been improved significantly. There are some factors which have a marginal effect on fairness among nodes, and some will reflect the fairness. In this paper, these factors were comprehensively considered, and the routing problem was modeled as a multiple attribute decision making(MADM) problems, which make the selection of the relay nodes more reasonable. Extensive experiments are made to evaluate the performance of our protocol and other classic protocols based on Infocom05 and TVCM model, and the results are discussed and analyzed in many aspects.

3. Network Structure and Assumption

In order to descript problem conveniently, in this section, we briefly give the network structure of MONs and assumptions used.

3.1 Network Structure

Firstly, we consider a MON as a symmetric weighted graph G(V, E). In which, V is the set of nodes, V={[N1.sub.],[N.sub.2],...[N.sub.N]},N[greater than or equal to]1 and N is the number of nodes in the network. E is the set of edges, E={[e.sub.12],[e.sub.13],...[e.sub.ij],...}, i[not equal to]j, 1 [less than or equal to]i, j[less than or equal to]N, and [e.sub.ij] is the weight of the edge between node i and j. In MONs, the carriers of all nodes are humans, which can be moving everywhere. The nodes move in accordance with their daily routine, hobbies and so on. If and only if two nodes enter into each other's wireless communication range, it can be considered that there is a physical contact between them, and data exchange may be carried out at that time. According to the graph G(V, E), we can extract the property of each node and relationship between nodes in the whole or local network.

In order to make it easier to understand, we give two snapshots of the structure of the network in Fig. 1. There are five nodes, which are represented as 1, 2, 3, 4 and 5 respectively. The line between a pair of nodes indicates that there is at least one physical contact between them, and the value above the line shows the weight of relationship between the corresponding node pair. From [t.sub.1] to [t.sub.2], the instantaneous structure graph of the network has changed a lot because of the movement of nodes.

3.2 Problem Description

Due to the frequent movement of nodes, there rarely exists an end-to-end path between source node and destination node in the network. Therefore, "store-carry-forward" mode is usually be used in most existing opportunity-based routing methods for MONs. Fig. 2 illustrates forwarding process of a packet from the sender to the receiver using the "store-carry-forward" mode. At time [t.sub.1], the sender S and the receiver D were located in two disconnected sub region, and there was not a complete path between them. So S would forward this packet to A. Due to node A also failed to reach node D directly, it carried the packet and waited for appropriate forwarding opportunity. At time [t.sub.2], node A entered the communication range of node E and then forwarded the packet to E, and at following time [t.sub.3], node E met receiver D and then finished this data transfer.

From Fig. 2, it can be seen easily that in the weak link of network state, store-carry-forward mode is an effective opportunistic data transfer mode, but the selection of relay nodes significantly affects the performance of data transmission. Therefore, the key of opportunistic data transmission under the condition of weak connection state in MONs is to find a better relay node selection strategy. This paper aims to design a more reasonable routing strategy to pursue fairness of delivery amount among nodes as much as possible along with guaranteed data delivery.

3.3 Assumptions

The node of MONs may be a vehicle mounted intelligent equipment or a smart phone carried by mobile user. If a node is vehicle-mounted equipment, it is continuously powered by the car battery. If a node is a smart phone, it can continuously work for about 3 days on average, which is enough for data delivery. Therefore, the nodal energy is not considered during our routing design. A mobile user will use his/her mobile device to do all kinds of things instead of just helping us to forward data, and can get a certain satisfaction and accomplishment from the completing of the task. Therefore, users hope that their own data delivery amount and success delivery rate is not so far different from those of the surrounding users. But, fairness of delivery amount among nodes is related to various factors, such as residual buffer size, data delivery amount, social relations between nodes and social status, etc. Network topology changes frequently and network global information is not easy to be obtained, but when several nodes meet, factors related to these nodes can be shared conveniently. We can construct reasonable routing strategy according to the related factors of these nodes. So, in order to simplify this issue, we assume that the initial buffers of all the mobile users and the Time-to-Live(TTL) of all generated packets are equal. In addition, we assume that all nodes are selfless and they are all willing to forward messages for others.

4. Fairness-aware Routing Strategy

In this section, we introduce our fairness-aware routing strategy in detail. As mentioned above, relying so heavily on nodes with higher 'status' will result in the unfairness among nodes. So, in order to avoid or reduce the occurrence of this situation, in our routing protocol, instead of using the global 'status' of a node as a metric, we considered three factors associated with fairness comprehensively, modeled the routing problem as a MADM problem [23], utilized an entropy method to decide the weight of each factor, and then make routing decision according to this sorting.

Therefore, in the first part of this section, we will show the relationship between these three factors and fairness and define them, then we will introduce the implementation steps of MADM based on entropy. And in the third part, we will introduce our FARS carefully.

4.1 Definition of Related Factors

In MONs, there are some factors which have a marginal effect on fairness among nodes, and some will reflect the fairness. Contact strength between node pair reflects not the central position of the node but the relationship between any node pair in the network. So, making routing decision depending on this indicator maybe improve the delivery rate more or less, but it does not lead to a large amount of data aggregation to a small number of nodes and will not bring obvious unfairness. Historical data delivery amount of node and residual sequence length represent the amount of data delivered by a node and the current cache occupancy of the node, respectively, which indicate the delivery ability of nodes and reflect the fairness among nodes directly. So, we take these three main factors into account comprehensively. Next, we will give the definitions of three factors.

* Historical Data Delivery Amount Historical data delivery amount refers to the total amount of data delivered before this time. The bigger this value is, the more data the node has forwarded in the past. From the view of fairness, we hope that this value is not too large or too small. To avoid increasing the weight of unfairness, the nodes with larger historical data delivery amount is not the best relay nodes. So, this indicator should be smaller. And, we use f to represent this metric in the following sections.

* Residual Sequence Length It refers to residual buffer of a node. It can be represented by the difference between initial buffer and occupied buffer size of a node. The bigger this value is, the larger the residual sequence space is, and the larger amount the node can forward in the future. We use f to represent this metric in the following sections.

* Contact Strength It refers to the contact strength between any node pair. Generally, contact strength is related to the contact duration and contact frequency. In this paper, we define contact strength using Equ(1). Here, [CN.sub.i,j] is the contact number of node [N.sub.i] with node [N.sub.j] in a certain time, and [CN.sub.i] is the total contact number of node [N.sub.i] with all the others nodes in the network in a certain time. [CA.sub.i,j] is the historical average contact duration between node [N.sub.i] and [N.sub.j] in a certain time, and [CD.sub.i] is the total historical average contact duration between node [N.sub.j] and all the other nodes in a certain time. [alpha] and [beta] are two coefficients, respectively. This metric is represented as [f.sub.3] in the following sections.

[CS.sub.i,j] = a[[CN.sub.ij]/[CN.sub.i]-[CN.sub.ij]]+[beta] [[CD.sub.ij]/[CD.sub.i]-[CD.sub.ij]].(1)

4.2 Entropy-based MADM

In this section, the routing problem was modeled as a MADM problem. And then, a fairness-aware routing strategy, named FARS, was proposed. We consider the former three factors, referred to as [f.sub.1], [f.sub.2], [f.sub.3], respectively, and utilize an entropy [24] method to decide the weight of each attribute. Detailed steps are outlined as follows.

1 Build a decision matrix

Assuming there are m nodes that encountered at the same time, that is, there are m candidates schemes to be selected. Therefore, decision matrix X is as Equ.(2)

[mathematical expression not reproducible]

Each entry [X.sub.ij] in the matrix is the factor[f.sub.j] of nodei,1 [less than or equal to]i [less than or equal to]m l [less than or equal to] j [less than or equal to]3

2 Linear proportional transformation

When making decision, the index that is expected a larger value is defined as positive indicator, and the others, the reverse indicators. Therefore, f1 is reverse index, and [f.sub.2], [f.sub.3] are positive ones. After the linear scaling transformation, all the indexes are positive indicators.

For positive indicator,[x*.sub.j] = nmm [x.sub.ij] [not equal to] 0, [z.sub.ij] = [[x.sub.ij]/[x*.sub.j](1[less than or equal to]i [less than or equal to] m,1 [less than or equal to] j [less than or equal to] 3);

For reverse indicator,[mathematical expression not reproducible]@

3 Standardizing decision matrix

The decision matrix X is transformed into Y, here, Y -[([y.sub.ij]).sub.mx3] = ([Y.sub.1],[Y.sub.2],[Y.sub.3])and

[mathematical expression not reproducible].(3)

4 Calculating entropy [e.sub.i], as

[mathematical expression not reproducible].(4)

5 Measure differential coefficient of entropy as

[g.sub.j],-=l-[e.sub.j],,(j = 1,2,3).(5)

6 Compute the weight [w.sub.j] of congestion factor [f.sub.j], as

[mathematical expression not reproducible](6)

4.3 Description of FARS

In this paper, our goal is to design an efficient routing strategy that can improve the fairness of delivery amount among nodes as much as possible along with guaranteed data delivery. After analyzing the factors related to node fairness, we use MADM algorithm based on entropy method to calculate the weight of every factors. And then, the gains of m candidate nodes can be obtained by Equ.(7).

[mathematical expression not reproducible].(7)

When a node carrying data packets finds other nodes within its communication range, it will determine the total number m of these nodes. The variable of m denotes the number of nodes which are the candidates of relays. Then, their respective three factors, namely historical data delivery amount, residual sequence length and contact strength, will be shared among them. Next, a decision matrix will be formed and MADM based on entropy method can be made. And lastly, the gain of each node can be calculated according to the Equ.(7). The gain of each node is sorted by descending order, and the nodes carrying data will forward the data to the nodes with larger gains. An example for FARS is expressed as Fig. 3, and Table 1 illustrates our forwarding strategy in detail.

From Table 1 and Fig. 3, it can be seen that the nodes carrying packets is responsible for collecting three factors of all nodes it encountered at the same time, building decision matrix and making routing decision. Three factors, including historical data delivery amount and residual sequence length, are fully considered when selecting relay nodes, the parameters of related factors can be obtained automatically using entropy method, and every factor of every encountered node will be updated after forwarding packets. So, our FARS can overcome the problem of subjectivity and poor dynamic adaptability in the existing weight distribution. In the next sections, we will use the experimental results and analysis to illustrate the effectiveness of our algorithm.

5. Simulation and Evaluation

Here, our FARS is evaluated with three typical utility-based forwarding schemes based on a real-life dataset and a synthetic mobile model. The compared algorithms and data sets are introduced first. Then, we describe the performance metrics and, finally, show the results.

5.1 Algorithms Compared

We evaluate the performance of FARS against three schemes, namely Epidemic routing[6], SimBet[12] and FairRoute[20]. Epidemic routing is a flooding multi-copy algorithm and has the optimal fairness degree, which is usually used as a baseline for comparison in the study of routing design for such kind of networks. SimBet used two social measures to design routing, and is a very typical example of greedy mechanism routing, which is appropriate as a comparison algorithm in this paper. FairRoute is the only work which devoted to the study of workload fairness during data routing for such kind networks in recent years, and has been cited for many times, which means that it has been widely recognized by the experts in the field of research. So these three schemes are chosen as comparison algorithms, and they are described as following:

* Epidemic routing[6]

It is a flooding multicopy algorithm which is often used as a baseline for comparison. If the energy and buffer are sufficient, this strategy can achieve the optimal success delivery rate, delivery delay [28] and fairness degree, while achieving the highest cost. But in the case of resource constrained, its delivery performance will be the worst[29]. So, its transmission delay and the balancing degree can be used as the baseline for evaluating several protocols.

* SimBet[12]

Its Utility is evaluated by combining two social measures (betweenness centrality and similarity) according to the potential social graph of contact traces. The betweenness of a node is defined as the proportion of shortest paths between all possible node pairs that pass through this node. Similarity is defined as the total number of common friends between nodes. We set parameter [alpha] = 0.5 according to the author's suggestion.

* FairRoute[20]

Inspired by the social processes of perceived interaction strength and assortativity, the authors introduced FairRoute, where messages are forwarded to users that have a stronger social relation and similar queue length with the destination node of the message. As mentioned in Section 2, FairRoute improves the balance of traffic load by controlling the queue size and is different from our focus on the fairness of data delivery amount.

5.2 Dataset Introduction

In our simulations, we make comparison our FARS with other algorithms based on a real-life mobility trace of Infocom05 gathered by the Haggle Project [25] and a synthetic trace obtained by TVCM model[26], referred to as TVCM in the following sections.

In Infocom05[27], the devices were distributed to 41 students attending the Infocom student workshop. Participants belong to different social communities (depending on their country of origin, research topic, etc.). The characteristics of Infocom05, such as inter-contact and contact distribution, have been explored in several studies [12, 13, 14] previously, to which we refer the reader for further background information.

For the synthetic contact model, we use the TVCM model to generate a synthetic dataset. It is a realistic model which is obtained from traces of wireless LAN (Local Area Network). The authors incorporate in these models two mobility characteristics: skewed location visiting preferences and periodical re-appearance. The TVCM includes communities that the mobile nodes are visited often. In recent years, there have been a lot of researches on this model[30,31]. In our simulations, we generate a synthetic mobility trace based on MIT parameters using TVCM model, where 100 nodes move in a square area 1000m x 1000m, the speed ranges from 1 to 3 m/s, communication range is 30m, and the maximum simulation time is one day. We also set time interval to 1s for update locations of nodes to avoid too large moving trace file.

These two datasets utilized are summarized in Table 2.

5.3 Performance Metric

In our simulation, we will compare and evaluate our routing strategy with the others in terms of the following metrics.

* Success delivery rate. This metric indicates the successful arrival rate of data packets, which can be computed as Equ.(8) illustrates:

[R.AUB.RATE] = [N.sub.DELIVED]/[N.sub.TOTAL] X 100% (8)

Where, [N.sub.DELIVED] represents the number of packets that are successfully delivered to the destination node and [N.sub.TOTAL] is the total number of packets generated during the simulation. It is preferred that this value becomes closer to 1. The higher value implies the more reliable network.

* Delivery cost. The average duplicates of a packet is often used to indicate delivery cost, which can be expressed by Equ.(9):

[D.sub.cos t] = [[].summation over (i=1)][N.sub.i,dup]/[] (9)

where [N.sub.i,dup] denotes the total duplicates of packet i. This value should be small as much as possible. The lower value implies the lighter network cost.

* Fairness index. It is a Jain's fairness index [32], which can be used to show the equilibrium degree of node loads in the network. It can be computed using the following equation:

Fairness = [([N.summation over (i=1)][L.sub.i,t]).sup.2]/N*[N.summation over (i=1)][]L.sub.i,t.sup.2] (10)

Where, [L.sub.i,t] denotes the historical data delivery amount of node [N.sub.i] at a certain moment t. It is preferred that this value becomes closer to 1. The higher value implies the better fairness among nodes in the networks.

5.4 Simulation Setup

In order to evaluate the performance of our FARS with other algorithms, we have developed a framework for MONs using Microsoft Visual Studio 2010. In the framework, simulator can read the mobility trace line by line and make a judgment about the existence of multi nodes encounter. During each time of simulation, the simulator will generate one packet after reading one line of mobility trace, and the total number of packets generated is 1000. For each packet, its source and destination nodes are all selected randomly, and its birth time is the real time when the line of mobility trace is generated. All generated packets have the same TTLs. If all the packets in the network expire, the simulation is finished. All nodes in dataset can be as source node or destination node. FIFO (First In First Out) strategy is used for every protocol in which the first packet reaching the buffer will be dropped when the buffer of node is full.

In order to fully evaluate our strategy, we have run our routing strategy and three compared protocols based on the datasets of Infocom05 and TVCM, respectively. In this section, we will give the detailed simulation results and analysis.

5.5 Comparative Results and Analysis

The results of success delivery rate based on four protocols are shown in Fig. 4. It can be seen that our FARS has achieved the relatively best performance in terms of success delivery rate compared with other three protocols. Taking Infocom05 as an example, the success delivery rate of FARS is 30% greater than Epidemic, 25% greater than SimBet and 15% greater than FairRoute. The reason is that: several main factors related to fairness, including historical data delivery amount, sequence length and contact strength, are fully considered in our FARS, which can avoid a large number of packets being delivered only by individual nodes with higher social property. Thus, our FARS can improve the success delivery rate of data packet by allowing more nodes with second high social property, lighter historical data delivery amount and relatively few buffer occupancy to participate in data delivery.

The fairness index based on four protocols is shown in Fig. 5. From this figure we can easily conclude that fairness index of FARS is the highest and the SimBet's is the least. The reason is that: several main factors that reflect current fairness state of nodes, including residual sequence length and historical data delivery amount, are fully considered in our FARS, but in FairRoute, there are only social relation and queue length being taken into account. When selecting relay nodes, the historical data delivery amount of candidate node is an important factor, and the nodes with smaller historical data delivery amount are more likely to be selected as relay node, which can avoid the nodes with more historical data delivery amount to delivery more data. It's not hard to understand why FARS got a relatively high fairness index. In order to show the superiority of FARS more clearly, we also give the contrast of sending data distribution of nodes in Infocom05 in Fig. 6 specifically. For comparison, sending data amounts have been normalized by dividing by the maximum number of sending data. From Fig. 6, it can also be concluded easily that FARS does greatly improve the fairness of data delivery amount among nodes.

Fig. 7 gives the average costs of the four strategies based on Infocom05 and TVCM trace, respectively. In order to make the metric of average cost more meaningful, we have excluded data packets that have not reached the destination node, and only calculate the average copy number of the packets that be delivered successfully. From this figure, it can be seen that Epidemic almost has the highest average cost, while the average cost of FARS is the lowest. The reason is that, the main factors which are related to the fairness of the nodes are fully considered when selecting relay nodes, so that the data exchange is limited to the nodes with about the same amount of the residual buffer and the historical data delivery, which can avoid generating a large number of data copies.

6. Conclusion

In this paper, we proposed a fairness-aware routing strategy named FARS that optimized delivery ratio and improved the fairness of nodes. Several main factors related to fairness were taken into account and the routing problem was modeled as a MADM problem, which made the selection of the relay nodes more reasonable. Extensive experiments were made to evaluate the performance of our FARS and other classic protocols based on Infocom05 and TVCM, and the results proved the validity and usefulness of our FARS. In future work, we will take measures to further shorten delivery delay and reduce the complexity of the algorithm.


This work is supported by the National Natural Science Foundation of China(61671144,61772175); the National Key Technology R&D Program of China (2015BAF32B04-3), the Joint Funds of the National Natural Science Foundation of China (U1404615, U1404602), the Key Science and Research Program in University of Henan Province(16A460018,17A520005), the Project of Basic and Advanced Technology Research of Henan Province of China (152300410081), the Natural Science Foundation of Henan Province(162300410098) and the Program for Innovative Research Team (in Science and Technology) in University of Henan Province (15IRTSTHN008), Open Funds of State Key Laboratory of Millimeter Waves (Grant No.K201504), China Postdoctoral Science Foundation (Grant No.2015M571637) and Youth Science Foundation of Henan University of Science and Technology.


[1] M.R.Schurgot, Cristina and k Jaffres-Runser, "Beyond Traditional DTN Routing: Social Networks for Opportunistic Communication," IEEE Communications Magazine, vol. 50, no. 7, pp. 155-162, July 2011. Article(CrossRef Link)

[2] W.Y.Shin, S.Y.Chung and Y.H.Lee, "Parallel opportunistic routing in wireless networks," Information Theory, IEEE Transactions on, vol.59, no.10, pp.6290-300, October 2013. Article(CrossRef Link)

[3] E.Ghadimi, O.Landsiedel, P.Soldati, S.Duquennoy and M.Johansson, "Opportunistic routing in low duty-cycle wireless sensor networks," ACM Transactions on Sensor Networks (TOSN). vol.10, no.4, pp.67, June 2014. Article(CrossRef Link)

[4] S.Batabyal and P.Bhaumik, "Mobility models, traces and impact of mobility on opportunistic routing algorithms: A survey," IEEE Communications Surveys & Tutorials, vol.17, no.3, pp.1679-1707, July 2015. Article(CrossRef Link)

[5] Fall K, "A delay-tolerant network architecture for challenged internets," in Proc. of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications,. pp.27-34, August 25-29, 2003.

[6] A. Vahdat and D. Becker, "Epidemic routing for partially connected ad hoc networks," University of Kansas, Lawrence. CS-200006, 2000.

[7] A. Lindgren, A. Doria, and O. Schelen, "Probabilistic routing in intermittently connected networks," ACM SIGMOBILE mobile computing and communications review, vol.7, no.3, pp. 19-20, August 25-29, 2003. Article(CrossRef Link)

[8] E. Talipov, Y. Chon, and H. Cha, "User context-based data delivery in opportunistic smartphone networks," Pervasive and Mobile Computing, vol. 17, no. 1, pp. 122-138, February, 2015. Article(CrossRef Link)

[9] H.A. Nguyen and S Giordano, "Context information prediction for social-based routing in opportunistic networks," Ad Hoc Networks, vol.10, no.8, pp.1557-1569, November 2012. Article(CrossRef Link)

[10] E. Bulut and B. K. Szymanski, "Exploiting friendship relations for efficient routing in mobile social networks," IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 12, pp. 2254-2265, 2012. Article(CrossRef Link)

[11] A. Mtibaa, M. May, C. Diot, and M. Ammar, "PeopleRank: social opportunistic forwarding," in Proc. of the 30th IEEE International Conference on Computer Communications, pp. 1-5, March14-19, 2010. Article(CrossRef Link)

[12] E.M.Daly andM.Haahr, "Social network analysis for routing in disconnected delay-tolerant MANETs," in Proc. of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 32-40, September 9-14, 2007. Article(CrossRef Link)

[13] E. M. Daly and M. Haahr, "Social network analysis for information flow in disconnected delay-tolerant MANETs," IEEE Transactions on Mobile Computing, vol. 8, no. 5, pp. 606-621, May 2009. Article(CrossRef Link)

[14] P. Hui, J. Crowcroft, and E. Yoneki, "BUBBLE Rap: social-based forwarding in delay-tolerant networks," IEEE Transactions on Mobile Computing, vol. 10, no. 11, pp. 1576-1589, November 2011. Article(CrossRef Link)

[15] P. Yuan, H. Ma, and H. Fu, "Hotspot-entropy based data forwarding in opportunistic social networks," Pervasive and Mobile Computing, vol. 16, pp. 136-154, January 2015. Article(CrossRef Link)

[16] Kaur, G, Hamsapriya, T, and Lalwani. P, "A new energy efficient queue based multipath load balancing in Ad hoc network," In Proc. of 2014 International Conference on Computer Communication and Informatics: Ushering in Technologies of Tomorrow, pp. 1-6, January3-5, 2014. Article(CrossRef Link)

[17] Fan, Xiaoguang, Victor OK Li, and Kuang Xu, "Fairness analysis of routing in opportunistic mobile networks," IEEE Transactions on Vehicular Technology, vol.63, no.3, pp.1282-1295, March 2014. Article(CrossRef Link)

[18] Takahashi A, Nishiyama H, and Kato N, "Fairness issue in message delivery in delay-and disruption-tolerant networks for disaster areas," in Proc. of 2013 International Conference on Computing, Networking and Communications, pp.890-894, January 28-31, 2013. Article(CrossRef Link)

[19] Mtibaa, Abderrahmen, and Khaled A. Harras, "Fairness-related challenges in mobile opportunistic networking," Computer Networks, vol.57, no.1, pp.228-242, January 2013. Article(CrossRef Link)

[20] Pujol, J. M., Toledo, A. L., and Rodriguez, P, "Fair routing in delay tolerant networks," In Proc. of IEEE INFOCOM 2009, IEEE, pp. 837-845, April 19-25, 2009. Article(CrossRef Link)

[21] Yang C, Stoleru R, "On balancing the energy consumption of routing protocols for opportunistic social networks," In Proc. of 2015 IEEE 34th International Performance Computing and Communications Conference, pp.1-9, December 14-16, 2015. Article(CrossRef Link)

[22] Le T, Kalantarian H, abd Gerla M, "A novel social contact graph based routing strategy for workload and throughput fairness in delay tolerant networks," Wireless Communications and Mobile Computing, vol,16, no. 11, pp. 1352-1362, August 2016. Article(CrossRef Link)

[23] Zanakis, S. H., Solomon, A., Wishart, N., and Dublish, S., "Multi-attribute decision making: A simulation comparison of select methods," European journal of operational research, vol.107, no.3, pp. 507-529, June 1998. Article(CrossRef Link)

[24] Shannon, C.E., "A mathematical theory of communication," The Bell System Technical Journal, vol.27, no.3, pp.379-423, July 1948. Article(CrossRef Link)


[26] W.-j. Hsu, T. Spyropoulos, K. Psounis, and A. Helm, "Modeling time-variant user mobility in wireless mobile networks," In Proc. of IEEE INFOCOM 2007, pp.758-766, May 6-12, 2007. Article(CrossRef Link)


[28] Anh N H M, and Hu C L, "Using Stationary Relay Nodes (Thrown Boxes) to Maximize Message Forwarding Performance in Delay-Tolerant Networks," International Journal of Science and Engineering, vol.4, no.4, pp. 33-40, 2014. Article(CrossRef Link)

[29] Spyropoulos T, and Sermpezis P, "Soft cache hits and the impact of alternative content recommendations on mobile edge caching," In Proc. of the Eleventh ACM Workshop on Challenged Networks, pp.51-56, October 3-7, 2016. Article(CrossRef Link)

[30] Jindal, A. and Psounis, K, "Performance analysis of epidemic routing under contention," In Proc. of the 2006 international conference on Wireless communications and mobile computing , pp. 539-544, July3-6, 2006. Article(CrossRef Link)

[31] H.Ma, G.Zheng, H.Wu, B.Ji, and J.Li, "EBRP: An Energy-Efficient and Buffer-Aware Routing Protocol for Mobile Crowdsensing Network," International Journal of Distributed Sensor Networks, vol.2016, pp. 1-14, February 2016. Article(CrossRef Link)

[32] Jain R, Chiu DM, and Hawe WR, A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer System, MA, Hudson, 1984.

Huahong Ma received her master degree in Signal and Information Processing in July 2005 at Yunnan University, China. Now, she is a Ph.D. candidate in Control Science and Engineering at Henan University of Science and Technology. Her main research interests are Crowd Sensing Network and Internet of Things.

Honghai Wu received the M.S and Ph.D. degrees from Beijing University of Posts and Telecommunications, in 2007 and 2015, and has been an assistant professor at Information Engineering College of Henan University of Science and Technology, China. His research interests include delay/disrupted tolerant networks, opportunistic networks and video delivery.

Guoqiang Zheng received the Ph.D. degree from Xi'an Jiaotong University, China, 2008. He is a professor at Henan University of Science and Technology on College of Electronic Information Engineering, China. His research interests include wireless communication technology, network communication protocol and software radio theory.

Baofeng Ji received the M.S and Ph.D. degrees in 2009 and 2013, and has been an assistant professor at Information Engineering College of Henan University of Science and Technology, China. His major is information and communication engineering and he is interested in signal processing, cooperative communications, WLAN and interference alignment.

Jishun Li received his Ph.D. degree from Shanghai Jiaotong University, China, 1996. He is a professor at Henan University of Science and Technology on College of Mechatronics Engineering, China. His main research direction is mechanical and electrical integration, measurement and control technology and instrument, signal processing, wireless sensor networks and so on.

Huahong Ma (1), Honghai Wu (1), Guoqiang Zheng (1), Baofeng Ji (1) and Jishun Li (2)

(1) School of Information Engineering, Henan University of Science and Technology Luoyang, 471023, China


(2) Henan Key Laboratory for Machinery Design and Transmission System Luoyang, 471023, China


(*)Corresponding author: Guoqiang Zheng

Received April 17, 2017; revised July 20, 2017; revised November 8, 2017; accepted December 10, 2017; published May 31, 2018
Table 1. The pseudocode of FARS

Nodes [N.sub.j],j=2,3,... m enter the wireless transmission range of
node [N.sub.1], which carried packets k (whose destination id node D)
at the same time;

  if [N.sub.j] = D then
        forwarding packet k to node [N.sub.j];
        update [f.sub.1], [f.sub.2], [f.sub.3] for node
        [N.sub.j], j=1,2,3,.. m ;
        Building decision matrix X, calculating gains [P.sub.i]
        for nodes [N.sub.i], i=1,2,.. m using entropy method;
        for j=2; j[less than or equal to]m; j++ do
          if [P.sub.j]>[P.sub.1] then
             forwarding packet m to node [N.sub.j];
                 update [f.sub.l], [f.sub.2], [f.sub.3] for node
                 [N.sub.j], j=1,2,3,.. m;

Table 2. Characteristics of dataset

Dataset                         Infocom05    TVCM

Duration(days)                       3          1
Number of experimental devices      41        100
Number of contacts                7907     212684
Average contact number/pair          9.64      42.97
COPYRIGHT 2018 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Ma, Huahong; Wu, Honghai; Zheng, Guoqiang; Ji, Baofeng; Li, Jishun
Publication:KSII Transactions on Internet and Information Systems
Article Type:Report
Date:May 1, 2018
Previous Article:Multi-homing in Heterogeneous Wireless Access Networks: A Stackelberg Game for Pricing.
Next Article:Exploiting Optimal Throughput of Adaptive Relaying Based Wireless Powered Systems under Impacts of Co-channel Interference.

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |