A Collaborative Self-Governing Privacy-Preserving Wireless Sensor Network Architecture Based on Location Optimization for Dynamic Service Discovery in MANET Environment

Abstract

Due to the characteristics of a MANET, none of the existing solutions for service discovery work well in decentralized mobile environments. In this paper, we propose a collaborative self-governing privacy-preserving wireless sensor network architecture to address the issue of service discovery in MANET environment. The proposed architecture is able to dynamically adjust the working modes between directory-based and directory-less modes according to the network status of a MANET. The dynamic network status of a MANET is monitored by a wireless sensor network. Two location optimization algorithms are developed for topology control and the preservation of user location privacy. Simulation results show that the proposed architecture can greatly improve the performance of service discovery.

1. Introduction

With the booming development of the Internet, more and more services are deployed on the web. Hence, the need for service discovery mechanisms is becoming increasingly urgent. Much research attention has been drawn to the designing of service discovery mechanisms. Meditskos and Bassiliades [1] developed a web service discovery framework using OWL-S advertisements. Junghans et al. [2] provided a review of formalisms for semantic web service discovery and developed distinct formalisms to describe functionalities and service requests. The proposal presented by Santhana and Balasundaram [3] employed k-means clustering to address the problem of web service discovery. In addition, service discovery methods which deal with functional and nonfunctional properties of services were also extensively studied [4]. Some techniques for web service discovery were contributed in the form of a patent [5]. In general, the service discovery could be conducted in three styles: reactive way, proactive way, and hybrid way. In reactive way, a user node which has a need of some kind of service issues a service query. Other nodes which received the service query may answer it by issuing a service reply. The nodes which answer the service query could be a directory node, service node, or user node. In proactive way, service information is periodically advertised by service nodes. Both directory nodes and user nodes will receive the service advertisements. If a user node which has a potential need of service happens to receive an appropriate service advertisement could directly use the service information, rather than issuing a service query to search service information.

Generally, the reactive way only generates network traffic when there is a need. To some degree, this leads to as less message overhead as possible. During the query process, the original service query might be forwarded by a node which is unable to answer it. In order to avoid flooding the whole network, it is necessary that a subtle time-to-live (TTL) value should be set. Here, the dilemma is that a small TTL value will limit the transmission range and then brings bad influence in the service discovery, while a large TTL value will expand the transmission range and then floods the query to a wide area. Since service nodes do not actively issue service advertisements in reactive way, both the latency and the failure rate of the service discovery are high. Similarly, the TTL value of periodic service advertisements should be cautiously selected in proactive way. Moreover, in order to mitigate the flooding effect caused by periodic service advertisements, the frequency of service advertisement should be elaborately tuned. As service nodes periodically issue service advertisements no matter whether there is a need for service information, both the latency and the failure rate of the service discovery in proactive way are lower than that in reactive way. However, this in turn constantly imposes a certain amount of message overhead on the whole network. As both the reactive way and the proactive way have advantages and disadvantages, the hybrid way combines the two complementary ways. However, since disadvantages of both ways are introduced, how to achieve a tacit cooperation of the two ways is challenging.

In this paper, we propose a collaborative self-governing privacy-preserving wireless sensor network (WSN) architecture for dynamic service discovery in MANET environment. Our model is based on the famous Chord protocol and could operate in both directory-based mode and directory-less mode. The WSN which consists of directory nodes greatly facilitates the service discovery. The topology control for the WSN is conducted through local location optimization and global location optimization. The location privacy of a user is preserved based on a direction-probing algorithm used in the local location optimization. The key function of our model is the autonomic mode switch between the directory-based mode and the directory-less mode.

The rest of this paper is organized as follows. Section 2 provides the related works about service discovery architectures and discusses the existing problems. Section 3 elaborates our collaborative self-governing privacy-preserving service discovery architecture. In Section 4, we evaluate the proposed model by simulation and present a detailed analysis of the simulation results. Section 5 concludes the paper and highlights the future work.

2. Review of Service Discovery Architectures

Traditionally, service discovery architectures are classified into two types: directory-based architecture and directory-less architecture.

2.1. Directory-Based Architecture

In directory-based architecture, a directory structure could be implemented either in centralized manner or in distributed manner.

For a centralized directory, all service information is stored in the same place. All services in the whole network should be registered with a centralized repository. At the same time, the centralized repository is responsible for all service queries. Examples of centralized directory are as follows: the service location protocol (SLP) [6] suggested by IETF, the Jini technology [7] developed by Sun Microsystems, the salutation protocol [8] proposed by IBM, the universal plug and play device architecture (UPnP) [9] specified by Microsoft, the Bluetooth service discovery protocol [10] presented by Bluetooth consortium, the secure wide-area service discovery service (SDS) [11], and the intentional naming system (INS) [12]. Generally speaking, a centralized manner means attractive simplicity, inevitable single point of failure, poor scalability, and weak mobility. On the contrary, a distributed manner indicates certain complexity, robustness, good scalability, and strong mobility. Taking the characteristics of a MANET environment into consideration, we hold that the distributed manner is preferable. Hence, we omit the details of the above centralized directories and focus on the instances of distributed directory.

For a distributed directory, the problem of wide-area service discovery needs to be focused on. There are two aspects to the concept of wide-area service discovery: one is the replication of service registration, and the second is the forwarding of service query. Since directory agents reside in various locations, the service registrations they received are usually different. Then, each directory agent only knows about a portion of service information in the whole network. If there is no replication scheme in a distributed directory, service information is only locally available around the particular directory agent with which it was registered. Rather, a distributed directory with a replication scheme enables the communication among directory agents. By replication of service information, each directory agent becomes aware of all services registered in the whole network. Suppose there is a distributed directory which does not support replication of service registration. For the purpose of improving the success rate of the service discovery, it is reasonable that a service query which could not be answered locally should be forwarded to another directory agent. This operation relies on a forwarding scheme provided by the distributed directory. Recently, a considerable amount of work has been done on the distributed directory. Based on the organization of the directory agents, distributed directory could be divided into four categories: backbone-based [13–15], cluster-based [16–19], DHT-based [20, 21], and other distributed directories [22, 23].

Kozat and Tassiulas [13] provided a virtual backbone which facilitates the registration and search of services. The virtual backbone is constructed by a subset of nodes in the network, and these nodes compose a dominating set. Though there is no replication scheme, nodes belong to the backbone forward service queries to each other when they cannot be answered locally. However, there is a flaw that the destination of the forwarding operation is random. The proposal [14] presented by Sailhan and Issarny remedied the flaw by forwarding an unsolved service query to the nodes which are expected to possess the corresponding service information. The selection of destination to which a service query is forwarded is based upon the exchange of profiles among directory agents. The protocol [15] proposed by Koubaa and Fleury aimed to build a backbone which could cover all service information in the whole network. Nevertheless, as only a service provider is allowed to join the backbone, it is likely that an integral backbone might be broken down into several isolated parts. In this case, the global communication of the backbone is cut off. Consequently, the disposal of service queries is crippled.

Klein et al. [16] presented a semantic overlay of hierarchical service rings. A service ring is composed of a cluster of service providers and is considered to be a directory, since the functions of accepting service registration and answering service query are contributed in the form of a service ring. Although replication is not supported, a service ring forwards a service query which it is unable to answer. Klein and König-Ries [17] proposed that services are dynamically organized into multilayer clusters. The authors make an assumption that there exists a common ontology which could be used to describe the services within the whole network. Upon receiving a service query, a node checks its leaf-level cluster. If the service query cannot be answered, higher-level clusters are examined in the pursuit of a suitable service. It is worth mentioning that nodes are clustered based on the physical proximity and the semantic proximity [16, 17]. Schiele et al. [18] suggested that clusters are formed according to the similarity of mobility patterns. A clusterhead is always ready to answer service queries. The remaining nodes in a cluster go to sleep when idle. Tyan and Mahmoud [19] presented a service discovery approach which clusters the nodes according to physical proximity. A gateway of each cluster plays the role of a directory. Wide-area service discovery is feasible since an unsolved service query could be forwarded to another gateway.

As mentioned above, when a replication scheme is not present, an unsolved service query should be forwarded to other nodes. However, it is not easy to determine an appropriate destination for an unsolved service query. Unlike backbone-based and cluster-based models, an exciting feature that the DHT-based approaches inherently possess is hash techniques which could facilitate the provision of location information. Seada and Helmy [20] developed a rendezvous-based architecture. The basic idea is that the whole network is divided geographically and each geographical area is responsible for a portion of service information in the network. Service information is mapped to a geographical area according to a hash-table-like mapping scheme. A part of nodes within a geographical area are selected to maintain the mapped information. Since the hash function used by service query is the same as the hash function used in the mapping of service information, the proper forwarding destination of a service query could be readily obtained by a directory agent. Sivavakeesar et al. [21] described a mechanism which is similar to the approach proposed in [20] except for the fact that the mapped information is handled by all nodes within a geographical area.

Other approaches which do not involve backbone, cluster, or DHT techniques are also notable. Lee et al. [22] presented a service discovery and delivery protocol called Konark. The proposed method is decentralized and targeted at a MANET environment. Under a pure peer-to-peer design, each node in the network has a database which stores the service information provided by other nodes. Jeong et al. [23] developed an ad hoc name service (ANS) system for IPv6 MANET to facilitate the service discovery and name-to-address resolution. It is assumed that each node could be configured with a site-local scoped IPv6 unicast address by ad hoc stateless address autoconfiguration [24, 25].

2.2. Directory-Less Architecture

As a MANET environment is born with no infrastructure, it is argued that a directory-less architecture is more appropriate than a directory-based architecture [26]. However, there is an important distinction between a directory-less architecture and a directory-based architecture: there are no directory agents in a directory-less architecture. Namely, there are only user agents and service agents in the whole network. The missing of the organization and maintenance for directory agents reduces the complexity of service discovery architecture: user agents issue service queries and service agents issue service advertisements. Though service queries are generated on demand, the number of replicates of a service query during the forwarding process could become very large. Furthermore, in order to achieve a decrease in latency and an increase in service availability, the number of service advertisements is also considerable. In this case, a pursuit of good service discovery performance might be prone to bring about a serious flooding problem.

Much research attention has been drawn to the operations of service queries and service advertisements. Chakraborty et al. [27] proposed a group-based service discovery (GSD) protocol for pervasive environment. In general, the protocol consists of two components. The first component is a P2P caching scheme dealing with the spread of service advertisements. A node stores the received service advertisements in a local database called service cache. A least-remaining-lifetime cache replacement policy is used to update the cache. The second component is a group-based intelligent forwarding strategy for regulating the forwarding of service queries. In specific, an unsolved service query is just forwarded to the nodes which possess matching service information. The determination of destination nodes is based on the information contained in the service cache. The reply info caching enhanced flexible forward probability (RICFFP) service discovery protocol presented by Gao et al. [28] also consists of two parts: reply info caching (RIC) and flexible forward probability (FFP). The RIC is a technique similar to the P2P caching scheme in [27]. In particular, a node could cache the service information in a received service reply. For a received service query, if there exists a match in the cache, the service query could be answered conveniently. The essence of the FFP is that the forward probability of a service query is in reverse proportion to the number of hops it has already traveled. Nedos et al. [29] introduced an optimal forwarding mechanism for service advertisements. By monitoring the neighbors, a node merely forwards the received service advertisements to a part of its one-hop neighbors. Therefore, the broadcasting of service advertisements is turned into several unicasts. Nidd [30] set the target application environment to single-hop short-range wireless systems. For each node, the broadcasting of service advertisements is scheduled to take place at regular intervals. The task of scheduling is performed by an exponential back-off algorithm. The dissemination strategies proposed by Campo et al. [31] and Lee et al. [32] are similar that they both cache service information contained in received service advertisements. Moreover, only service advertisements which are not expired and have not been seen recently are broadcasted.

2.3. Problems

As the directory-based architecture and the directory-less architecture are complementary, hybrid architecture is another option for service discovery in a MANET environment. For a node in hybrid architecture, if there is no directory agent within its radio range, both service advertisements and service queries are sent in the same way of directory-less architecture. Otherwise, service information contained in service advertisements is registered with directory nodes. Service queries could be answered by both directory agents and service agents. Though a great deal of research has been done to the above three types of service discovery architectures, it is still controversial that which one is superior to the other two. It is recognized that the difficulty of comparison is largely due to the characteristics of a MANET environment. For instance, the nodes in a MANET might possess various degrees of mobility. Moreover, both the velocity and the moving direction of a node are unpredictable. The regular communication among nodes in the whole network should not be interrupted by the node mobility. Since a MANET is self-organized, there are no constraints on the joining and leaving of a node. The appearance of a new participator or departure of an existing participator could bring a significant change to the network topology. Again, the communication in the whole network should not be influenced.

Considering a MANET with directory-based architecture, the TTL value of service query should at least guarantee that a service query could arrive at a directory node. If the frequency of service query is low, the message overhead introduced by service registration and directory maintenance is likely to surpass the message overhead brought in by service advertisement with a directory-less architecture. For directory-less and hybrid architectures, large TTL values of both service query and service advertisement could improve the performance of service discovery. However, there is a compromise between flooding problem and performance enhancement. When there are a large number of service queries, a directory-less architecture has to increase the number of service advertisements. But since both service query and service advertisement are simply broadcasted, a risk of network congestion still could not guarantee a satisfactory performance of service discovery. Ververidis and Polyzos [33] pointed out that it could be useful to develop a flexible architecture which is able to adjust its parameters and working modes between directory-based and directory-less modes according to the status of a MANET.

3. A Collaborative Self-Governing Privacy-Preserving WSN Architecture for Dynamic Service Discovery

3.1. Network Model

3.1.1. Nodes

In our architecture, there are three possible roles for a mobile node: service provider, service requestor, and service directory. In order to perform the operations which facilitate the service discovery process, the above three types of nodes are equipped with three key components service agent (SA), user agent (UA), and directory agent (DA), respectively. For the sake of simplicity, in the remainder of this paper, we refer to service provider nodes, service requestor nodes, and service directory nodes as SAs, UAs, and DAs, respectively. To facilitate the presentation of our model, we consider a MANET consists of DAs, SAs, and UAs. In addition, there is a WSN composed of all DAs.

3.1.2. Directory Agent

Each DA is a wireless sensor node. DAs offer a place storing service information and SAs register service information with DAs. Then, DAs answer the service queries issued by UAs based on the service information they have. The existence of DA is to improve the effectiveness of the service discovery architecture. The WSN constituted by all the DAs is based on Chord [34]. Chord is a scalable distributed lookup protocol which has been applied to service discovery [35–37]. The most important operation that Chord provides is mapping a given key onto a node. By consistent hashing, each data item could be associated with a unique key. The $〈key,dataitem〉$ pair is stored at the corresponding node to which the key maps. The mechanisms facilitating the joining and leaving of node could guarantee the normal operations of the whole network. In classic sensor networks, all sensor nodes are scheduled to send the obtained information to a single sink node. Though this approach eases the routing work, authors of [38, 39] point out that the nodes which are in vicinity of the sink node bear heavy work load of relaying. As a result, the batteries of these nodes are drained out much earlier than other nodes. Thus, there is no sink in our WSN of all the DAs. The status of the whole network is summarized and presented in a monitoring token. In clustered sensor networks, the principle of clusterhead rotation is studied extensively in [40–42]. However, the election and rotation of clusterhead inevitably introduce extra overhead. On the contrary, since the consistent hashing mechanism employed by Chord maps the keys of data items uniformly, the querying process of service is inherently load-balanced for all the DAs. This feature also helps to avoid a quick energy exhaustion of certain DAs.

3.1.3. Unified Service Information Management

Our service discovery architecture employs a unified service information management scheme. It is necessary that all DAs, SAs, and UAs which participated in the architecture are aware of the scheme. In particular, there is a list of properties which is used for profiling a service. Each property has a number of values. We denote the list of properties and values by L and all nodes in the network have knowledge of this list. For example, a property called scope may indicate the application domain of a service, such as search engine, news archive, and anonymous FTP. We assume that there exists a predetermined list of properties and the corresponding values. The properties are denoted by set $\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{y}=\left\{\mathrm{p}{\mathrm{r}}_{\mathrm{1}},\mathrm{p}{\mathrm{r}}_{\mathrm{2}},\dots ,\mathrm{p}{\mathrm{r}}_{np}\right\}$ . The corresponding values of $\mathrm{p}{\mathrm{r}}_i$ are denoted by set $p_i=\left\{p{v}_{i\mathrm{1}},p{v}_{i\mathrm{2}},\dots ,p{v}_{im}\right\}$ . We suggest that one property consumes one byte. Then, there could be $m=\mathrm{256}$ different values for a property. Now, we introduce the definition of service description.

Definition 1.

By description of a service we mean the character string $\mathrm{d}\mathrm{e}\mathrm{s}\mathrm{p}=p{v}_{\mathrm{1}s},p{v}_{\mathrm{2}j},\dots ,p{v}_{\left(np-i\right)k}$ which is formed by concatenating the values of $np-i$ properties sequentially, where $\mathrm{0}⩽i<np$ and $\mathrm{1}⩽s,j,k⩽\mathrm{256}$ . When $i=\mathrm{0}$ , we call $\mathrm{d}\mathrm{e}\mathrm{s}\mathrm{p}$ a complete description. Otherwise, we call $\mathrm{d}\mathrm{e}\mathrm{s}\mathrm{p}$ an incomplete description.

Then, we know that there are totally ${\prod }_{i=\mathrm{1}}^{np}‍\left|p_i\right|$ different complete descriptions for profiling services. The format of service description is shown in Figure 1.

Figure 1

Service description.

3.2. Directory-Based Mode

In directory-based mode, all DAs in the MANET form a Chord network. All nodes in the MANET are mobile. SAs register their service information with DAs. A service query issued by a UA is handled by DAs.

3.2.1. Service Registration and Deregistration in WSN

For service registration, the service information submitted to a DA consists of three parts: description of the service, ID of the service provider (e.g., company name), and URL for accessing the service. Note that only a complete service description can be used for service registration. There are 32 bytes to accommodate the ID of service provider. Though the HTTP protocol does not stipulate the maximum length of a URL, we limit it to a maximum of 2048 bytes. The format of service registration is shown in Figure 2.

Figure 2

Service registration.

Since the WSN is based on Chord, we denote the identifier space of the Chord network by ${\mathrm{2}}^m$ . In order to accommodate the total ${\prod }_{i=\mathrm{1}}^{np}‍\left|p_i\right|$ different complete descriptions for profiling services, the inequality ${\mathrm{2}}^m⩾{\prod }_{i=\mathrm{1}}^{np}‍\left|p_i\right|$ should be satisfied.

In our model, we use the SHA-1 [43] as the consistent hash function to generate keys for both DAs and services. We denote the hash function by $sHash\left(string\right)$ . Upon receiving a valid service registration, a DA first sends a service registration acknowledgment to the SA which issued the service registration. Then, the DA extracts the description and the ID parts as a character string $str$ . The key of the service is obtained by $key=sHash\left(str\right)$ . The $〈key,\mathrm{U}\mathrm{R}\mathrm{L}〉$ pair is then sent to the DA which is responsible for the key. An SA could register its service information with an arbitrary DA within its radio range. As long as an SA receives a service registration acknowledgment, there is no need to register the service again. If the corresponding DA becomes out of the radio range when an SA is registering a series of services, the SA could contact another DA to register the remaining services. The service deregistration is conducted in a similar way to the service registration.

3.2.2. Key Generation and Searching in WSN

In unstructured P2P network, the searching based on a keyword is feasible. However, the consistent hashing of filename in structured DHT prohibits such operation in Chord. As a result, only the approach of exact match works. The inverted index proposed in [44] employs the mapping of $〈keyword,node〉$ . Then, the searching based on a keyword is implemented by redundancy storage. The major drawback of this approach is the problem of common keywords. The nodes which are responsible for common keywords suffer from heavy burden. In our model, a key is generated by hashing the character string of the description of a service concatenated by the service provider ID. The inclusion of the service provider ID resolves the above problem of common keywords.

When there is a potential need of certain service, several interested values are selected from the list L by a UA. Then, a service query with the same format as a service description is sent to a DA. Upon receiving a service query, a DA first checks whether there are missing values for properties. For a complete description, the DA which received the service query simply appends the IDs of service providers known to it and hashes the character string composed of the description and the ID. Then, the DA searches the obtained keys. However, it is very likely that values of some properties are missing due to uncertainty. Consequently, we have an incomplete description. For i missing values, each one is filled by several most popular values queried in the past. We denote the number of most popular values by $nmpv$ .

After the filling operation of the original incomplete description, we have $nmpv$ complete descriptions. Then, the IDs of service providers known to the DA are appended to the complete descriptions. We denote the number of service providers a DA is aware of by $nsp$ . For a scenario of $i=\mathrm{1}$ , $nmpv=\mathrm{3}$ , and $nsp=\mathrm{2}$ , the filling and appending process of an incomplete description is illustrated in Figure 3. Since there are six character strings of the descriptions concatenated by the service provider IDs, we could obtain six different keys for searching. The missing of property values is allowed, as it provides an open search result for a UA. However, since the keys are generated based on service information which is wishfully created by a UA and a DA, it is worth noting that both a complete description and an incomplete description are likely to yield no search results. For an existing service with a search key, the responsible DA will send a service reply to the original DA which issued the search. Then, the search result is fed back to the UA by the original DA.

Figure 3

Filling and appending.

3.2.3. Topology Control and Function Tuning for WSN

Since DAs are mobile in directory-based mode, the mobility has a strong impact on the topology of the WSN. Moreover, the unpredictable node failures also exert influence on the topology of the WSN. In our model, the topology control for WSN consists of two parts: local location optimization and global location optimization.

The local location optimization (LLO) is performed between a DA and the UAs which are communicating with the DA. For an individual DA, we divide its 360-degree radio range into six equal adjacent areas: $a_i\hspace{0.17em}\hspace{0.17em}\left(i=\mathrm{1,2},\dots ,\mathrm{6}\right)$ . As shown in Figure 4, the upward direction represents north.

Figure 4

Six areas.

The two salient features of the local location optimization are privacy preservation and energy conservation. As a long communication distance requires more energy for radio transmission, it is beneficial that the communication distance between a DA and a UA could be shortened once they get in touch with each other. In our model, the result of a service query is sent to a UA by the original DA it queried. This procedure makes the shortening of communication distance even more important. Since the mobile nodes are equipped with omni-directional antennas, a DA has no idea of where a UA is and therefore is unable to determine a correct moving direction. For the sake of privacy protection, a UA is unwilling to share its location in any form (e.g., GPS coordinates). To address this problem, we develop a direction-probing algorithm to determine a moving direction for a DA. As shown in Figure 5, this algorithm contains a four-step movement: $s_i\hspace{0.17em}\hspace{0.17em}\left(i=\mathrm{1,2},\dots ,\mathrm{4}\right)$ .

Figure 5

Four-step movement.

Considering a DA whose original location is $\left(x_{\mathrm{0}},y_{\mathrm{0}}\right)$ and a UA whose location is unknown, the DA performs the following movements consecutively: $s_{\mathrm{1}}\left(N,\Delta y\right)$ , $s_{\mathrm{2}}\left(E,\Delta x\right)$ , $s_{\mathrm{3}}\left(S,\Delta y\right)$ , and $s_{\mathrm{4}}\left(W,\Delta x\right)$ . The values of $\Delta x$ and $\Delta y$ are both positive. After a four-step movement, the DA returns to its original location $\left(x_{\mathrm{0}},y_{\mathrm{0}}\right)$ . During each step, the variation of signal intensity is recorded. We denote an increase and a decrease of signal intensity by + and −, respectively. Then, the moving direction of the DA is determined according to Table 1.

Table 1

Moving direction determination.

	N	W	S	E
$a_{\mathrm{1}}$	+	−	−	−
$a_{\mathrm{2}}$	+	−	−	+
$a_{\mathrm{3}}$	−	−	+	+
$a_{\mathrm{4}}$	−	−	+	−
$a_{\mathrm{5}}$	−	+	+	−
$a_{\mathrm{6}}$	+	+	−	−

When there are several UAs which are communicating with the DA, the desired moving directions related to different UAs might be various. Generally, it is considered that the energy consumption is in direct proportion to the communication distance. Hence, in order to reduce the total energy consumption, the sum of distances between the DA and each UA should be as small as possible. Considering two UAs $u{a}_{\mathrm{1}}$ and $u{a}_{\mathrm{2}}$ , the communication distances between the two UAs and the DA are denoted by $r_{\mathrm{1}}$ and $r_{\mathrm{2}}$ , respectively. In addition, we denote the signal intensities of the two UAs by $s_{\mathrm{1}}$ and $s_{\mathrm{2}}$ , respectively. We make the assumption that the signal intensity and the communication distance follow the inverse square law $s_i=\delta /r_i^{\mathrm{2}}$ , where δ is a constant coefficient and $i=\mathrm{1,2}$ . The condition of equality for $r_{\mathrm{1}}+r_{\mathrm{2}}=\mathrm{2}\sqrt{r_{\mathrm{1}}·r_{\mathrm{2}}}$ is $r_{\mathrm{1}}=r_{\mathrm{2}}$ . Moreover, $r_{\mathrm{1}}=r_{\mathrm{2}}$ is equivalent to $s_{\mathrm{1}}=s_{\mathrm{2}}$ . Similarly, for n UAs, we have the condition of equality for the inequality $r_{\mathrm{1}}+r_{\mathrm{2}}+\cdots +r_n⩾n\sqrt[n]{r_{\mathrm{1}}·r_{\mathrm{2}}·\cdots ·r_n}$ as $s_{\mathrm{1}}=s_{\mathrm{2}}=\cdots =s_n$ . Thus, the moving direction of the DA is adjusted based on the idea of equalizing the signal intensities of all UAs. However, when there are several UAs, this equalization process could be complicated. Alternatively, we choose to synthesize the n moving directions determined for the n UAs with weight values. The weight values of the UAs are calculated in reverse proportion to their signal intensities. The detailed direction-probing algorithm is illustrated in Algorithm 1. Once a final moving direction of the DA is obtained, the DA starts to move along the direction. When the n signal intensities become approximately equal to each other, the DA will stop moving. Each time a new UA gets in touch with the DA or an existing session is terminated, a new direction-probing procedure is initiated.

Algorithm 1: Direction-probing procedure.

Direction-Probing $\left(da,ua\left[n\right]\right)$

(1) original signal intensity $ua\left[j\right].s\left(\mathrm{0}\right)$

(2) for   $i\leftarrow \mathrm{1}$   to  4

(3)  for   $j\leftarrow \mathrm{1}$   to  n

(4)   if   $ua\left[j\right].s\left(i\right)>ua\left[j\right].s(i-\mathrm{1})$   then

(5)    signal variation $ua\left[j\right].v\left(i\right)\leftarrow$ “+”

(6)   else  signal variation $ua\left[j\right].v\left(i\right)\leftarrow$ “−”

(7)   end  if

(8)    $s\left[j\right]\left[i\right]\leftarrow ua\left[j\right].v\left(i\right)$

(9)  end for

(10) end for

(11) for   $j\leftarrow \mathrm{1}$   to  n

(12)  switch   $\left(s\left[j\right]\right)$

(13)   case  “ $+---$ ”: $ua\left[j\right].d=a_{\mathrm{1}}$   break

(14)   case  “ $+--+$ ”: $ua\left[j\right].d=a_{\mathrm{2}}$   break

(15)   case  “ $--++$ ”: $ua\left[j\right].d=a_{\mathrm{3}}$   break

(16)   case  “ $--+-$ ”: $ua\left[j\right].d=a_{\mathrm{4}}$   break

(17)   case  “ $-++-$ ”: $ua\left[j\right].d=a_{\mathrm{5}}$   break

(18)   case  “ $++--$ ”: $ua\left[j\right].d=a_{\mathrm{6}}$   break

(19)  end  switch

(20) end  for

(21)  ${ua}^{\prime }\left[n\right]=order\left(ascending,ua\left[n\right],ua\left[n\right].s\left(\mathrm{0}\right)\right)$

(22)  $s.sum\leftarrow \mathrm{0}$

(23) for   $j\leftarrow \mathrm{1}$   to  n

(24)   $s.sum\leftarrow s.sum+{ua}^{\prime }\left[j\right].s\left(\mathrm{0}\right)$

(25) end for

(26) for   $j\leftarrow \mathrm{1}$   to  n

(27)   ${ua}^{\prime }\left[j\right].w=s.sum/{ua}^{\prime }\left[j\right].s\left(\mathrm{0}\right)$

(28) end for

(29)  $da.d=synthesis\left({ua}^{\prime }\left[j\right].d,{ua}^{\prime }\left[j\right].w\right)$

The global location optimization (GLO) is performed between DAs and it is based on the direction-probing algorithm described in the local location optimization. Other than local location optimization, the global location optimization concentrates on topology maintenance.

As a DA in the WSN has a maximum transmission range, in order to keep the connectivity of the WSN, the relative positions among the DAs should be carefully controlled. The global connectivity of the WSN could be decomposed into several groups of connectivity. In particular, we develop a connectivity maintenance algorithm to maintain the local connectivity of three DAs. Considering an individual DA which is denoted by $da$ , by the Chord protocol, $da$ has a predecessor and a successor. We denote the two DAs by $da.predecessor$ and $da.successor$ , respectively. The signal intensity between $da$ and $da.predecessor$ is denoted by $da.predecessor.s$ . The signal intensity between $da$ and $da.successor$ is denoted by $da.successor.s$ . When $da.predecessor.s$ or $da.successor.s$ keeps decreasing, $da$ becomes aware of the fact that its predecessor/successor is moving away from it. Once $da.predecessor.s$ or $da.successor.s$ is lower than a threshold $s_{\mathrm{l}\mathrm{o}\mathrm{w}}$ , $da$ initiates a direction-probing procedure to determine the direction of the predecessor/successor. Meanwhile, it sends a SLOW_DOWN message to the predecessor/successor for notification. Once a moving direction is determined, $da$ starts to move toward the predecessor/successor in order to prevent the signal intensity from getting too low. In addition, the predecessor/successor which receives the SLOW_DOWN message will adjust its movement for the purpose of getting close to $da$ . Once the signal intensity between $da$ and the predecessor/successor reaches a certain level, the predecessor/successor stops getting close to $da$ . We denote the signal intensity of this level by $s_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{l}}$ . Note that when both $da.predecessor.s$ and $da.successor.s$ are greater than or equal to $s_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{l}}$ , the $da$ stops moving. For both $da.predecessor$ and $da.successor$ , a compromise of directions might be needed. In this case, a composite moving direction is used by $da$ . The detailed connectivity maintenance algorithm is illustrated in Algorithm 2. Since the energy of a DA is limited, we hold that the function of connectivity maintenance stops when the remaining energy of a DA is critically low, and this feature is indicated by the last statement of Algorithm 2. A complete function tuning algorithm is described later.

Algorithm 2: Connectivity maintenance procedure.

$ConnectivityMaintenance\left(da,da.predecessor,da.successor\right)$

(1) repeat

(2)   $FLA{G}_{\mathrm{1}}\leftarrow false$

(3)   $FLA{G}_{\mathrm{2}}\leftarrow false$

(4)  if   $da.predecessor.s<s_{\text{low}}$   then

(5)    $FLA{G}_{\mathrm{1}}\leftarrow true$

(6)    $da.send\left(\text{SLOW\_DOWN},da.predecessor\right)$

(7)    $da.d_{\mathrm{1}}=da.direction\text{-}probing\left(da,da.predecessor\right)$

(8)   if   $da.predecessor$   received  SLOW_DOWN  then

(9)     $da.predecessor.d=da.predecessor.direction\text{-}probing\left(da.predecessor,da\right)$

(10)     $da.predecessor.move\left(da.predecessor.d\right)$

(11)  end  if

(12) end  if

(13) if   $da.successor.s<s_{\text{low}}$   then

(14)   $FLA{G}_{\mathrm{2}}\leftarrow true$

(15)   $da.send\left(\text{SLOW\_DOWN},da.successor\right)$

(16)   $da.d_{\mathrm{2}}=da.direction\text{-}probing\left(da,da.successor\right)$

(17)  if   $da.successor$   received  SLOW_DOWN  then

(18)    $da.successor.d=da.successor.direction\text{-}probing\left(da.successor,da\right)$

(19)    $da.successor.move\left(da.successor.d\right)$

(20)  end  if

(21) end  if

(22) if   $FLA{G}_{\mathrm{1}}\hspace{0.17em}\&\&\hspace{0.17em}FLA{G}_{\mathrm{2}}==true$   then

(23)   $da.predecessor.w=\left(da.predecessor.s+da.successor.s\right)/da.predecessor.s$

(24)   $da.successor.w=\left(da.predecessor.s+da.successor.s\right)/da.successor.s$

(25)   $da.d=synthesis\left(da.d_{\mathrm{1}},da.d_{\mathrm{2}},da.predecessor.w,da.successor.w\right)$

(26) else  if   $FLA{G}_{\mathrm{1}}==true$   then

(27)     $da.d=da.d_{\mathrm{1}}$

(28)    else  if   $FLA{G}_{\mathrm{2}}==true$   then

(29)       $da.d=da.d_{\mathrm{2}}$

(30)    end  if

(31) end  if

(32) end  if

(33)  $da.move\left(da.d\right)$

(34) if   $da.predecessor.s⩾s_{\text{normal}}$   then

(35)   $da.predecessor.stop\left(da.predecessor.d\right)$

(36) end  if

(37) if   $da.successor.s⩾s_{\text{normal}}$   then

(38)   $da.successor.stop\left(da.successor.d\right)$

(39) end if

(40) if   $\left(da.predecessor.s⩾s_{\text{normal}}\right)\&\&\left(da.successor.s⩾s_{\text{normal}}\right)$   then

(41)   $da.stop\left(da.d\right)$

(42) end  if

(43) until   $E\left(da\right)⩽e_{\gamma }$

As energy conservation is a critical issue in WSN for DAs and network life, we develop a function tuning algorithm based on the remaining energy of a DA. Moreover, this algorithm also assists the topology maintenance. We denote the remaining energy of $da$ by $E\left(da\right)$ . In specific, the remaining energy of a DA is classified into four statuses according to three critical values: $e_{\alpha }$ , $e_{\beta }$ , and $e_{\gamma }$ . The four energy statuses $S_n$ , $S_l$ , $S_a$ , and $S_s$ are detailed in Table 2.

Table 2

Energy statuses and descriptions.

Status	Description
$S_n$	Normal status. The remaining energy is $E(da)>e_{\alpha }$
$S_l$	Low status. The remaining energy is $e_{\beta }<E(da)⩽e_{\alpha }$
$S_a$	Alert status. The remaining energy is $e_{\gamma }<E(da)⩽e_{\beta }$
$S_s$	Serious status. The remaining energy is $E(da)⩽e_{\gamma }$

When $da$ is in the normal status, it is fully functional. Namely, it accepts service registrations, handles service queries, sends service replies, performs local location optimization and global location optimization, and so forth. Once $da$ enters the low status, it stops performing local location optimization. When it turns into the alert status, an ALERT message is sent to both $da.predecessor$ and $da.successor$ . As soon as $da.predecessor$ and $da.successor$ receive the ALERT message, they both stop the local location optimization temporarily (even when they are in the normal status). Now, the three DAs $da$ , $da.predecessor$ , and $da.successor$ are in preparation for the future serious status of $da$ . Once $da$ enters the serious status, it disables all functions except for performing a data transfer. By the Chord protocol, a node which is about to leave the network should transfer all the $〈key,dataitem〉$ pairs it is responsible for to its successor. When the transfer completes, the leaving node notifies its predecessor to change successor to the successor of the leaving node. Similarly, the successor of the leaving node is notified to change predecessor to the predecessor of the leaving node. Finally, the leaving node is completely isolated from the Chord network, the successor of its former predecessor is now its former successor, and the predecessor of its former successor is now its former predecessor. Then, the former predecessor of $da$ sets the availability of $da$ to LOGOUT in a monitoring token; the information about the monitoring token is provided later in Section 3.4.

As described above, when the status of a DA changes from normal to low, there is only one function that is removed, namely, the local location optimization. All the remaining functions of a DA are operational in three statuses: normal, low, and alert. The function of global location optimization is removed when the status of a DA changes to serious. Hence, this function tuning algorithm significantly assists the connectivity maintenance. The detailed function tuning algorithm is illustrated in Algorithm 3.

Algorithm 3: Function tuning procedure.

  $FunctionTuning\left(da,e_{\alpha },e_{\beta },e_{\gamma }\right)$

(1)  if   $E\left(da\right)>e_{\alpha }$  then  $S=S_n$

(2)  else  if   $e_{\beta }<E\left(da\right)⩽e_{\alpha }$   then   $S=S_l$

(3)  else  if   $e_{\gamma }<E\left(da\right)⩽e_{\beta }$   then   $S=S_a$

(4)  else   $E\left(da\right)⩽e_{\gamma }$   then   $S=S_s$

(5)  end  if

(6)  switch   $\left(S\right)$

(7)   case   $S_n$  : break

(8)   case   $S_l:da.function\leftarrow da.function$ ∖ $\left\{\text{LLO}\right\}$

(9)    break

(10)  case   $S_a:da.send\left(\text{ALERT},da.predecessor\right)$

(11)    $da.send\left(\text{ALERT},da.successor\right)$

(12)   break

(13)  case   $S_s:da.function\leftarrow \mathrm{\varnothing }$

(14)    $da.transfer\left(〈key,\text{URL}〉,da.successor\right)$

(15)    $da.send\left(\text{CHANGE\_SUCCESSOR}\left(da.successor\right),da.predecessor\right)$

(16)    $da.send\left(\text{CHANGE\_PREDECESSOR}\left(da.predecessor\right),da.successor\right)$

(17)   break

(18) end  switch

3.3. Directory-Less Mode

In directory-less mode, all DAs in the MANET are stationary. However, they still keep forming a Chord network. Other nodes in the MANET are mobile, namely, UAs and SAs. Though the WSN based on the Chord protocol still exists, there are no topology control and key searching based on the Chord network. Thus, the directory-less mode is much simpler than the directory-based mode. For DAs and SAs, the service registration is operational as before. This is done to get prepared for a mode switch. The mode switch between the directory-based mode and directory-less mode is detailed later in Section 3.4. In classic directory-less architectures, there are only UAs and SAs. Hence, there is no so called relaying function associated with DAs. The service discovery is only conducted based on service queries issued by UAs and service advertisements issued by SAs. In our model, the DAs provide relaying function for service queries, service advertisements, and service replies. Moreover, since DAs possess a large amount of service information, a DA could issue a service reply to answer a service query based on the service information it has (service information it originally knows and service information it learns through the relaying). For the purpose of mitigating the flooding problem and improving the performance of service discovery, we develop a two-hop zone scheme for the directory-less mode.

3.3.1. Two-Hop Zone Scheme

For a node $n_i$ in the MANET network, the two-hop zone of $n_i$ consists of two parts: one-hop neighbors and two-hop neighbors. A one-hop neighbor $n_o$ of node $n_i$ is a node which is one hop away from node $n_i$ . Though there might be several paths between $n_i$ and $n_o$ , the shortest path between them is one hop. The sufficient and necessary condition for a node $n_o$ to be a one-hop neighbor of node $n_i$ is that they are able to directly communicate with each other. The degree of node $n_i$ , namely, the number of one-hop neighbors of $n_i$ , is denoted by $d_{\left(i,\mathrm{1}\right)}$ . Then, we denote the set of one-hop neighbors of $n_i$ by

$$\begin{array}{cc}& N_{\left(i,\mathrm{1}\right)}=\left\{n_{i\mathrm{1}},n_{i\mathrm{2}},\dots ,n_{i{d}_{\left(i,\mathrm{1}\right)}}\right\}.\end{array}$$

(1)

Similarly, a two-hop neighbor $n_t$ of node $n_i$ is a node which is two hops away from node $n_i$ . Though there might be several paths between $n_i$ and $n_t$ , the shortest path between them is two hops. The sufficient and necessary condition for a node $n_t$ to be a two-hop neighbor of node $n_i$ is that they are not able to directly communicate with each other and node $n_t$ is a one-hop neighbor of node $n_i$ 's one-hop neighbor(s). The number of two-hop neighbors of $n_i$ is denoted by $d_{\left(i,\mathrm{2}\right)}$ . The set of two-hop neighbors of $n_i$ is

$$\begin{array}{cc}& N_{\left(i,\mathrm{2}\right)}=N_{\left(i\mathrm{1,1}\right)}\cup N_{\left(i\mathrm{2,1}\right)}\cup \cdots \cup N_{\left(i{d}_{\left(i,\mathrm{1}\right)},\mathrm{1}\right)}\mathrm{\setminus }{N}_{\left(i,\mathrm{1}\right)}.\end{array}$$

(2)

By the definition of a two-hop neighbor, the number of two-hop neighbors of node $n_i$ can be calculated as

$$\begin{array}{cc}& d_{\left(i,\mathrm{2}\right)}=\left|{\displaystyle \bigcup }_{n_{ij}\in N_{\left(i,\mathrm{1}\right)}}‍N_{\left(ij,\mathrm{1}\right)}\mathrm{\setminus }{N}_{\left(i,\mathrm{1}\right)}\right|-\mathrm{1}.\end{array}$$

(3)

Note that node $n_i$ is a one-hop neighbor of its one-hop neighbor(s); namely,

$$\begin{array}{cc}& n_i\in {\displaystyle \bigcup }_{n_{ij}\in N_{\left(i,\mathrm{1}\right)}}‍N_{\left(ij,\mathrm{1}\right)}\mathrm{\setminus }{N}_{\left(i,\mathrm{1}\right)}.\end{array}$$

(4)

Thus, node $n_i$ should be excluded from the calculation of $d_{(i,\mathrm{2})}$ .

For an individual node $n_i$ in the MANET network, we denote the frequency of service advertisement of $n_i$ by $d{f}_i$ . A service advertisement contains a set of service records. We denote the set of service records contained in a service advertisement by $D\left(n_i\right)$ , where $\left|D\left(n_i\right)\right|⩾\mathrm{1}$ . During a certain measurement period, the average number of service records sent by node $n_i$ is $\overline{d_i}$ per advertisement. Then, we have $\overline{d_i}⩾\mathrm{1}$ . In order to facilitate the presentation of our two-hop zone scheme, we make the following premise.

Premise  1. Let $\left[t_a,t_b\right]$ be a measurement period, where $t_a<t_b$ . We assume that the period is sufficiently long to observe the behaviors of node $n_i$ together with its one-hop neighbors and two-hop neighbors. Moreover, the behavior characteristics of every node considered remain unchanged, such as the frequency of service advertisement, the frequency of service query, and the average number of service records per advertisement.

Node $n_i$ receives the service advertisements from all its one-hop neighbors. An update of its local database is carried out according to the service information contained in the received service advertisements. Since the frequencies of service advertisement vary from node to node, the service advertisements from the one-hop neighbors of node $n_i$ are arrived asynchronously. Moreover, the frequency of service advertisement of a particular node may change from time to time. Hence, the service advertisements from the one-hop neighbors of node $n_i$ are arrived randomly. For simplicity, we assume that the frequencies of service advertisement of all nodes in the network remain constant during the measurement period $\left[t_a,t_b\right]$ . In essence, this assumption is given by Premise  1.

We denote the total number of service records contained in the service advertisements received by node $n_i$ by $s{d}_{(i,r)}$ , and it is computed as

$$\begin{array}{cc}& s{d}_{\left(i,r\right)}={\displaystyle \sum }_{n_{ij}\in N_{\left(i,\mathrm{1}\right)}}‍{\bar{d}}_{\left(ij\right)}·⌊d{f}_{\left(ij\right)}·\left(t_b-t_a\right)⌋.\end{array}$$

(5)

For each one-hop neighbor of $n_i$ , the number of service records advertised by $n_{ij}$ is calculated by multiplying the average number of service records per advertisement by the times of service advertisement during the measurement period $\left[t_a,t_b\right]$ . Premise  1 guarantees that each one-hop neighbor of $n_i$ performs the service advertisement at least once during the measurement period $\left[t_a,t_b\right]$ . Thus, the result of $d{f}_{(ij)}·\left(t_b-t_a\right)$ is greater than or equal to 1. For a noninteger number of the times of service advertisement, the floor operation rounds the result to the biggest integer which is less than $d{f}_{(ij)}·\left(t_b-t_a\right)$ .

If node $n_i$ is a UA or DA, it forwards the received service advertisements to all its one-hop neighbors. When node $n_i$ is an SA, besides forwarding the received service advertisements, it also issues service advertisements. We denote the total number of service records sent by node $n_i$ by $s{d}_{(i,s)}$ , and it consists of two parts:

$$\begin{array}{cc}& s{d}_{\left(i,s\right)}=s{d}_{\left(i\right)}+s{d}_{\left(i,f\right)}.\end{array}$$

(6)

Node $n_i$ issues its own service advertisements to all its one-hop neighbors at the frequency of $d{f}_i$ . The total number of service records issued by node $n_i$ is denoted by $s{d}_{(i)}$ , which is computed as

$$\begin{array}{cc}& s{d}_{\left(i\right)}=\overline{d_i}·⌊d{f}_i·\left(t_b-t_a\right)⌋.\end{array}$$

(7)

$s{d}_{(i)}$ is calculated by multiplying the average number of service records per advertisement by the times of service advertisement during the measurement period $\left[t_a,t_b\right]$ . Premise  1 guarantees that node $n_i$ performs the service advertisement at least once during the measurement period $\left[t_a,t_b\right]$ . Hence, the result of $d{f}_i·\left(t_b-t_a\right)$ is greater than or equal to 1. For a noninteger number of the times of service advertisement, the floor operation rounds the result to the biggest integer which is less than $d{f}_i·\left(t_b-t_a\right)$ .

Node $n_i$ forwards the service advertisements received from other nodes. The total number of service records forwarded by node $n_i$ is denoted by $s{d}_{(i,f)}$ . Among the service advertisements received by $n_i$ , whose TTL values are greater than 0 should be forwarded by node $n_i$ . As the two-hop zone scheme we proposed stipulates that the initial TTL value of a service advertisement is 2, the TTL value of each service advertisement received by node $n_i$ is either 1 or 0. Thus, the coverage of the original service advertisement issued by node $n_i$ is its one-hop and two-hop neighbors. In other words, the propagation range of an original service advertisement is limited within the two-hop zone of the issuing node. This characteristic could mitigate the flooding problem and reduce the message overhead imposed on the whole network.

Suppose the TTL value of the received service advertisements is under Poisson distribution

$$\begin{array}{cc}& P\left\{\mathrm{T}\mathrm{T}\mathrm{L}=k\right\}=\frac{{\lambda }_d^k·e^{-{\lambda }_d}}{k!},\hspace{1em}{\lambda }_d>\mathrm{0},\hspace{0.17em}\hspace{0.17em}k=\mathrm{0,1}.\end{array}$$

(8)

In our two-hop zone scheme, node $n_i$ is supposed to forward the received service advertisements to all its one-hop neighbors. However, it is necessary that the service advertisements sent to $n_i$ by its own one-hop neighbor $n_{ij}$ should not be forwarded back to $n_{ij}$ by $n_i$ . Though the corresponding one-hop neighbor might vary from one service advertisement to another, we denote it by a node $n_{iy}$ universally. Then, the total number of service advertisements forwarded by node $n_i$ is computed as

$$\begin{array}{cc}& {\lambda }_d·e^{-{\lambda }_d}·{\displaystyle \sum }_{n_{ij}\in N_{\left(i,\mathrm{1}\right)}}‍\left(⌊d{f}_{\left(ij\right)}·\left(t_b-t_a\right)⌋·\left(d_{\left(i,\mathrm{1}\right)}-\mathrm{1}\right)\right).\end{array}$$

(9)

The universal node $n_{iy}$ is excluded by the minus one operation. Note that (9) is the number of service advertisements rather than the number of service records. As mentioned above, the number of service records contained in a valid service advertisement is greater than or equal to one. The total number of service records forward by node $n_i$ is computed as

$$\begin{array}{ll}s{d}_{\left(i,f\right)}& ={\lambda }_d·e^{-{\lambda }_d}\\ & \hspace{1em}·{\displaystyle \sum }_{n_{ij}\in N_{\left(i,\mathrm{1}\right)}}‍\left({\bar{d}}_{\left(ij\right)}·⌊d{f}_{\left(ij\right)}·\left(t_b-t_a\right)⌋·\left(d_{\left(i,\mathrm{1}\right)}-\mathrm{1}\right)\right).\end{array}$$

(10)

Combining (5) and (10) we have the total number of service records forwarded by node $n_i$ as

$$\begin{array}{cc}& s{d}_{\left(i,f\right)}={\lambda }_d·e^{-{\lambda }_d}·\left(d_{\left(i,\mathrm{1}\right)}-\mathrm{1}\right)·s{d}_{\left(i,r\right)}.\end{array}$$

(11)

Then, (6) could be rewritten as

$$\begin{array}{ll}s{d}_{\left(i,s\right)}& =\overline{d_i}·⌊d{f}_i·\left(t_b-t_a\right)⌋\\ & \hspace{1em}+{\lambda }_d·e^{-{\lambda }_d}·\left(d_{\left(i,\mathrm{1}\right)}-\mathrm{1}\right)·s{d}_{\left(i,r\right)}.\end{array}$$

(12)

That is to say, each one-hop neighbor of node $n_i$ receives $s{d}_{(i,s)}$ service records from $n_i$ .

When node $n_i$ receives a service query, it checks its local database. If the service query could be answered locally, there is no need to send it out. Otherwise, node $n_i$ sends it to its one-hop neighbors. Every one-hop neighbor of $n_i$ will receive a duplicate of the service query. While a service query is traveling through the network, the intermediate nodes will be recorded successively in a travel path. This path information stored in the service query plays an important role for the transmission of a service reply.

We denote the total number of service queries sent by node $n_i$ by $s{s}_{(i,s)}$ , and it consists of two parts:

$$\begin{array}{cc}& s{s}_{\left(i,s\right)}=s{s}_{\left(i\right)}+s{s}_{\left(i,f\right)}.\end{array}$$

(13)

Suppose node $n_i$ issues its own service queries to all its one-hop neighbors at the frequency of $s{f}_i$ . If the average number of service requests contained in the service queries issued by node $n_i$ is $\overline{s_i}$ per service query, the total number of service requests issued by $n_i$ is denoted by $s{s}_{(i)}$ , which is computed as

$$\begin{array}{cc}& s{s}_{\left(i\right)}=\overline{s_i}·⌊s{f}_i·\left(t_b-t_a\right)⌋.\end{array}$$

(14)

In our two-hop scheme, we stipulate that a service query contains exactly one service request. Hence, $\overline{s_i}$ is identically equal to 1. In the reminder of this paper, we use a service request and a service query interchangeably.

For the service queries received from other nodes, node $n_i$ checks its local database to determine whether a service query could be answered locally. If a service query could be answered locally, node $n_i$ will issue a service reply designated to the node which originally issued the service query. The service queries which cannot be answered by node $n_i$ are disposed according to their TTL values. If the TTL value of a service query is 0, it will be dropped by node $n_i$ , without any forwarding. The service queries whose TTL values are greater than 0 will be forwarded by node $n_i$ . Our two-hop scheme stipulates that the initial TTL value of a service query is 4. Thus, the TTL values of the service queries received by node $n_i$ are within the set $\left\{\mathrm{3,2},\mathrm{1,0}\right\}$ . Meanwhile, the coverage of an original service query issued by node $n_i$ is two two-hop zones. In another word, an original service query is restricted within two two-hop zones of the issuing node. The same as the service advertisement, an upper bound of the initial TTL of a service query is to alleviate the flooding problem and weaken the message overhead imposed on the whole network.

Suppose the TTL value of the received service queries is under Poisson distribution

$$\begin{array}{cc}& P\left\{\mathrm{T}\mathrm{T}\mathrm{L}=k\right\}=\frac{{\lambda }_s^k{e}^{-{\lambda }_s}}{k!},\hspace{1em}{\lambda }_s>\mathrm{0},\hspace{0.17em}\hspace{0.17em}k=\mathrm{0,1},\mathrm{2,3}.\end{array}$$

(15)

We consider all the service queries sent to node $n_i$ are directly from its one-hop neighbors. We denote the total number of service queries received by node $n_i$ by $s{s}_{(i,r)}$ ; it could be calculated as

$$\begin{array}{cc}& s{s}_{\left(i,r\right)}={\displaystyle \sum }_{n_{\left(ij\right)}\in N_{\left(i,\mathrm{1}\right)}}‍{\bar{s}}_{\left(ij\right)}·⌊s{f}_{\left(ij\right)}·\left(t_b-t_a\right)⌋.\end{array}$$

(16)

Suppose that node $n_i$ could be able to answer $a_i$ percent of the service queries sent to it. The same as the service advertisement, a service query sent to $n_i$ by its one-hop neighbor $n_{ij}$ should not be forwarded back to $n_{ij}$ by $n_i$ . Then, the number of service queries that should be forwarded by node $n_i$ is obtained analogously:

$$\begin{array}{ll}s{s}_{\left(i,f\right)}& =\left(\frac{{\lambda }_s{e}^{-{\lambda }_s}}{\mathrm{1}!}+\frac{{\lambda }_s^{\mathrm{2}}{e}^{-{\lambda }_s}}{\mathrm{2}!}+\frac{{\lambda }_s^{\mathrm{3}}{e}^{-{\lambda }_s}}{\mathrm{3}!}\right)\\ & \hspace{1em}·\left(d_{\left(i,\mathrm{1}\right)}-\mathrm{1}\right)·\left(\mathrm{1}-a_i\right)·s{s}_{\left(i,r\right)}.\end{array}$$

(17)

Then, (13) could be rewritten as

$$\begin{array}{ll}s{s}_{\left(i,s\right)}& =⌊s{f}_i·\left(t_b-t_a\right)⌋+\left(\frac{{\lambda }_s{e}^{-{\lambda }_s}}{\mathrm{1}!}+\frac{{\lambda }_s^{\mathrm{2}}{e}^{-{\lambda }_s}}{\mathrm{2}!}+\frac{{\lambda }_s^{\mathrm{3}}{e}^{-{\lambda }_s}}{\mathrm{3}!}\right)\\ & \hspace{1em}·\left(d_{\left(i,\mathrm{1}\right)}-\mathrm{1}\right)·\left(\mathrm{1}-a_i\right)·s{s}_{\left(i,r\right)}.\end{array}$$

(18)

Compared with service advertisement and service query, the number of service replies is small in nature. In general, the occurrence of a service reply is unpredictable and irregular. It is actually meaningless to impose restrictions on the sending frequency of a service reply. Moreover, in order to improve the performance of service discovery, we do not assign a specific upper bound to the initial TTL value of a service reply. A service reply uses the path information contained in the corresponding service query. The service replies designated to node $n_i$ are corresponding to the service queries issued by $n_i$ .

We denote the total number of service replies sent by node $n_i$ by $s{r}_{(i,s)}$ ; it consists of two parts:

$$\begin{array}{cc}& s{r}_{\left(i,s\right)}=s{r}_{\left(i\right)}+s{r}_{\left(i,f\right)}.\end{array}$$

(19)

$s{r}_{(i)}$ denotes the number of service replies corresponding to the service queries which are answered by node $n_i$ itself. As mentioned above, node $n_i$ could be able to answer $a_i$ percent of the service queries sent to it. Hence, $s{r}_{(i)}$ could be computed as

$$\begin{array}{cc}& s{r}_{\left(i\right)}=a_i·s{s}_{\left(i,r\right)}.\end{array}$$

(20)

Besides sending its own service replies, node $n_i$ also forwards the service replies designated to other nodes. Among the service replies received by node $n_i$ , those designated to node $n_i$ will not be forwarded by $n_i$ . For a service reply designated to another node, node $n_i$ will try to forward it to the next node according the path information contained in the service reply. If the particular next node is not available, the service reply will be dropped by node $n_i$ . Now, we denote the total number of service replies received by node $n_i$ by $s{r}_{(i,r)}$ . Suppose that $b_i$ percent of the service replies received by node $n_i$ are designated to it. Among the service replies which should be forwarded by node $n_i$ , we assume that $f_i$ percent of them cannot be delivered to the next node, for the next node might be failed or out of the radio range of node $n_i$ . Then, the total number of service replies forwarded by node $n_i$ could be calculated as

$$\begin{array}{cc}& s{r}_{\left(i,f\right)}=\left(\mathrm{1}-b_i\right)·\left(\mathrm{1}-f_i\right)·s{r}_{\left(i,r\right)}.\end{array}$$

(21)

Combining (19), (20), and (21), the total number of service replies sent by node $n_i$ could be rewritten as

$$\begin{array}{cc}& s{r}_{\left(i,s\right)}=a_i·s{s}_{\left(i,r\right)}+\left(\mathrm{1}-b_i\right)·\left(\mathrm{1}-f_i\right)·s{r}_{\left(i,r\right)}.\end{array}$$

(22)

3.3.2. Level of Connectivity

In order to facilitate a further investigation of the two-hop zone scheme, we propose a novel method to calculate the level of connectivity for the whole network based on the two-hop zone scheme. In the first place, we formulate the level of connectivity of two arbitrary nodes under the two-hop zone scheme. For two arbitrary nodes $n_i$ and $n_j$ , the relationship between them is denoted by $f_k\left(n_i,n_j\right)$ , where k indicates the number of hops in the shortest path between $n_i$ and $n_j$ . As depicted in Figure 6, the shortest path between two arbitrary nodes $n_i$ and $n_j$ can be divided into five cases. The intermediate nodes are denoted by $n_{mi}$ .

Figure 6

Node relationships under the two-hop zone scheme.

In Figure 6(a), node $n_i$ and node $n_j$ are able to directly communicate with each other. The number of hops between them is 1. In this case, we have

$$\begin{array}{cc}& f_{\mathrm{1}}\left(n_i,n_j\right)~\left(n_i\in N_{\left(j,\mathrm{1}\right)}\right),\left(n_j\in N_{\left(i,\mathrm{1}\right)}\right).\end{array}$$

(23)

In Figure 6(b), the number of hops between node $n_i$ and node $\mathrm{n}\mathrm{o}\mathrm{d}{\mathrm{e}}_j$ is 2. They share the same one-hop neighbor $n_{m\mathrm{1}}$ . Node $\mathrm{n}\mathrm{o}\mathrm{d}{\mathrm{e}}_j$ is within the two-hop zone of node $n_i$ . In this case, we have

$$\begin{array}{ll}{f}_{\mathrm{2}}\left(n_i,n_j\right)& ~\left(n_i\in N_{\left(j,\mathrm{2}\right)}\right),\left(n_j\in N_{\left(i,\mathrm{2}\right)}\right),\\ & \left(n_{m\mathrm{1}}\in N_{\left(i,\mathrm{1}\right)}\cap N_{\left(j,\mathrm{1}\right)}\right).\end{array}$$

(24)

In Figure 6(c), the number of hops between node $n_i$ and node $n_j$ is 3. Node $n_i$ has a one-hop neighbor node $n_{m\mathrm{1}}$ and a two-hop neighbor node $n_{m\mathrm{2}}$ . Since node $n_{m\mathrm{2}}$ is a one-hop neighbor of node $n_j$ , $n_j$ is within the two-hop zone of node $n_{m\mathrm{2}}$ . In this case, we have

$$\begin{array}{ll}{f}_{\mathrm{3}}\left(n_i,n_j\right)& ~\left(n_{m\mathrm{1}}\in N_{\left(i,\mathrm{1}\right)}\right),\left(n_{m\mathrm{2}}\in N_{\left(i,\mathrm{2}\right)}\right),\\ & \left(n_{m\mathrm{1}}\in N_{\left(j,\mathrm{2}\right)}\right),\left(n_{m\mathrm{2}}\in N_{\left(j,\mathrm{1}\right)}\right).\end{array}$$

(25)

In Figure 6(d), the number of hops between node $n_i$ and node $n_j$ is 4. Node $n_i$ has a one-hop neighbor node $n_{m\mathrm{1}}$ and a two-hop neighbor node $n_{m\mathrm{2}}$ . Since node $n_{m\mathrm{2}}$ is a two-hop neighbor of node $n_j$ , node $n_j$ is within the two-hop zone of node $n_{m\mathrm{2}}$ . Node $n_i$ and node $n_j$ share the same two-hop neighbor node $n_{m\mathrm{2}}$ . In this case, we have

$$\begin{array}{ll}{f}_{\mathrm{4}}\left(n_i,n_j\right)& ~\left(n_{m\mathrm{1}}\in N_{\left(i,\mathrm{1}\right)}\right),\left(n_{m\mathrm{2}}\in N_{\left(i,\mathrm{2}\right)}\cap N_{\left(j,\mathrm{2}\right)}\right),\\ & \left(n_{m\mathrm{3}}\in N_{\left(j,\mathrm{1}\right)}\right),\left(n_{m\mathrm{2}}\in N_{\left(m\mathrm{1,1}\right)}\cap N_{\left(m\mathrm{3,1}\right)}\right).\end{array}$$

(26)

In Figure 6(e), the number of hops between node $n_i$ and node $n_j$ is greater that 4. Node $n_i$ has a one-hop neighbor node $n_{m\mathrm{1}}$ and a two-hop neighbor node $n_{m\mathrm{2}}$ . Node $n_j$ has a one-hop neighbor node $n_{m\mathrm{4}}$ and a two-hop neighbor node $n_{m\mathrm{3}}$ . The dotted line ellipse indicates that nodes $n_{m\mathrm{2}}$ and $n_{m\mathrm{3}}$ are connected as the same with node $n_i$ and node $n_j$ in the previous four cases, namely, $f_{\mathrm{1}}$ , $f_{\mathrm{2}}$ , $f_{\mathrm{3}}$ , and $f_{\mathrm{4}}$ . In this case, the relationship between $n_i$ and $n_j$ is expressed recursively by

$$\begin{array}{ll}{f}_{>\mathrm{4}}\left(n_i,n_j\right)& ~\left(n_{m\mathrm{1}}\in N_{\left(i,\mathrm{1}\right)}\right),\left(n_{m\mathrm{2}}\in N_{\left(i,\mathrm{2}\right)}\right),\left(n_{m\mathrm{3}}\in N_{\left(j,\mathrm{2}\right)}\right),\\ & \left(n_{m\mathrm{4}}\in N_{\left(j,\mathrm{1}\right)}\right),f_{k-\mathrm{4}}\left(n_{m\mathrm{2}},n_{m\mathrm{3}}\right),\end{array}$$

(27)

where $f_{k-\mathrm{4}}\left(n_{m\mathrm{2}},n_{m\mathrm{3}}\right)$ indicates the relationship between $n_{m\mathrm{2}}$ and $n_{m\mathrm{3}}$ .

More complex situations can be decomposed and modeled through the iteration of different cases illustrated in Figure 6.

The level of connectivity between node $n_i$ and node $n_j$ is denoted by $d\left(n_i,n_i\right)$ . It is defined as

$$\begin{array}{cc}& d\left(n_i,n_j\right)=\left\{\begin{array}{cc}\mathrm{0},\hfill & k=\mathrm{0}\hfill \\ \frac{\mathrm{1}}{k},\hfill & k=\mathrm{1,2},\mathrm{3,4}\hfill \\ \frac{\mathrm{1}}{\mathrm{4}+\mathrm{1}/d\left(n_i^{\prime \prime },n_j^{\prime \prime }\right)}\hfill & k>\mathrm{4}.\hfill \end{array}\right.\end{array}$$

(28)

For $k=\mathrm{0}$ , there is no path between $n_i$ and $n_j$ ; then we define $d\left(n_i,n_j\right)=\mathrm{0}$ . When $k⩾\mathrm{0}$ , the level of connectivity between two nodes monotonically decreases with the increase of the number of hops between them. For $k=\mathrm{1,2},\mathrm{3}$ , and 4, the reciprocal of k is used as the value of $d\left(n_i,n_j\right)$ . For $k>\mathrm{4}$ , the calculation of $d\left(n_i,n_j\right)$ cannot be done within the two-hop zones of $n_i$ and $n_j$ . The value of $d\left(n_i,n_j\right)$ is determined recursively. Trivially, a two-hop zone of a node covers two hops. Thus, each time k is beyond a multiple of 4, another calculation of the level of connectivity is required. Then, the number of recursions could be calculated as $R=⌊(k-\mathrm{1})/\mathrm{4}⌋$ .

In the case of $k>\mathrm{4}$ , node $n_i^{\prime \prime }$ is the particular two-hop neighbor of node $n_i$ which lies in the shortest path between $n_i$ and $n_j$ , so do node $n_j^{\prime \prime }$ and node $n_j$ . Taking Figure 6(e) for example, the level of connectivity between node $n_i$ and node $n_j$ is computed by

$$\begin{array}{cc}& d\left(n_i,n_j\right)=\frac{\mathrm{1}}{\mathrm{4}+\mathrm{1}/d\left(n_{m\mathrm{2}},n_{m\mathrm{3}}\right)}.\end{array}$$

(29)

Suppose the set of nodes which node $n_i$ could communicate with is denoted by set $N_c=\left\{n_{\mathrm{1}},n_{\mathrm{2}},\dots ,n_c\right\}$ . Then, we define the level of connectivity for node $n_i$ as

$$\begin{array}{cc}& d\left(n_i\right)={\displaystyle \sum }_{j=\mathrm{1}}^c‍d\left(n_i,n_j\right).\end{array}$$

(30)

For N nodes in the whole network, there exist $C_N^{\mathrm{2}}=N(N-\mathrm{1})/\mathrm{2}$ different pairs among them. We define the level of connectivity for the network as

$$\begin{array}{cc}& d\left(N\right)={\displaystyle \sum }_{\forall n_i\in N,\forall n_j\in N}‍d\left(n_i,n_j\right),\hspace{1em}{n}_i\ne n_j.\end{array}$$

(31)

Theoretically, a sufficiently large value of R could result in a situation that there always exists a path between two arbitrary nodes, irrespective of the magnitude of N. With the increase of R, the value of $d\left(N\right)$ will keep increasing until inflection point $\left(\widehat{l},\widehat{d}\right)$ is reached. Here, $\widehat{d}$ is the maximum of $d\left(N\right)$ . For $R⩾\widehat{l}$ , $d\left(N\right)\equiv \widehat{d}$ . In addition, we define $\widehat{l}$ as the degree of convergence of the network. The smaller the $\widehat{l}$ is, the better the network converges.

3.4. Autonomic Switch between Two Modes

In order to facilitate the information updating and network status gathering in the WSN, we introduce a monitoring token which is kept passing around the Chord network. The autonomic switch between the directory-based mode and the directory-less mode is based on the network status gathering. By a round, we mean that the monitoring token is transmitted by all the DAs once. The current mode of the service discovery architecture is indicated by a flag called MODE, and its value is DA-BASED or DA-LESS. In addition, the monitoring token contains two lists: the SA list $sal$ and the DA list $dal$ . The structure of the monitoring token is shown in Figure 7.

Figure 7

Monitoring token.

Though the unified service information management scheme described in Section 3.1.3 stipulates that all nodes in the MANET have knowledge of the properties and values of services, the DAs initially have no idea of any SAs. Thus, we use the monitoring token to perform the information updating associated with SAs. In general, the appearance of a new SA is accompanied by service registration initiated by the SA. For a DA which received a service registration, it updates local database with the service information. When the monitoring token arrives at the DA, the DA checks whether the SA list of the monitoring token contains the SA of the service registration. If the SA already exists, the DA did nothing for the SA. Otherwise, the DA adds the SA to the SA list of the monitoring token. Meanwhile, the DA checks whether there are unknown SAs. The local database is updated with the information of SAs which are unknown to the DA. That is to say, when the monitoring token arrives at a DA, the DA initiates a two-way update about the information of SAs. When an existing SA is about to leave the MANET, it issues a logout message to an arbitrary DA within its radio range. The DA which receives the logout message first removes the service information associated with the SA in the local database. When the monitoring token arrives at the DA, the DA marks a logout flag in the SA list for the SA. During the transmission of the monitoring token, other DAs become aware of the logout of the SA through the two-way update and remove the service information associated with the SA in their local databases. When the monitoring token arrives at the DA next time, the DA issues a logout acknowledgment to the SA. As long as the SA receives the logout acknowledgment, it could leave the network freely and there is no need to logout again. Although there is no topology control and key searching based on the Chord network in the directory-less mode, the transmission of the monitoring token is still operational. Thus, the two-way update, service registration, and SA logout are also performed normally. The detailed information updating procedure is shown in Algorithm 4.

Algorithm 4: Information updating procedure.

  $InformationUpdating\left(da,\text{SReg}[n],token,\text{SA}.\text{logout}[m],round(\mathrm{0})\right)$

(1)  for each $\text{SA}\in token.sal$

(2)   if   $\text{SA}\notin da.sal\hspace{0.17em}\&\&\hspace{0.17em}\text{SA}.availability\ne \text{LOGOUT}$   then

(3)     $da.sal\leftarrow da.sal\cap \left\{\text{SA}\right\}$

(4)   end  if

(5)   if   $\text{SA}\in da.sal\hspace{0.17em}\&\&\hspace{0.17em}\text{SA}.availability==\text{LOGOUT}$   then

(6)     $da.sal\leftarrow da.sal$ ∖ $\left\{\text{SA}\right\}$

(7)     $da.database\leftarrow da.database$ ∖ $\left\{\text{records\hspace{0.17em}of}\hspace{0.17em}\text{SA}\right\}$

(8)   end  if

(9)  end  for

(10) for   $i\leftarrow \mathrm{1}$   to  n

(11)  if   $\text{SReg}[i].\text{SA}\notin da.sal$   then

(12)    $da.sal\leftarrow da.sal\cap \left\{\text{SReg}[i].\text{SA}\right\}$

(13)  end  if

(14)  if   $\text{SReg}[i].\text{SA}\notin token.sal$   then

(15)    $token.sal\leftarrow token.sal\cap \text{SReg}[i].\text{SA}$

(16)  end  if

(17) end  for

(18) for   $j\leftarrow \mathrm{1}$   to  m

(19)  if   $t==round(\mathrm{0})$   then

(20)    $da.sal\leftarrow da.sal\mathrm{\setminus }\left\{\text{SA}.\text{logout}[j]\right\}$

(21)    $da.database\leftarrow da.database\mathrm{\setminus }\left\{\text{records\hspace{0.17em}of\hspace{0.17em}SA}.\text{logout}[j]\right\}$

(22)    $da.set\left(token.sal.entry[\text{SA}.\text{logout}[j]].availability,\text{LOGOUT}\right)$

(23)  else  if   $t==round(\mathrm{1})$   then

(24)       $da.send\left(\text{LOGOUT\_ACK},\text{SA}.\text{logout}[j]\right)$

(25)     end  if

(26)  end  if

(27) end  for

Besides information updating, the monitoring token also plays another vital function: network status gathering. A DA in the WSN senses the local network status in its vicinity. The information of local network statuses is gathered by the monitoring token, and then a high-level overview of the network status is revealed. This overview of the network status facilitates the autonomic switch between the directory-based mode and the directory-less mode. Suppose our service discovery architecture is under the directory-less mode. If the frequency of service query decreases, the frequency of service advertisement should be decreased accordingly. However, if the frequency of service query keeps decreasing significantly, a switch to the directory-based mode is needed. Now, assume our service discovery architecture is under the directory-base mode; if the frequency of service query increases, the frequency of service advertisement should be increased. If the frequency of service query keeps increasing significantly, a switch to the directory-less mode is needed.

In particular, each time the monitoring token arrives at a DA, if the DA realizes that the frequency of service query it perceived locally is beyond a threshold $q{f}_{\mathrm{0}}$ , it adds a plus sign to its entry in the monitoring token. However, if the DA realizes that the frequency of service query it perceived locally is lower than the threshold $q{f}_{\mathrm{0}}$ , it checks whether there exists a plus sign in its entry in the monitoring token. A plus sign which already existed will be removed by the DA. Suppose our service discovery architecture is under the directory-base mode. When a DA keeps adding plus signs for several rounds, a local overload is occurring. Moreover, if a considerable number of DAs have encountered a local overload, the directory-less mode should be used. When the number of DAs which encountered a local overload is small, the directory-based mode should be used. We denote the number of plus signs which indicates a local overload by $lo$ (local overload). Moreover, we denote the percentage of locally overloaded DAs which indicates a mode switch between the two modes by $go$ (global overhead). Suppose the service discovery architecture is under directory-based mode. When the monitoring token arrives at a DA, the DA first updates the number of plus signs in its entry. Then, it examines the entries of all DAs. If the percentage of locally overloaded DAs is larger than $go$ , it changes the value of MODE in the monitoring token from DA-BASED to DA-LESS for the purpose of informing other DAs to switch their modes. Similarly, a reverse switch from DA-LESS to DA-BASED is triggered by a percentage of locally overloaded DAs which is smaller than $go$ . The detailed autonomic mode switch procedure is shown in Algorithm 5.

Algorithm 5: Autonomic mode switch procedure.

  $AutonomicModeSwitch\left(da[n],q{f}_{\mathrm{0}},lo,go,token\right)$

(1)  if   $da[i].qf\_perceived⩾q{f}_{\mathrm{0}}$   then

(2)    $token.dal.entry[i].status\leftarrow token.dal.entry[i].status$   +  “+”

(3)  else  if   $token.dal.entry[i].s\mathrm{t}atus\ne \mathrm{\varnothing }$   then

(4)      $token.dal.entry[i].status\leftarrow token.dal.entry[i].status$   −  “+”

(5)    end  if

(6)  end  if

(7)   $nlo\leftarrow \mathrm{0}$

(8)  for   $k\leftarrow \mathrm{1}$  to  n

(9)   if   $\left|token.dal.entry[k].status\right|⩾lo$   then

(10)     $nlo\leftarrow nlo+\mathrm{1}$

(11)  end  if

(12) end  for

(13) if   $\mathrm{t}\mathrm{o}\mathrm{k}\mathrm{e}\mathrm{n}.\text{MODE}==\text{DA-BASED}$   then

(14)  if   $nlo/n⩾go$   then

(15)    $da[i].set\left(\mathrm{t}oken.\text{MODE},\text{DA-LESS}\right)$

(16)  end  if

(17) else

(18)  if   $\left(nlo/n<go\right)$   then

(19)    $da[i].set\left(token.\text{MODE},\text{DA-BASED}\right)$

(20)  end  if

(21) end  if

4. Numerical Results

4.1. Experimental Environment and Simulation Parameters

For the purpose of evaluating our model, we develop a MANET platform which is based on the NS-2 [45]. All simulation results are obtained on HP with Inter Core2 Q9550 2.83 GHz, 4 GB RAM with Debian 2.6.32-48squeeze1 (Linux version is 2.6.32-5-686) and gcc 4.3.5 (Debian 4.3.5-4).

In our platform, the number of DAs in the WSN is 32. The identifier space of the underlying Chord network is ${\mathrm{2}}^m={\mathrm{2}}^{\mathrm{16}}$ . The numbers of SAs and UAs are 25 and 200, respectively. The number of different complete descriptions for profiling services should be ${\prod }_{i=\mathrm{1}}^{np}‍\left|p_i\right|⩽{\mathrm{2}}^{\mathrm{16}}$ . In [36, 46], the authors use a famous dataset [47] to conduct their experiments. The dataset contains 2507 real web services on the Internet. In this paper, we generate 8000 records of different service information based on the dataset. The consistent hash function based on SHA-1 is employed to calculate the IDs of DAs and the keys of services. The 8000 keys and the corresponding service information (URL, SA) are mapped to the 32 DAs according to the Chord protocol. The IDs of the 32 DAs and the numbers of service records for which each node takes responsibility are shown in Table 3.

Table 3

Information of the 32 DAs.

Number	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
ID	1456	2383	2461	6511	7002	7560	11438	12704	13087	15018	15408	20197	24126	24700	33059	33837
Records	562	124	4	514	55	73	468	153	41	241	34	611	456	71	991	93
Number	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
ID	37271	38208	39176	40539	42247	43982	46340	47226	47396	49090	49122	52350	53654	55839	59680	62300
Records	430	104	135	174	212	221	278	102	15	218	3	423	126	248	485	335

For a DA $da$ and its predecessor $da.predecessor$ on the Chord network, if the IDs of $da$ and $da.predecessor$ are the smallest one and the largest one among all the DAs, respectively, the distance between $da$ and $da.predecessor$ is calculated as

$$\begin{array}{cc}& dis\left(da,da.predecessor\right)=2^m-da.predecessor.id+da.id.\end{array}$$

(32)

Otherwise, we compute the distance between them by

$$\begin{array}{cc}& dis\left(da,da.predecessor\right)=da.id-da.predecessor.id.\end{array}$$

(33)

We define the responsibility ratio of $\mathrm{d}\mathrm{a}$ as the ratio of the number of service records for which $\mathrm{d}\mathrm{a}$ takes responsibility and the distance between $\mathrm{d}\mathrm{a}$ and $\mathrm{d}\mathrm{a}.\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{d}\mathrm{e}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{o}\mathrm{r}$ . And it is computed as

$$\begin{array}{cc}& da.rr=\frac{\left|da.records\right|}{dis\left(da,da.predecessor\right)}.\end{array}$$

(34)

As shown in Figure 8, the responsibility ratios of the 32 DAs are marked as blue crosses and the linear regression equation of them is drawn in red. The responsibility ratios of most DAs are within the range of $\left[\mathrm{0.08,0.14}\right]$ , except for $\mathrm{D}{\mathrm{A}}_{\mathrm{3}}$ . The responsibility ratio of $\mathrm{D}{\mathrm{A}}_{\mathrm{3}}$ is close to 0.05. The IDs of $\mathrm{D}{\mathrm{A}}_{\mathrm{2}}$ and $\mathrm{D}{\mathrm{A}}_{\mathrm{3}}$ are 2383 and 2461, respectively. Since, $\mathrm{D}{\mathrm{A}}_{\mathrm{3}}$ is close to its predecessor $\mathrm{D}{\mathrm{A}}_{\mathrm{2}}$ and the number of service records it is responsible for is small, it takes little responsibility for the service records in the network. As the responsibility is measured by a ratio, it is rational that the responsibility ratio of $\mathrm{D}{\mathrm{A}}_{\mathrm{27}}$ is larger than $\mathrm{D}{\mathrm{A}}_{\mathrm{3}}$ .

Figure 8

Responsibility ratio of 32 DAs.

4.2. Performance Criteria

Though there are various criteria which are used to evaluate the effectiveness of service discovery architectures, we adopt three fundamental criteria: service availability, message overhead, and delay. Each of these criteria is presented below.

4.2.1. Service Availability

Gao and Ma [48] considered that the service availability is the probability that a service is available. It is formulated as the ratio of the number of times a service responds to a user request to the number of total requests made by the user. This definition is targeted at the evaluation of user experience toward a known service. However, the service availability in our model aims to evaluate the performance of service discovery. Thus, we define the service availability from another perspective. In particular, we introduce the service availability of a single node and the service availability of the network. Since service queries and service replies are flowing through all nodes in the network (including UAs, SAs, and DAs), we define the service availability of a single node as the ratio of the total number of incoming service replies to the total number of outgoing service queries. Considering a node $n_i$ , the service availability is denoted as

$$\begin{array}{cc}& s{a}_i=\frac{s{r}_{\left(i,r\right)}}{s{s}_{\left(i,s\right)}}.\end{array}$$

(35)

Then, the service availability of the network is defined as

$$\begin{array}{cc}& s{a}_N=\frac{{\sum }_{i=\mathrm{1}}^{N}s{a}_i}{N}.\end{array}$$

(36)

4.2.2. Message Overhead

The concept of message overhead mainly concerns two types of messages: service queries and service replies. In order to improve the performance of service discovery, both the two kinds of messages are duplicated to a certain extent. Specifically, a service query is duplicated for the purpose of reaching more nodes. While a service reply is duplicated in another way, since there are several copies of service queries, it is rational that there may appear several service replies which are originated from various nodes. As service replies are generated in response to the received service queries, we hold that normal service replies should not be considered as message overhead. Thus, we hold that the message overhead should be measured by the portion of service queries which are duplicated redundantly. We denote the number of service queries issued by node $n_i$ by $s{s}_{(i)}$ . The number of the service replies received by node $n_i$ is denoted by $s{r}_{(i,r)}$ . And $b_i$ percent of the service replies received by node $n_i$ are designated to it. We denote the number of duplicates of $s{s}_{(i)}$ by $\mathrm{d}\mathrm{u}\mathrm{p}\left(s{s}_{(i)}\right)$ . Then, the message overhead of node $n_i$ is defined as

$$\begin{array}{cc}& m{o}_i=\frac{\mathrm{d}\mathrm{u}\mathrm{p}\left(s{s}_{\left(i\right)}\right)}{b_i·s{r}_{\left(i,r\right)}}.\end{array}$$

(37)

Then, the message overhead of the network is defined as

$$\begin{array}{cc}& m{o}_N=\frac{{\sum }_{i=\mathrm{1}}^{N}m{o}_i}{N}.\end{array}$$

(38)

4.2.3. Delay

The response time is a prominent factor of a harmonized user experience. In practice, the delay is greatly concerned by many users. In our model, the delay perceived by a UA consists of two parts: the processing time and the transmission time. Since we do not focus on the relationship between the processing time and the transmission time, we measure the delay in all. Though the number of service queries issued by node $n_i$ is $s{s}_{(i)}$ , it is likely that a part of the service queries finally get no service replies. We denote the number of service queries which finally get one service reply (or several service replies) by $r_i·s{s}_{(i)}$ , where $\mathrm{0}<r_i⩽\mathrm{1}$ . For a service query which at least has one service reply, the delay associated with the service query indicates the time period between node $n_i$ sends the service query and node $n_i$ receives the first corresponding service reply. We denote the time period by t. Then, the delay which node $n_i$ perceived is defined as

$$\begin{array}{cc}& \mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}{\mathrm{y}}_i=\frac{{\sum }_{j=\mathrm{1}}^{r_i·s{s}_{\left(i\right)}}{t}_j}{r_i·s{s}_{\left(i\right)}}.\end{array}$$

(39)

Then, the delay of the network is defined as

$$\begin{array}{cc}& \mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}{\mathrm{y}}_N=\frac{{\sum }_{i=\mathrm{1}}^N\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}{\mathrm{y}}_i}{N}.\end{array}$$

(40)

4.3. Experimental Results and Analysis

The two characteristics of the directory-based mode are energy conservation and function tuning. Both characteristics concentrate on prolong the network lifetime for the WSN. In practice, as certain applications require all the nodes are operational, the network lifetime may mean the time period before the first node failure due to energy exhaustion. However, in most applications, the network lifetime means the time period before a number of the nodes in the network exhaust their energy. Notable topology management schemes have been proposed for energy conservation issues, such as [49–51]. However, a major assumption of these schemes is high density of sensors. In order to investigate the performance of our model, we compare it with the approach proposed by Pan et al. [51]. The simulation result shown in Figure 9 indicates a slightly better performance of our model.

Figure 9

Operational nodes versus time step.

As shown in Figure 9, both percentages of the operational nodes for the two models decrease with the increase of time step. In our experiments, we assume that the percentage of failed nodes which indicates the end of the network lifetime is 50%. Note that this percentage is just used for the comparison between our model and Pan et al.'s model. In fact, our model is able to operate normally even when there are few nodes left in the network. The percentage of the operational nodes falls below 50% around $t=\mathrm{275}$ in our model. Pan et al.'s model performs similar to our model during the period of $t\in \left[\mathrm{0,100}\right]$ . When $t>\mathrm{100}$ , the percentage of the operational nodes of Pan et al.'s model decreases quickly compared to that of ours. Moreover, the percentage of the operational nodes falls below 50% around $t=\mathrm{225}$ in Pan et al.'s model.

Now, we consider our directory-based mode alone. For three fixed values of the frequency of service query $s{f}_i=0.006$ , 0.008, and 0.01, the service availability of the network and the delay of the network are plotted in Figures 10 and 11, respectively.

Figure 10

Service availability versus time step.

Figure 11

Delay versus time step.

As shown in Figure 10, the values of service availability of the network for $s{f}_i=0.006$ , 0.008, and 0.01 are fluctuated in the range of 60%~90%. In our model, the $〈key,\mathrm{U}\mathrm{R}\mathrm{L}〉$ information of a node which leaves the network is transferred to the successor of the node. Thus, the decrease of operational nodes imposes slight influence on the service availability of the network. Note that service queries are generated based on service information which is wishfully created by UAs and DAs. Though the Chord network itself is able to guarantee the normal search of a key, there are chances that some service queries lead to no service replies. This is why the values of the service availability of the network are less than 100% even at the early stage of simulation. Since a large frequency of service query brings more burden to the DAs than that of a small frequency of service query, the slight differences of service availability of the network among the three curves are caused by DAs which are about to fail. These DAs miss issuing service replies by chance. Thus, the ordering of the service availability of the network is roughly $s{f}_i=\mathrm{0.006}>s{f}_i=\mathrm{0.008}>s{f}_i=\mathrm{0.01}$ .

As shown in Figure 11, the values of delay of the network for $s{f}_i=0.006$ , 0.008, and 0.01 increase with the increase of time step. Since the number of operational nodes is decreasing with the increase of time step, the work load which a DA confronts with is getting heavier with the increase of time step. Thus, a service query may encounter a long processing time. Though there are fewer DAs in the WSN, the shortening of transmission time is no match for the growth of processing time. Hence, the total delay is inevitably increased. In addition, a large frequency of service query also results in a larger backlog than that of a small frequency of service query. Thus, the ordering of the delay of the network is roughly $s{f}_i=\mathrm{0.01}>s{f}_i=\mathrm{0.008}>s{f}_i=\mathrm{0.006}$ .

For the directory-less mode, we adopt a fixed setting of $b_i=\mathrm{0.1}$ and $f_i=\mathrm{0.15}$ . Namely, $b_i$ percent of the service replies received by node $n_i$ are designated to it. Among the service replies which should be forwarded by node $n_i$ , $f_i$ percent of them cannot be forwarded to the next node. The number of plus signs which indicates a local overload is $lo=\mathrm{4}$ . The percentage of locally overloaded DAs which indicates a mode switch between the two modes is $go=\mathrm{75}\%$ . Since a sufficiently large value of R could result in a situation that there always exists a path between two arbitrary nodes, we adopt the maximum of k as 10. Then, the number of recursions $R=⌊\left(k-\mathrm{1}\right)/\mathrm{4}⌋=\mathrm{2}$ . In order to facilitate an in-depth analysis of our model, we consider two cases of distribution for the level of connectivity for the network: uniform distribution and proportional distribution. For all nodes in the MANET, the numbers of pairs for 10 levels of connectivity are illustrated in Figure 12. In the case of uniform distribution, the numbers of pairs for 10 levels of connectivity are uniformly distributed. In the case of proportional distribution, the number of pairs is in proportion to the level of connectivity.

Figure 12

Number of pairs for 10 levels of connectivity.

As previously described, the mode switch between the directory-based mode and the directory-less mode is triggered by the percentage of locally overloaded DAs. Essentially, a local overload for a DA is caused by excessively frequent service queries. In order to investigate the mode switch of our model, we conducted extensive simulations to find an empirical threshold of the frequency of service query. Finally, we learned that the empirical threshold of the frequency of service query is $q{f}_{\mathrm{0}}=\mathrm{0.003}$ . Namely, a value of $q{f}_{\mathrm{0}}$ which is greater than 0.003 will lead to more than 75% locally overloaded DAs and then triggers a mode switch from directory-based to directory-less.

Figure 13 shows the service availability of the network under the two distributions. When $q{f}_{\mathrm{0}}\in \left[\mathrm{0.0005,0.003}\right]$ , the simulation is under directory-based mode. Since the early stage of simulation is under directory-based mode, the difference between the two distributions is not significant. When $q{f}_{\mathrm{0}}\in \left[\mathrm{0.003,0.0055}\right]$ , the simulation is under directory-less mode. As the uniform distribution could provide more small levels of connectivity between two nodes than that of proportional distribution, a node could communicate with more distant nodes. Thus, the values of service availability of the network under the uniform distribution are larger than their counterparts under the proportional distribution.

Figure 13

Service availability versus frequency of service query.

As shown in Figure 14, the delay of the network monotonically increases with the increase of the frequency of service query when $q{f}_{\mathrm{0}}\in \left[\mathrm{0.0005,0.003}\right]$ and monotonically decreases when $q{f}_{\mathrm{0}}\in \left[\mathrm{0.003,0.0055}\right]$ . The simulation result indicates that the differences between the two distributions under both directory-less mode and directory-based mode are not significant.

Figure 14

Delay versus frequency of service query.

As shown in Figure 15, when $q{f}_{\mathrm{0}}\in \left[\mathrm{0.0005,0.003}\right]$ , the values of message overhead of the network under both distributions remain in one. When the mode switches to the directory-less mode, the values of message overhead of the network under both distributions monotonically increase with the increase of the frequency of service query. In addition, the differences between the two distributions under both directory-less mode and directory-based mode are not significant when $q{f}_{\mathrm{0}}\in \left[\mathrm{0.003,0.0055}\right]$ . Thus, the performance of the directory-based mode is superior to the directory-less mode in terms of message overhead.

Figure 15

Message overhead versus frequency of service query.

Through the experimental results shown in Figures 13–15, it can be observed that the mode switch function of our model could significantly improve the performance of service discovery in terms of service availability, message overhead, and delay.

5. Conclusions

With the increasing need for flexible service discovery architectures for service discovery in MANET environment, we propose and evaluate a collaborative self-governing privacy-preserving wireless sensor network architecture. The proposed architecture is based on the Chord protocol and focuses on location optimization and energy conservation. The key function of the architecture is that it provides an autonomic mode switch between the directory-based mode and the directory-less mode. In order to evaluate our model, we developed a MANET platform and conducted extensive simulations regarding three critical criteria concerning service discovery: service availability, message overhead, and delay. The simulation results indicate that the autonomic mode switch between the directory-based mode and the directory-less mode greatly improves the performance of service discovery in terms of the above three criteria. One open issue is how to effectively determine an empirical threshold of the frequency of service query.