Landmark-Centric Routing for Wireless Sensor Networks in Mobile Delay Tolerant Environments

Abstract

Wireless sensor networks (WSNs) have wide applications in many fields sharing common grounds as their major technical challenges. This paper focuses on a high-level information association issue and designs an efficient routing protocol accordingly for delay tolerant mobile sensor networks (DTMSNs). In this paper, after making an analysis about the effect of social network theory on forwarding scheme and node mobility, we exploit landmark, a new social-aware metric indicating the geographical location corresponding to a node interest or a node community. To the best of our knowledge, this is the first work in which landmark is utilized to assist message forwarding in DTMSNs. Additionally, we propose the landmark-centric routing protocol utilizing the metric to accurately predict node mobility geographically. We can take full advantage of node mobility in our protocol while preserving the positive effects of existing social-aware metrics on protocol performance. Simulation results show that the proposed protocol achieves the highest packet delivery ratio outperforming SocialCast and doubling SGBR with more than 50% delivery cost reducing.

1. Introduction

Wireless sensor networks (WSNs) have wide applications in many fields such as military, environmental monitoring, medical, industrial, household, and other business areas. Due to the characteristics of WSNs, there are common grounds among such applications. Specifically, issues like dynamic topologies, demand of efficient routing protocols and distributed information processing approaches, network connectivity, and information association are all major technical challenges in industrial wireless sensor networks (IWSNs), delay tolerant mobile sensor networks (DTMSNs), and other WSN fields. This paper will focus on a high-level information association issue (i.e., the metric we propose and the way we derive its information among different nodes on a social layer) and accordingly design an efficient routing protocol for DTMSNs. As the key problems this paper deals with are also major challenges in IWSNs, our research will be helpful in the study of corresponding fields in IWSNs.

Message forwarding in DTMSNs employs the so-called “store-carry-and-forward” paradigm. That is, a node stores and carries the message until it meets another node, and then it forwards the message to that relay node. In such a case, the epidemic manner, that is, flooding, can help to deliver messages to all of their reachable destinations with the least end-to-end delay. However, too many replicas (of messages) are generated in the flooding scheme, which greatly increases the cost of the routing. To achieve leverage of the cost and the other metrics of routing protocols, it is suggested that messages should be disseminated via the nodes which are more likely to meet the destination nodes. After years of investigation, researchers have realized that nodes with specific social relationships tend to meet each other more often. Based on this intuition, existing routing protocols [1–8] exploit the sociality of nodes in the form of social interaction utilities, which measure the association between a node and a message from different aspects. Social interaction utilities are proven to be able to improve the performance of routing protocols [9]. Therefore, those protocols that employ social interaction utilities are called social-aware routing protocols. Further social-aware metrics have been exploited to make more efficient use of the sociality of nodes. For example, node community indicates strong social relationships among a crowd of nodes and has been utilized in several protocols such as [2, 6, 8]. Node interest introduces content-based multicast schemes to protocol design in DTMSNs [3, 8, 10]. In a content-based multicast scheme, nodes that are interested in the message might ignore those that disseminate the message, and it is not necessary for nodes that disseminate the message to know who is interested in their messages. Nodes sharing similar node interest are very likely to be colocated and form a node community where strong social relationships are assured. Therefore, content-based multicast schemes are inherently suited to social-aware DTMSN environments and are more effective than unicast schemes. As such, social-aware metrics improve protocol performance; on the other hand, node mobility is also highly correlated to protocol performance. Since DTMSN utilizes mobility-assisted routing scheme, the accurate prediction of node mobility can help to make right decisions on how to choose next carriers to take messages closer to the destination. As a matter of fact, nodes are always attracted by some specific geographical positions during movements because the goals (the spots where nodes are moving towards) have respective social meanings. Current DTMSN routing protocols concentrate on the relationships between nodes and messages from a social-aware aspect; thus, messages can be delivered to its destination via a series of relay nodes having some social interactions. However, if we can take the geographical aspect into consideration, numbers of additional relay nodes that have no social interactions but will arrive some spots nearby the message's destination can offer significant help to the routing decision (which we call geographical utility). Unfortunately, as far as we know, none of the existing DTMSN routing protocols has been concerned with this geographical aspect.

To compensate for this deficiency, we exploit landmark, a mobility-associated social-aware metric that can be used to accurately predict node mobility geographically on the basis of social network analysis. To give an overview of the existing social-aware metrics (node community and node interest) and the newly proposed metric landmark, the positive (social interaction utility, content-based multicast, and geographical utility) and negative (extra cost) effects they bring to protocol performance are listed in Table 1. As can be seen, all of the three metrics can employ social interaction utility; node interest and landmark can utilize content-based multicast, but only landmark can make use of the advantage brought by the geographical prediction of node mobility. The detailed relationships among node community, node interest, and landmark (including the extra cost) will be discussed in Section 2.

Table 1

Metrics and properties in social-aware routing protocol design.

Metric	Property
	Social interactionutility	Content-based multicast	Geographical utility	Extra cost
Node community	✓	✗	✗	Minimum
Node interest	✓	✓	✗	Medium
Landmark	✓	✓	✓	Maximum

Based on the observation in Table 1, our objective in this paper is to design a landmark-aware routing protocol which is more efficient than landmark-oblivious (but social-aware) protocols. To that end, we design landmark-centric routing protocol, which employs the geographical information of landmark to predict the mobility of nodes having strong social relationships with the landmark. We also employ social interaction utility and the content-based multicast scheme such that their positive effects on protocol performance can be preserved in our protocol. Simulation results show that our protocol reduces more than 50% delivery cost compared to SocialCast [8] and SGBR [6] and achieves the highest packet delivery ratio outperforming SocialCast and doubling SGBR. Further, we extend the protocol to a more complicated experimental scenario where the global landmark information is agnostic to nodes and show that even a rough estimation of landmark geographical information can get the protocol, outperforming SocialCast and SGBR. We summarize our contributions in this paper as follows.

• (i)

  We exploit landmark, a novel social-aware metric, to accurately predict node mobility on the basis of social network theory, such that mobility-assisted routing can benefit from it. As far as we know, our work is the first to exploit landmark and utilize it in protocol design for DTMSNs.

• (ii)

  We make an exhaustive analysis on the effect of social network theory on forwarding scheme and node mobility in DTMSNs. By this means, we elaborate the essential of landmark including why landmark exists, what its relationship with node community and node interest is, how to derive landmark from scratch, and how landmark predicts node mobility.

• (iii)

  We propose the landmark-centric routing protocol (LCRP). By comparing our protocol with SocialCast and SGBR, we show that LCRP achieves the highest packet delivery ratio which outperforms SocialCast and doubles SGBR, and reduces more than 50% of delivery cost. Further, LCRP is extended to the scenario where landmark is agnostic to nodes. Simulation results show that even a rough estimation of landmark geographical information makes LCRP outperform the two protocols.

The rest of the paper is organized as follows. In Section 2, we make an exhaustive analysis on the effect of social network theory on forwarding scheme and node mobility in DTMSNs and elaborate the essential of landmark. Section 3 presents the landmark-centric routing protocol in detail. In Section 4, we compare the performance of LCRP with SocialCast and SGBR. Related work is introduced in Section 5. Section 6 summarizes our conclusion and describes future work.

2. The Essential of Landmark

To understand the essential of landmark, that is, why does it exist, what is its relationship with node community and node interest, how to derive it from scratch and how does it predict node mobility, we will review DTMSNs from a viewpoint of high level. Figure 1 shows the DTMSN architecture merged with social network analysis. Social network theory affects both forwarding scheme module and node mobility module (the dashed boxes in Figure 1) in DTMSNs. The effect of social network theory on forwarding scheme (i.e., protocol performance) has been discussed in Section 1. Social network theory affects node mobility because most DTMSN scenarios are composed of humans, whose mobility is driven by their inherent social relationships.

Figure 1

The DTMSN architecture merged with social network analysis.

Landmark exists because in human mobility analysis, researchers find that people prefer to visit a few locations which bring more attractions to them [11–18]. The location where people spend a lot of time, for example, working place or home, indicates the inherent social relationships. People spend most of their time in their daily life staying at several of such locations which we name as landmarks.

Landmarks are attractive to people and people have interest in these locations. The interest here is exactly the node interest in DTMSNs. Therefore, landmark is actually the geographical location of a specific node interest. Node interest also drives nodes to form community structure; that is, nodes sharing similar interest are very likely colocated thus come into being a community and nodes belonging to the same community always have similar interest [8]. The habitat of the community members (the place where the nodes are colocated) is actually landmark as well. For example, in a campus scenario, the students who love “reading” always meet each other in the “library.” Here, these students compose the node community, “reading” represents the node interest and “library” is the landmark which is not only the location associated with node interest “reading” but also the habitat of these students (node community). With node interest “reading” we can use the content-based multicast scheme, while with only node community we cannot do that because the “students” community structure has not direct relation with node interest “reading.” However, landmark can utilize the content-based multicast scheme because the landmark “library” indicates the node interest “reading” inherently. We have briefly stated this at the content-based multicast part of Table 1.

In a word, the three metrics are associated with one another. Node community is the structural presentation of inherent social relationships among a crowd of nodes in DTMSNs. Node interest is the semantic meaning of node community and landmark, and landmark is the geographical location of node community and node interest. Therefore, we can derive all the three metrics if we have a method to get any one of them. Fortunately, there are community detection algorithms such as k-clique [19] that can detect the structure of node community and therefore are regarded as the interface of the social network (see Figure 1). After deriving the node community by using k -clique, we can attach it with a key word accounting for the corresponding node interest. However, in a distributed environment, the community detection algorithm has to be conducted concurrently at every node. Hence, the key word should be unified among different nodes with the help of more control messages (which indicate the extra cost in Table 1). Further, for deriving landmark, the corresponding community members’ favorite locations need to be studied and analyzed based on which the habitat of the community members can be extracted. This inevitably incurs extra control messages. In brief, we are able to derive landmarks from scratch at the price of control messages.

As landmarks are the habitat of the community members, this indicates that all the members would love to visit landmarks at high probability. Thus, for a content-based multicast scheme where the destination nodes are those who share similar node interest and are colocated at the landmark and form the community, if we keep forwarding the message towards the landmark, it will be very probably that destination nodes encounter the message carrier on their own initiative. Hence, we say that landmarks predict node mobility accurately. As messages are forwarded easily inside the community, they will be roaming nearby the landmark waiting for destination nodes to visit. Landmark-assisted routing is so directive that hopefully will have better performance.

3. Landmark-Centric Routing Protocol

3.1. Design Principle

We will discuss the design principle with a campus scenario. Figure 2 maps this scenario containing three landmarks, that is, playground, library, and laboratory. These three landmarks are associated with three interests, namely “sports,” “reading,” and “working.” Suppose that student A meets student B in the campus. A is carrying a message that needs to be forwarded to the community whose members are interested in “reading.” Following some social-aware forwarding scheme such as SocialCast [8], the message will be forwarded to the student who is more dynamic and has more contact with that community (the community associated with “reading”) members. The geographical aspect is totally oblivious to SocialCast. However, with the assistance of landmark, we can make a different decision about the relay choice.

Figure 2

A campus scenario.

Since the message is destinated to the community associated with interest “reading,” the members of this community (the destination nodes of the message) can always be found nearby the corresponding landmark, “library.” Based on this intuition, when the two students meet each other, the message will be hereafter carried by the student who will be more geographically closer to “library.” In general, to make movements in the campus, both A and B maintain a map of the scenario. When A encounters B, A tells B the destination community of the message as well as his nearest distance from the destination landmark in current movement epoch, which is estimated based on the map known by A. After that, B replies to A with his nearest distance correspondingly. Then the current carrier A will make decisions about who will be the new carrier of the message after this contact. In Figure 2, dest(A) and dest(B) present student A's and student B's destination spots of current movement epochs. It is clear that student B will arrive at a spot (dest(B)) being much nearer to “library” than student A, such that student B will carry this message after this contact. B has much higher probability to encounter the members of the community associated with “reading” than A because B is close to these members geographically. Once the message is delivered from B to such a member (which is one of the destinations of the message), it means that the message has reached the community associated with “reading.” In such a case, the message should not leave the community anymore because the community assures strong social relationships among its members.

The above idea seems to be very simple for random mobility models (such as random waypoint and random direction) because in these models nodes are always moving, and almost all contacts are detected between two moving nodes. However, researchers have found that contacts usually happen when the two people are staying somewhere [16] for at least a short while. In such a case, it is hard to decide which one should carry the message. Therefore, to utilize the landmark information, it is necessary to tune a little the setting of mobility models based on human mobility characteristics.

Most existing human mobility models characterize a movement epoch as follows. At the beginning of a movement epoch, a node chooses a destination and moves to it at a speed. After arrival, the node stays at the destination spot for a time period which is known as pause time. Till the end of the pause time, the node begins to choose a new destination and start the next movement epoch. In order to utilize landmark information during the pause time period, the ideal condition is that the pausing node knows where it will go in next movement epoch. Fortunately, this assumption might be reasonable because in real-life scenarios, human mobility is actually scheduled. For example, when a student is reading in the library, it is very likely that he has planned where to go when he finishes reading. As a result, we can tune the movement epoch of human mobility models: as soon as a node arrives at current destination and decides how long it will stay, its next destination is determined as well. With this tuning, we can design the landmark-centric routing protocol (LCRP) in detail.

3.2. LCRP

The pseudocode of LCRP is shown in Algorithm 1. LCRP works when a contact is happening. For example, when node i encounters node j, to employ the landmark utility, a piece of information called Landmark Vector should be exchanged before the data transfer. A Landmark Vector includes the node id n, dest(n), distance(n, L), com(n), the packet's id m, and label(m) (for each message in n's buffer, see Algorithm 1). When two nodes meet each other, they firstly drop expired messages, followed with exchanging their Landmark Vector. Then, for each message in each node's buffer, the protocol makes two decisions. First, if the other node is the destination of the message, the message should be delivered to it (Sink, line 4 in Message Delivery in Algorithm 1). Second, the new carrier of the message should be determined, as the Carrier Selection indicates (line 5 in Message Delivery in Algorithm 1).

Algorithm 1: Pseudocode of Landmark-Centric Routing Protocol.

Functions:

dest $(n)$ : the next pausing spot of node n

com $(n)$ : the label of community that node n belongs to

distance $(n$ , $L)$ : the closest distance of node n to L during the movement from current spot to dest $(n)$ , where L

represents the interest (corresponding to the destination community of m) landmark

copy $(m)$ : forward a duplicate of message m from current carrier to the other node

label $(m)$ : the label which describes the destination community of message m

new_carrier $(m)$ : the new carrier of message m, the other node should not carry m any longer

Messages:

DATA <id, tag, replicas, launch time, time to live>: id is the packet id, tag stands for the label of the destination

community (e.g., the interest), replicas depicts the remaining times that the message can be copied, launch time

indicates the time when this message is generated, and time to live is used to decide when the message's lifetime is expired.

Landmark Vector <n, dest $(n)$ , distance $(n,L)$ , com $(n)$ , m, label $(m)$ >: n is node id, m is packet's id

(for each message in n's buffer), dest $(n)$ , distance $(n,L)$ , com $(n)$ , and label $(m)$ are defined as above

Message Delivery (Invoked when node i encounters node j)

(1) drop packets with their lifetime expired in both nodes’ buffers

(2) the two nodes exchange the Landmark Vector with each other

(3) for all messages m in both nodes’ buffers

(4) Sink

(5) Carrier Selection

(6) end for

Sink

(1) if  m is in node i's buffer then

(2)   if j is a member of m's destination community and j has not received m before then

(3)  deliver message m to the application

(4)  node j records locally that message m has been received

(5)   end if

(6) end if

(7) if m is in node j's buffer then

(8)   if i is a member of m's destination community and i has not received m before then

(9)  deliver message m to the application

(10)  node i records locally that message m has been received

(11) end if

(12) end if

Carrier Selection:

(1) if com $(i)$  = label $(m)$   and com $(j)$  = label $(m)$   then

(2)  copy $(m)$

(3) end if

(4) if com $(i)$  = label $(m)$   and com $(j)$ ≠label $(m)$   then

(5)  new_carrier $(m)$   $\leftarrow i$

(6) end if

(7) if com $(\mathrm{i})$ ≠label $(\mathrm{m})$   and com $(\mathrm{j})$  = label $(\mathrm{m})$   then

(8)  new_carrier $(\mathrm{m})$   $\leftarrow j$

(9) end if

(10) if com $(\mathrm{i})$ ≠label $(\mathrm{m})$   and com $(\mathrm{j})$ ≠label $(\mathrm{m})$   then

(11) if distance $(\mathrm{i},\mathrm{L})$  < distance $(\mathrm{j},\mathrm{L})$   then

(12)   new_carrier $(\mathrm{m})$   $\leftarrow i$

(13) end if

(14) if distance $(\mathrm{i},\mathrm{L})$  > distance $(\mathrm{j},\mathrm{L})$   then

(15)  new_carrier $(\mathrm{m})$   $\leftarrow j$

(16) end if

(17) end if

LCRP utilizes a “one-to-community” multicast scheme which we consider as applicable in real-life scenarios. When a message is generated, it is labeled with the destination community. As in Algorithm 1, label(m) indicates the destination community of message m. With this label attached to message m, we can identify whether the member nodes of a community should receive the message. com(n) is the label of community that node n belongs to and is stored locally in node n's buffer. With the help of these two functions, a node is able to identify whether it should receive m (see Sink in Algorithm 1).

The main part of our protocol, namely, Carrier Selection, determines the relay of the message for each hop. As depicted in Carrier Selection in Algorithm 1, the community structure has a higher priority (than the landmark) to determine the next carrier of the message, because a node's being in a message's destination community indicates that it will more probably meet other destination nodes than an ordinary node. When neither of the two meeting nodes is belonging to the destination community, the new carrier of the message then will be chosen based on the landmark utility. In such a case, the message will be forwarded towards the geographical spot associated with the community, until one of the destination nodes receives it. After that, this destination node will carry the message till it expires. In order to facilitate the intercommunity's dissemination, the message replication strategy (line 2 in Carrier Selection in Algorithm 1) will accordingly be active when the carrier meets another destination node. Note that LCRP limits the amount of replicas for a specific message ID by setting it as a parameter.

3.3. Extended LCRP

LCRP is suitable for the network environments where the geographical information of landmarks is public knowledge; that is, each node in the network is aware of where each landmark is and which key word each landmark is associated with (e.g., “reading”). However, the scenarios where nodes are agnostic of landmark information exist. Suppose that a person enters an unknown environment, he is only familiar with his most favorite locations attracting him. For example, in Figure 3, favorite location (n) nearby a landmark indicates that current landmark belongs to the set of node n's favorite locations, which is stored locally by node n. In such a case, nodes need to study the global knowledge of the landmarks’ geographical information before using LCRP. The global landmark information can be obtained with the help of control messages, for example, a message containing the contact duration information that a node can ever get and the node's most favorite locations and corresponding visiting probabilities. With this information in hand, each node will be able to obtain the community structure by conducting distributed community detection algorithms such as k-clique and estimate the global landmarks’ geographical information through analysis.

Figure 3

A strange environment.

In fact, as we have verified the existence of landmark (Section 2), the status of landmark will be either aware to each node (called “aware”, e.g., the scenario in Algorithm 1) or not (called “agnostic”, e.g., the scenario in Figure 3). LCRP chooses different strategies on basis of these two different input sources of landmark information, as shown in Figure 4. For an “aware” scenario, we can employ LCRP directly. While for an “agnostic” scenario, we need to obtain the community structure and the landmark information through “control message exchange” and “analysis and estimation” as discussed above, such that the case will be transformed into an “aware” network environment. Note that the more accurate the estimation of geographical landmark information is, the better the protocol performs.

Figure 4

LCRP chooses different strategies based on the different input source of landmark information.

4. Performance Evaluation

In this section, we implement LCRP and compare the performance of LCRP with SocialCast [8] and SGBR [6]. We choose these two routing protocols for comparison because they are very effective protocols designed for DTMSNs, and both of them are social-aware but landmark-oblivious protocols. SocialCast utilizes social interaction utility and a content-based multicast scheme. SGBR utilizes social interaction utility. Because of the absence of node interest, SGBR is a unicast protocol. For the consistency of the comparisons, in the following simulations, we extend SGBR to a multicast protocol; that is, we set the packet generation in SGBR the same as that in LCRP and SocialCast. Since packets are routed individually in SGBR, this extension will not degrade its performance.

We choose three metrics to evaluate the performance of forwarding protocols. They are delivery cost (cost), packet delivery ratio (pdr), and average delay (delay). The delivery cost indicates the price of forwarding a data packet successfully and accounts for the efficiency of the protocol. The delivery cost is calculated by the ratio of “the amount of received control packets plus the amount of data packets” replicas’ to “the amount of received data packets.” Packet delivery ratio is actually the successful rate of forwarding data packets and average delay indicates how long a data packet will be received by the destination node. Packet delivery ratio and average delay both account for the effectiveness of the protocol. Packet delivery ratio is calculated as the ratio of “amount of received data packets” to “amount of generated data packets”. Average delay is calculated as the ratio of “sum of delay of all received data packets” to “amount of received data packets.”

With a network environment similar to LCRP, SocialCast [8] chooses CMM [13] to evaluate its performance. However, CMM has been proved defective, that is, specifically, in the majority of configurations all users collapse into a single location; this practically overthrows the initial setting of the system [11]. HCMM [11] is subsequent to CMM and gets rid of this defect. Hence, we choose HCMM as the human mobility model to represent the default network environment of LCRP (i.e., “aware”). In HCMM, the network area is set to be 5000 meters × 5000 meters. There are 100 nodes in the network, each node has a transmission range of 250 meters. These settings are able to provide a sufficiently sparse and disconnected network. As in [8], we assume that half of the nodes are publishers and all nodes are subscribers, and messages are published during the interval [3000 s, 4000 s] (500 s longer than [8]) over a total period of 28800 s (8 hours), with a publishing interval of 60 s. The amount of node interests (one interest corresponds to one community which is predefined in HCMM) in the network is 4. When a node is moving, the speed is uniformly chosen at random over the range of 1 to 6 meters per second, and the pause time is set to be 10 seconds. Each node has a large enough buffer such that messages will not be discarded due to the buffer size. Simulations are run in a discrete event simulator written in C++.

About the parameters of the routing protocols, the number of replicas is set as 1 (in LCRP), 32 (in SGBR) and 5 (in SocialCast), respectively. That is, in this scenario, LCRP does not employ the message replication strategy. There is only one copy for each message ID. LCRP relies very little on the message replication strategy among these three protocols. SGBR depends on the message replication strategy with a binary mechanism, such that the value is set as 32. The dependency of SocialCast on the message replication strategy falls in between LCRP and SGBR; hence, we assign a value of 5 to SocialCast. In SGBR, the updating factor, which is used to adjust the degree of two nodes’ connectivity, is set as 0.45; the aging constant measuring the decay of two nodes’ connectivity is set as 0.98; the connectivity threshold and dropping threshold, both of which are used to help a node make a decision of forwarding or dropping a message, are assigned the value of 0.5. While in SocialCast, the weight of change degree of connectivity utility is set to be 0.25, the weight of colocation utility is set to be 0.75, and the hysteresis threshold which forbids that the message is bounced back and forward between nodes with similar fluctuating utilities is set as 0.2. Since the carrier selection of SocialCast is executed periodically, we set the interval as 1 second.

For each data, we average the results over 20 runs, using different seeds for each scenario. The simulation results are shown in Figures 5–7. TTL indicates the time-to-live of messages, which is measured by seconds as in [6]. In Figure 5, a low cost means a better performance. As can be seen, LCRP reduces more than 50% cost comparing to SGBR and SocialCast (these two protocols hold similar cost). In Figure 6, a high pdr indicates a better performance. Thus, LCRP and SocialCast have better performance than SGBR (both of LCRP and SocialCast double the pdr of SGBR, and LCRP is even better according to Figure 6). In Figure 7, a low delay accounts for a better performance. We can see that LCRP and SGBR both have lower delay than SocialCast. To view the three metrics as a whole, we will find that LCRP has the best performance among the three protocols. The comparison results also show that LCRP has the highest pdr (outperforms SocialCast and doubles SGBR) with more than 50% delivery cost reduction, indicating an outperformance of landmark-aware scheme comparing to landmark-oblivious scheme.

Figure 5

Three protocols’ delivery cost in the “aware” experimental scenario.

Figure 6

Three protocols’ packet delivery ratio in the “aware” experimental scenario.

Figure 7

Three protocols’ average delay in the “aware” experimental scenario.

We also evaluate the performance of extended LCRP with an experimental scenario (i.e., “agnostic”). For such a scenario, we choose SWIM [16] as the human mobility model because SWIM is a model depicting such a network environment which is proven to be very excellent in characteristizing human mobility, especially the community structure. In SWIM, the network area, amount of nodes, node transmission range, and publisher percentage are set the same as those in HCMM. However, the forming of community structure in SWIM is spontaneous. Hence, we prepare a relatively long time (three days or 259200 seconds) for the forming and steady of community structure. Keeping the same message publishing duration and interval as in “aware” network scenario, we set the 200000th second as the beginning point in time for message publishing. Since the SWIM itself does not provide the community structure results, we utilize the k-clique community detection algorithm. k-clique [19] has two parameters, namely, k and the threshold Tth. We are not going to dig deeply into these two parameters here due to space limitation. In brief, the two parameters can be used together to guarantee the strength of social relationships among members of the detected community. In our simulations, in order to run the distributed k-clique at any moment, we abandon Tth and define a scale parameter β instead. If we run the distributed k-clique at time T, the threshold value Tth will be calculated as $\beta \times T$ . In the following simulations, we set k as 4 and β as 0.3. Also, for an unambiguous community structure, we set the homes of 20 nodes (uniformly and randomly chosen from all the 100 nodes) nearby each other, for example, chosen from the same cell. The network is divided into 29 × 29 cells according to SWIM, the coefficient α (see [18]) is set to be 0.25, the pause time is chosen from a truncated power law over $[10,1440]$ seconds with slope 1.45, and the flight time is set to be 10 seconds. Due to the policies of our simulations, the mobility model settings produce the same effect to the three protocols, thus these settings only offer an “agnostic” scenario where community structure is distinct but do not influence the comparison results of the three protocols. For all the three protocols, the system begins k-clique community detection at the 200000th second, and each detected community then has a label. Publishers tag each message with this label indicating the destination community. As communities are mutually independent, messages with different labels are forwarded independently. To simplify the network model, we set one distinct community (the 20 nodes whose homes share the same cell), such that the label will be associated with this community and all its member nodes are subscribers. Node buffers are also set to be infinite.

Note that in SWIM a node knows its own favorite locations but it has not the knowledge of the overall network. Therefore, as mentioned in Section 3.3 and Figure 4, nodes need to exchange some key information with the help of control messages, using which they can conduct k-clique community detection algorithm locally and estimate the geographical information of landmarks by analysis. In this experimental scenario, we employ a rough method to estimate the geographical information of landmarks; that is, each node keeps the community structure detected by k-clique; thus, the geographical information of each community landmark known by the node can be calculated as the geographical centre of the community members’ most favorite locations approximately.

The parameters of the three protocols are the same as the above except that the number of replicas is set as 4 in LCRP. Figures 8–10 depict the simulation results of protocol performance in an “agnostic” experimental scenario (SWIM mobility model). In Figure 8, we can see that the cost of LCRP decreases with TTL. The reason is that LCRP requires amounts of control messages to assist in deriving the landmark information in such a scenario. With the TTL getting larger, LCRP is able to forward increasing amount of messages (see Figure 9). However, the amount of control messages remains constant, such that the overhead per message decreases. Consequently, from Figures 8–10, we can see that the advantage of LCRP becomes more and more distinct with increasing TTL.

Figure 8

Three protocols’ delivery cost in the “agnostic” experimental scenario.

Figure 9

Three protocols’ packet delivery ratio in the “agnostic” experimental scenario.

Figure 10

Three protocols’ average delay in the “agnostic” experimental scenario.

We evaluate the performance of LCRP over SocialCast and SGBR in this section. Since we exploit landmark metric in this paper and our motivation is using landmark to design protocols achieving higher pdr than landmark-oblivious (but social-aware) protocols with reducing (or, at least, not increasing) cost. The comparison results indicate that, for the default scenario, LCRP evidently outperforms the other two protocols with pdr exceeding SocialCast and doubling SGBR while reducing more than 50% cost. Even for the scenario where global landmark information is agnostic to nodes, a roughly extended LCRP outperforms the other two protocols as well. Therefore, we can conclude that landmark is able to improve the performance of routing protocols in DTMSNs while preserving the positive effects of existing social-aware metrics on protocol performance.

5. Related Work

Up to now, most existing routing protocols have various connections with social network theory because social-aware forwarding improves routing performance in comparison with social-oblivious protocols. ContentPlace [7] is a social-aware, content-based, and utility-based routing protocol. Utility indicates the association between a node and a message. In ContentPlace, the utility is calculated based on the social strength of the relationship between the node/message and the communities. When two nodes meet each other, each node computes the utility values of all the messages in both nodes’ buffers and selects the set of messages that maximizes the local utility of its buffer.

SocialCast [8], so far as we know, is the first routing protocol that utilizes publish/subscribe (pub/sub for short, a content-based multicast scheme) paradigm designed for DTMSNs. It is very effective so that we compare our protocols’ performance with it. SocialCast is designed with social-aware and utility-based as well. In SocialCast, community structures are prior defined and one community corresponds to one interest/subscription. The utility is defined as a weighted sum of relevance (to subscription) and dynamic of nodes. More importantly, the Kalman-filter is utilized so that each utility value is a predict value, which even strengthens the effectiveness.

Hui and Crowcroft [2] propose a social-aware and community based routing protocol named BUBBLE. A message generated from the source node is firstly forwarded to the community where the destination node belongs based on the global centrality and then to the specific node based on local centrality. MOPS [4] utilizes social-aware, community based, and pub/sub paradigm simultaneously as SocialCast. It adopts the closeness metric to conduct community detection and messages can be forwarded from intracommunity to intercommunity then to all destination nodes. The data transferring from intracommunity to intercommunity is similar to BUBBLE.

To explore the friendship social interactions, Bulut and Szymanski [5] propose FBR. The authors create a new metric (social pressure metric, SPM) to evaluate friendship. Further, they use this metric to detect friendship communities so that data forwarding among friends may achieve high packet delivery ratio and low overhead. Not quite different from the above mentioned protocols, SocialElection [20] is also a social-aware routing protocol with pub/sub paradigm. Gao and Cao [3] utilize social-aware, pub/sub, utility-based and interest-based forms in protocol design. The authors concentrate on node interest such that the utility is calculated with a node interest metric and a data description metric. SADD [21] is a routing protocol similar to user centric, with the absence of pub/sub paradigm.

SGBR [6] is a social-aware unicast routing protocol. It adopts the characteristic of community but not the specific community structure. SGBR utilizes the feature that nodes belonging to a community tend to meet more often, but SGBR does not conduct any community detection algorithm in protocol design. In [10], the authors try to utilize the cosine similarity of node interest profile to assist data forwarding in social-aware routing protocols, because they believe similar node interest profiles lead to close social interactions. The mobility model they use is SWIM as well. However, they do not consider the correlation between the node interest profile and the corresponding landmarks in the network area. We argue that the interest profile should be correlated to the mobility model; that is, interests should have landmarks.

Fan et al. [22] notice users’ geolocation preference and propose the concept of geocommunity and geocentrality. Their design aims at broadcasting data from a superuser to other users. Geographical aspect is concerned in this work to tackle broadcasting in DTMSNs with heterogeneous nodes.

As can be seen, the design principle of our routing protocol is different from existing routing protocols. Although some of existing protocols utilize pub/sub paradigm or concentrate on node interest, our protocols adopt diverse methods; that is, we design a “one-to-community” data dissemination mode based on the content-based multicast scheme and explore the interest landmark to assist message forwarding. There are researches that support our design principle. For example, Díaz et al. have proved that the utility of node interest can assist in improving the protocols’ performance in [9]. Further, the authors of [23, 24] claim that different communities exhibit different interests for different locales, and different communities are attracted to certain physical locations with different intensities and clients form community geographically. All of these support our analysis about the relationship among interest, community, and landmark. In addition, Pagani and Rossi [25] evaluate several utility-based forwarding protocols in different mobility scenarios. Their conclusion is that researchers can make the choice of the appropriate policy for defining the utility component according to the mobility scenarios. This perspective supports our solution in this paper. We choose different strategies to implement LCRP according to the mobility scenarios where the input source of landmark information may be different.

6. Conclusion

In this paper, we make an exhaustive analysis on the effect of social network theory to forwarding scheme and node mobility in DTMSNs. We indicate that communities and interests are correlated with geographical locations in the network area and exploit the so-called landmark metric. After revealing the essential of landmark, we propose the landmark-centric routing protocol and extend it to a more complicated scenario. To validate the landmark metric and our protocol, we evaluate the performance of LCRP in comparison with two outstanding DTMSN routing protocols. Simulation results indicate that our protocol outperforms the other two protocols with pdr exceeding SocialCast and doubling SGBR while reducing more than 50% cost. Even for the scenario where global landmark information is agnostic to nodes, a roughly extended LCRP outperforms the other two protocols as well, which means that the landmark metric and our protocol are effective.

For the “agnostic” network scenario, we roughly estimate the geographical landmark information to implement LCRP. Evidently, a more accurate estimation will lead to a better performance of LCRP, which will be left as future work.