Wenjun Liu
email: w-jliu@163.com

Jianxi Fan
email: jxfan@suda.edu.cn

Shukui Zhang
email: zhansk@suda.edu.cn

Xi Wang

Relay Hop Constrained Rendezvous Algorithm for Mobile Data Gathering in Wireless Sensor Networks

Keywords: Wireless Sensor Networks, NP-Hard, Mobile collector, Rendezvous node

Recent research shows that significant energy saving can be achieved in wireless sensor networks (WSNs) by introducing mobile collector (MC). One obvious bottleneck of such approach is the large data collection latency due to low mobile speed of MC. In this paper, we propose an efficient rendezvous based mobile data gathering protocol for WSNs, in which the aggregated data will be relayed to Rendezvous Node (RN) within bounded hop d. The algorithm design in the protocol jointly considers MC tour and data routing routes in aggregation trees. The effectiveness of the approach is validated through both theoretical analysis and extensive simulations.

Introduction

In recent years Wireless Sensor Networks (WSNs) have become an attractive technology for a large number of applications, ranging from monitoring [START_REF] Xu | A Wireless Sensor Network for Structural Monitoring[END_REF], localization [START_REF] Yang | Quality of Trilateration: Confidence based Iterative Localization[END_REF], to target tracking [START_REF] Samarah | A Predictive Energy-Efficient Technique to Support Object-Tracking Sensor Networks[END_REF]. To design and deploy sophisticated WSNs, many issues need to be resolved such as node deployment, energy conservation, routing in dynamic environments, and so on. Specifically, most of these existing solutions for data collection take advantage of multi-hop routing to relay data. One obvious drawback of this schema is that it leads to unbalanced energy consumption among the sensors on the transmission path to sink [START_REF] Batalin | Call and Response: Experiments in Sampling the Environment[END_REF].

Recent research has shown a rapid transition from traditional data gathering pattern to introduction of mobile elements, which can improve energy efficiency, connectivity, and reliability effectively [START_REF] Francesco | Data Collection in Wireless Sensor Networks with Mobile Elements: A Survey[END_REF]. A typical application scenario is that a forest ranger who equipped with handheld device roams in the network and gathers the information of detective area. In such an application, mobile user can visit different regions in the network and communicate with the sensors nearby in single hop paradigm, which reduces not only contention and collisions, but also the message loss. However, due to the low velocity of the mobile collector, usually 0.5-2m/s, e.g. Packbot [START_REF] Somasundara | Mobile Element Scheduling with Dynamic Deadlines[END_REF], it would incur long latency if every node is traveled in data gathering [START_REF] Francesco | Data Collection in Wireless Sensor Networks with Mobile Elements: A Survey[END_REF]. Obviously, it can not meet the requirement of time-sensitive applications.

In order to shorten data gathering latency, integrating multi-hop transmission scheme into mobile data gathering is an effective approach [START_REF] Rao | Analyzing Multi-hop Routing Feasibility for Sensor Data Harvesting using Mobile Sink[END_REF], in which a subset of sensors is selected as Rendezvous Node (RN). In this pattern, at every transmission hop each node aggregates the local data from its affiliated sensors, until delivers to RN which caches and uploads data to the mobile collector (MC) when it arrives. However, it is necessary that the transmission hop should be constrained as a proper level for several reasons. First, energy saving is considered as the most important concern in WSNs. Adopting multi-hop routing to relay data can easily result in unbalanced energy consumption among sensors, and it is adverse for energy-limited nodes. Second, a big relay hop means that the node acting as RN should have high performance to aggregate and cache data before MC arrives. Third, time-sensitive applications often require the sensing data to be delivered with certain deadline. For instance, in the application of forest fire monitoring, the fire should be detected and reported instantly.

The main contributions of this paper can be summarized as follows: 1) We define the mobile data gathering problem based on RN as MDG-RN, which jointly considers MC tour and routes in aggregation trees, and prove it is NP-Hard. 2) We develop two efficient algorithms to solve the MDG-RN problem. The former is a heuristic algorithm which always selects the node with maximum load from the d-hop neighbors of the current farthest node to BS. The latter caters to the characteristic of WSNs, and selects RN iteratively in distributed manner. On the basis of selected RNs, using algorithm for Traveling Salesman Problem (TSP) to produce MC tour, along which MC periodically visits these RNs and picks up the cached data. 3) Simulation results show that both algorithms can achieve satisfactory performance comparing with existing schemes.

The rest of the paper is organized as follows: Section 2 reviews related work. Section 3 introduces the network model and problem definition. The major contributions are introduced in Section 4 and Section 5. The simulation results are presented in Section 6. Finally, Section 7 concludes this paper.

Related Work

Recently, many research efforts have appeared in the literature to explore mobilityenable data collection in sensor networks [START_REF] Francesco | Data Collection in Wireless Sensor Networks with Mobile Elements: A Survey[END_REF][START_REF] Somasundara | Mobile Element Scheduling with Dynamic Deadlines[END_REF][START_REF] Rao | Analyzing Multi-hop Routing Feasibility for Sensor Data Harvesting using Mobile Sink[END_REF][START_REF] Nesamony | On Optimal Route of a Calibrating Mobile Sink in a Wireless Sensor Network[END_REF][START_REF] He | A Progressive Approach to Reducing Data Collection Latency in Wireless Sensor Networks with Mobile Elements Sinks[END_REF][START_REF] Ma | SenCar: An Energy-Efficient Data Gathering Mechanism for Large-Scale Multihop Sensor Networks[END_REF][START_REF] Gatzianas | A Distributed Algorithm for Maximum Lifetime Routing in Sensor Networks with Mobile Sink[END_REF][START_REF] Xing | Efficient Rendezvous Algorithms for Mobility-Enabled Wireless Sensor Networks[END_REF][START_REF] Zhao | Bounded Relay Hop Mobile Data Gathering in Wireless Sensor Networks[END_REF]. These approaches may be classified as uncontrollable or controllable in general [START_REF] Francesco | Data Collection in Wireless Sensor Networks with Mobile Elements: A Survey[END_REF]. The former is obtained by attaching a collector node on certain mobile entity such as an animal or a bus; the latter is achieved by intentionally adding a mobile entity e.g., a mobile robot or an unmanned aerial vehicle, into the network to carry the collector. Clearly, a controlled mobility gives more flexibility for designing a data collection scheme.

The major performance bottleneck of such mobility-enabled WSNs is the increased latency in data collection. There are many approaches address to the delay problem. The first category is using the single hop transmission scheme. It is not difficult to conclude that direct-contact data collection is generally equivalent to the NP-complete TSP. Nesamony et al. [START_REF] Nesamony | On Optimal Route of a Calibrating Mobile Sink in a Wireless Sensor Network[END_REF] formulated the traveling problem as TSP with Neighborhood, where a MC needs to visit the neighborhood of each sensor exactly once. He et al. in [START_REF] He | A Progressive Approach to Reducing Data Collection Latency in Wireless Sensor Networks with Mobile Elements Sinks[END_REF] proposed a progressive optimization approach, called CSS, to reduce the tour length, and thus the data collection latency. This kind of approach minimizes the network energy consumption by one hop transmission, but it incurs high latency when collecting data from large sensing fields due to the slow speed of MC.

In second category multi-hop transmissions is adopted. Ma et al. [START_REF] Ma | SenCar: An Energy-Efficient Data Gathering Mechanism for Large-Scale Multihop Sensor Networks[END_REF] gave a moving path planning algorithm by finding some turning points, which is adaptive to the sensor distribution and can effectively avoid obstacles on the path. In [START_REF] Gatzianas | A Distributed Algorithm for Maximum Lifetime Routing in Sensor Networks with Mobile Sink[END_REF], Gatzianas et al. optimized data gathering performance by presenting a distributed maximum lifetime routing algorithm, where a mobile collector sequentially visits a set of anchor points and each sensor transmits data to the mobile collector at some anchor points via multi-hop paths. Such type of approach reduces latency effectively. However, without the hop count constraint, the unbalanced energy consumption leads to untimely network partition.

The last category is a hybrid approach with constraint conditions that usually jointly considers multi-hop data transmissions and the moving tour of MC in data collection. Xing et al. [START_REF] Xing | Efficient Rendezvous Algorithms for Mobility-Enabled Wireless Sensor Networks[END_REF] proposed a rendezvous-based data collection approach under the constraint that the tour length of the mobile collector is no longer than a threshold. With the relay hop constraint, Zhao et al. [START_REF] Zhao | Bounded Relay Hop Mobile Data Gathering in Wireless Sensor Networks[END_REF] proposed a pollingbased mobile data gathering scheme that minimize the tour length of MC and data gathering latency. They give two algorithms to find a set of PPs among sensors. In [START_REF] Rao | Analyzing Multi-hop Routing Feasibility for Sensor Data Harvesting using Mobile Sink[END_REF], Rao et al. establishes bounds for multi-hop routing as a function of sensor and MC parameters such as data generation rate, sink speed and sensor density. They developed a framework to parameterizes multi-hop routing using a hop-bound factor k. Their model revealed that for stable mobile sink operation, there exists a feasible range of the hop-bound factor k. The approach studied in this paper falls into this category.

Preliminary

Network Model

We assume N sensor nodes are scattered randomly over the interest area and left unattended to continuously sense and report events. There is a static BS located in the center of sensing area and a mobile collector (MC) moved in controlled mobility. MC knows its own physical locations through the GPS units on it. However, for generality, we do not make such assumption on sensor nodes. Under the consideration of same communication range, the communication links are symmetric. We consider WSN as a undirected graph G(V, E), where the vertex set V represents all the sensors and the edge set E represents the communication links. Two vertices, u and v in V , are adjacent if there is a edge e=(u,v)∈ E, then we say u is neighbor of v, and vice versa.

A path P = < v 1 , v 2 , • • • , v l > of length l -1 for l ≥ 2 in
G is a sequence of distinct vertices such that any two consecutive vertices are adjacent. The neighbors of a vertex v, denoted by N (v), is the set of all vertices adjacent to v in G. The d-hop neighbors of node v is denoted by d-N (v).

In data-centric WSNs, data from sources will be sent to RN or BS continuously, thus the data routes should be created in advance. On the basis of underlying topology G, a set of directed aggregation tree T = {T i } represents logic communication topology. For any T i , 0 < i < N , its root is the node r i in RN. For any link e ∈ G, the communication cost is represented by its Euclidean distance. In addition,we assume the N -to-one aggregation model is adopted, in which a node can aggregate multiple data packets it received into one packet before relaying it [START_REF] Madden | TAG: A Tiny Aggregation Service for Ad-Hoc Sensor Networks[END_REF].

Definitions

In the data collection schema, the RNs cache the data originated from sources and send to the MC via short-range transmissions when it arrives. The requirement is that the total length of MC tour should be minimized under the relay hop constraint. We refer to this problem as Mobile Data Gathering based on Rendezvous Nodes (MDG-RN) which is defined as follow:

Definition 1. Given a set of sensors S = {s 1 , s 2 , . .

. , s N } and relay hop d, look for 1) A set of RN R; 2) A MC tour U connected all nodes in R and BS such that

∑ (u,v)∈U | uv | is minimized, where (u, v) is a line segment on U and | uv | is its Euclidean distance; 3) A set of aggregation trees {T i (V i , E i )} with height at most d that are rooted at r i ∈ R such that ∪ i V i = S and ∑ i ∑ (u,v)∈Ei | uv | is minimized.
From the definition of MDG-RN problem, the distribution of RNs and the data routes in each aggregation tree with the hop constraint should be jointly considered in order to find optimal solution. Thus the MDG-RN problem in this case can be formulated as:

M inimize ∑ (u,v∈U ) |uv| (1) Subject to c h si,ri = 1, ∀s i ∈ S, ∀r i ∈ R, 0 ≤ h ≤ d. (2) ∑ ri∈R c h si,ri = 1, ∀s i ∈ S, 0 ≤ h ≤ d. ( 3
)
|s i r i | ≤ |s i r j |, ∀s i ∈ S, ∀r i ∈ R, r i ̸ = r j (4)
For nodes r, v ∈ V in G, we claim r covers v, if there is a path from v to r. A node v is d-hop covered by r if this path has the length no lager than d, written as c d v,r . A set of sensors are covered by r means an aggregation tree rooted at r is produced. The d-hop cover guarantees that any packet from the sources can be sent to rendezvous node r within d hops. As aforementioned, in ideal N -to-one aggregation mode, the total length of communication edges in an aggregation tree is more worthy of attention comparing with the number of nodes associated with RNs. We define the transmission cost as load formally. The load of a node v, written as Load(v), is the total edge length associated with it in aggregation tree T in network. If the height of aggregation tree rooted at v is d then its load is called d-hop load, written as d -Load(v). For node v, its uncovered d-hop load is the d-hop load except the edge length connecting the covered nodes in T , and it is written as unC -d -Load(v).

Theorem 1. The MDG-RN problem is NP-hard.

Proof. This problem can be shown to be NP-hard by a polynomial-time reduction from the Euclidean Traveling Salesman Problem. Specifically, a special case of the decision version of MDG-RN problem is to ask if there exists a set of RNs such that all the sources must be RNs. This can be done by modifying the node transmission range R t . When R t is small enough, nodes are unreachable from each other. In such case, the relay hop d is equal to 0, and then MC must visit all the RNs to collect data. Thus the MDG-RN problem is NP-hard.

⊓ ⊔

Algorithm for MDG-RN Problem

Due to the NP-hardness of the MDG-RN problem, in this section, we develop a Load Priority based RN Determination Algorithm (LP-RDA) for this problem.

The basic idea of algorithm is to determine a set of RNs such that its total number is minimum and its distribution is near the BS as much as possible under the constraint of relay hop counts, and that the load of RNs is also optimized.

The LP-RDA algorithm can be described as the following 3 steps: STEP 1: INITIALIZATION for any node s i ∈ S s i .status := not -Covered; computes s i .dist -to -BS base on received signal strength; sends FB -Msg(s i .ID, dist -to -BS, hopC) to BS hop-by-hop;

At beginning, static BS broadcasts "BEACON" message network-wide at a certain power. Each node computes the approximate distance to BS, dist -to -BS, base on the received signal strength. After that, every node sends message FB -Msg() to BS hop-by-hop. BS obtains the information of nodes in network after receiving these feedback messages. STEP 2: ITERATION BS determines a appropriate starting node x; for any node s j ∈ d-N G (x) find a new RN r i which has maximum unC -d -Load(s j ). r i sends Declar -Msg() to d-N(r i ) and r j .status:= Covered; for any s j receiving Declar -Msg() from r i if s j .status = not -Covered then it joins its RN and s j .status := Covered;

The iterative process to determine node status as shown in STEP 2. Depending on whether it is d-hop covered by RN, each node is set in one of two states: "Covered" or "not -Covered". Initially, all nodes are in the state of "un -Covered". The node with maximum hopC, x, is selected as the starting node. For the same hopC, the node with little dist -to -BS is selected. For d-N (x), each node computes its unC -d -Load() by local message exchange. Next, algorithm tests the nodes in d-N (x) toward the direction of BS such that the node with maximum unC -d -Load() is determined as new RN. The selected RN declares its identity by sending declaration message within its d-hop neighbors. Those uncovered nodes received this message will register as its member node and mark itself as covered. While there are uncovered nodes in the network, algorithm selects a new starting node again. Repeat this process, until all the nodes are covered by RNs. STEP 3: OPTIMIZATION for any s j receiving Declar -Msg() from r i if s j .status = Covered and |s j r i | < |s j r j |) then changes its RN from r j to r i when receives r i 's message;

We notice that a part of nodes in d-N (r i ) may have become the member of other tree T j , j < i already. In order to optimize the load of aggregation tree, if these covered nodes are closer to a new RN r i , then they will disaffiliate themselves from original roots and join r i . The optimization pseudo-code as shown in STEP 3 above.

An example demonstrates the execution of LP-RDA as shown in Fig. 1. The solid circles represent sensors and the black ones indicate that they are covered by RNs. The gray line segments show the connectivity, and the directed line segments represent the data routes in aggregation trees. Initially, no node is covered. Although 18 and 1 have the same 4 hops, the former with smaller dist -to -BS is selected as the starting node. Its uncovered 2-hop neighbor set is {10, 11, 15, 19}. 11 is the desirable one which will send Declar -Msg() to recruit its members. After its neighbors at most 2-hop away joining in this RN, they are covered as shown in Fig. 1b. Similarly, node 1 with 4 hops is selected as the next starting node. In the process of construction of aggregation trees, a part of nodes change their routes whenever shorter distance to new RN arises, e.g., node 8 changes its RN from 3 to 13, with which the optimization is accomplished. Fig. 1c gives the final result which produce the data gathering tour of MC as highlighted by the red line segments.

Theorem 2. LP-RDA has the time complexity of O(N 2 +N d),

where N is the number of sensors in network, d is the relay hop.

Proof. During the initial stage, every node sends feedback message to BS hop by hop after receiving the BS's "BEACON" message. It takes O(N ) time for BS to gather network information. Next, BS starts the iterative RN selection process. At every turn, LP-RDA selects the farthest node v as the starting node, it will no larger than N even in the worst case. Moreover, in each turn it takes O(d) time for v's d-hop neighbors d-N (v) compute their load, the RN declares its identify, and the MN joins new RN, respectively. Thus the iteration requires O(dN ) time. Finally, adopting existing approximate algorithm for TSP to produce the MC tour will take O(N 2 ) time. Thus, the total time spent is

O(N ) + O(3dN ) + O(N 2 ). The time complexity of LP-RDA is O(N 2 + dN ).
⊓ ⊔

Distributed Algorithm for MDG-RN Problem

According to the assumption above, every node only knows the existence of its direct neighbors, thus the information acquisition of d-hop neighbors is mainly completed via d-hop information exchange. The execution of Algorithm needs BS's schedule and it can not be executed in fully distributed pattern. In the following, we present a Tree based Distributed RN Determination Algorithm (T-DRDA), which can be identified as 3 steps.

STEP 1: INITIALIZATION Construct SDT T under the constraint of R t ; s i .status:= Suspensive;

The initialization pseudo-code executed by each senor as shown in STEP 1. Initially, each node has the same status "Suspensive". We claim the branches of a node in T are its sub-trees rooted at its direct children, and the local height of a branch (LHB) is the tree height from current node to its known farthest child in local message exchange. For any node x, its LHB of i-th branch is noted as x.br -LHB[i]. Every node sends local exchange message Exg -Msg() to its father within d hops along T . When any node in the network receives messages from its children, it will perform relevant statistics and then forward or destroy the message depending on specific conditions. After d-hop message propagation, each node has the information of its d-hop neighbors. According to the obtained local information, each node makes decision of its status as shown the code in STEP 2. If the LHB of each branch is less than d and its parent is not null, then this node becomes a member node (MN), then it will wait for a Join -Msg(). If there is a node whose LHB is exactly d, or it includes a branch whose LHB is less than d and its parent is null, then node turns into RN, and send declaration message Declar -Msg() to recruit its members within d hops range along tree including its parent and children. However, if current node's LHB is lager than d, then its status is still undetermined. STEP 3: JOIN -RN Upon receiving Declar -Msg(r j , h) in T if s i .status = Suspensive then s i .status:= MN and sends Join -Msg() to register as MN with r j ;

For STEP 3, whenever nodes receive Declar -Msg(), they change their status as "Covered", and register as MN with the sender. If multiple such messages are received, the nearest sender is chosen. Next, MN sends Join -Msg() to inform RN of its joining. After receiving the join messages, RN registers these nodes as its members and performs necessary maintenance and management. Note that when any MN determines a RN, it will be deleted from T . The remainder nodes in sub-tree repeat this procedure until every node becomes a RN or MN. Fig. 2 illustrates the execution of distributed algorithm. The gray, red and black nodes represent MN, RN and undetermined nodes, respectively. Fig. 2a shows the initial network topology under the constraint R t . Fig. 2b depicts the node statuses after the first iteration. Fig. 2c gives the final statuses of all nodes and the MC tour. Finally, we give the following properties which show the complexity of the T-DRDA algorithm. During each iteration, each node generates d messages at most which are sent to its parent within d-hop in T . In the decision stage, each RN sends a declaration message to its d-hop neighbors in T . After receiving the declaration, its neighbors register with this node as MN by sending a join message. Both messages are restricted in d hop during the broadcast. That is, the number of messages that forwarded by single node in T will no more than d. Therefore, the total number of messages that a node has to handle is at most

d + 1 + d. Thus the message complexity of T-DRDA is O(N ) + O(d) = O(N + d) per node. ⊓ ⊔

Performance Evaluation

In this section, we evaluate the performance of proposed algorithms and present the simulation results. The performance metrics are mainly the number of RNs (N RN ), the iterations, and the tour length of MC (L M CT ). We first evaluate the performance by varying the parameters, and then compare them with two existing mobile data gathering schemes, SPT-DGA and PB-PSA [START_REF] Zhao | Bounded Relay Hop Mobile Data Gathering in Wireless Sensor Networks[END_REF]. SPT-DGA is a centralized algorithm, in which within the relay hop bound it iteratively finds an set of PPs among the sensors on a shortest path tree. Whereas, PB-PSA obtains the desirable solution in a distributed manner. We adopt the Nearest-Neighbor (NN) algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF] in the simulation to determine the moving tour. Fig. 3 shows the performance of LP-RDA and T-DRDA under different transmission ranges (R t ). We can see that N RN in both algorithms decreases quickly with the increase of R t . The reason is that under the same node density a big R t leads to the d-hop neighbors of a sensor increasing significantly, which means that less RNs can cover all nodes in the network. Obviously, in such case the load of each RN will increase with decrease of N RN . The increase of R t makes hopC reduced. Therefore, for the iterations in LP-RDA, it is consistent with hopC, and decreases dramatically in Fig. 3b. It is worth pointing out that small iterations Fig. 4 plots the relationship between N RN and d. In the figure, under fixed R t = 30m, N RN in both algorithms decreases with d. The revelation of this result is that a tradeoff should be made between local message overhead and latency. On one hand, under fixed R t a small relay hop means the data can be aggregated to RNs quickly, but MC tour length will increase inevitably, which will cause a long latency. On the other hand, if the relay hop is too large, then the load of RNs will increase, accordingly, which not only calls for high node performance, but also result in unbalanced energy consumption.

In the following, we simulate the performance of LP-RDA and T-DRDA comparing with PB-PSA and SPT-DGA under different network sizes. Fig. 5 depicts the iterations of different algorithms as a function of network nodes N . We can see that comparing with that the iterations of centralized algorithms increasing with network sizes significantly, distributed schemes keeps a low growth and has excellent efficiency. For example, T-DRDA needs only 1 iteration when N is less than 100. Even under the case N = 400, algorithm needs 3.15 rounds on average. The reason LP-RDA excels SPT-DGA is that at every turn the former selects RN from the node with maximum d-hop load within its uncovered d-hop neighbors, which produces as less N RN as possible. Furthermore, during the execution, the iteration of algorithm is scheduled by BS, which has unlimited functionality. Finally, Fig. 6 depicts N RN and L M CT under different network sizes N . By contrast, the centralized algorithm receives more optimized N RN . In order to ensure a short MC tour, the selection of RN in algorithm design mainly considers two factors: one is approaching its location to static BS, the other is decreasing their number. Under fixed d, a smaller L M CT means a short latency of data gathering. We can see that the centralized algorithms are superior to distributed algorithms and the proposed algorithms outperform the other two algorithms.

Conclusions

In this paper, we study relay constrained mobile data gathering with mobile collector. We develop two efficient rendezvous based data gathering algorithms. One is a heuristic algorithm which always selects the node with maximum load from the d-hop neighbors of the current farthest node to BS. The other caters to the characteristic of WSNs, and selects RN iteratively from far to near in distributed manner. Both of them jointly consider MC tour and data routing routes in aggregation trees. The effectiveness of our algorithms is validated through both theoretical analysis and extensive simulations.

Fig. 1 .

 1 Fig. 1. An example to illustrate LP-RDA algorithm (N =20, d=2). (a) Initial topology. (b) The cover after the first RN is determined. (c) The final RNs, aggregation trees, and MCs tour.

Fig. 2 .

 2 Fig. 2. An example to illustrate T-DRDA (N =23, d=2). (a) Initial topology. (b) RNs and their MNs after iteration 1. (c) The final RNs, aggregation tree, and MC tour.

STEP 2 :

 2 STATUS DETERMINATION if s i .status = Suspensive then for each branch of s i if s i .br -LHB[j] < d-1 and s i .parNode != Null then s i .status:= MN; else if s i .br -LHB[j] = d-1 or (s i .parNode = Null and s i .br -LHB[j] < d-1) then s i .status:= RN and sends Declar -Msg() to d-N(s i ) in T;

Theorem 3 .

 3 T-DRDA has the time complexity of O(N ), where N is the number of sensors. Proof. T-DRDA adopts SDT T as underlying communication topology which can be constructed in O(1) time. In the worst-case, sensor will experience N/d iterations at most. In each iteration, it takes O(d) time for node to obtains d-hop neighbors information by local exchange. With the gathered information, each node makes its decision independently by O(1) time. After that, RN and MN will send declaration and join messages with O(d) time, respectively. Therefore, The total time complexity in T-DRDA is O(1)+O(N/d) * O(3d+1) = O(N ). ⊓ ⊔ Theorem 4. T-DRDA has the message exchange complexity of O(N + d) per node, where N is the number of sensors, and d is the relay hop counts. Proof. SDT T in T-DRDA can be constructed with message complexity O(N ).

Fig. 3 .Fig. 4 .Fig. 5 .

 345 Fig. 3. Performance of LP-RDA and T-DRDA under different transmission ranges Rt. (a) The number of RNs versus Rt. (b) The iterations versus Rt.

Fig. 6 .

 6 Fig. 6. Performance of LP-RDA and T-DRDA under different network sizes. (a) The number of RNs versus networks. (b) Tour length versus network sizes.

Acknowledgments. This work is supported by National Natural Science Foundation of China (61170021), Specialized Research Fund for the Doctoral Program of Higher Education (20103201110018), Natural Science Foundation of Jiangsu (BK2011376), Application Foundation Research of Suzhou of China (SYG201240, SYG201118), Program for Postgraduates Research Innovation in University of Jiangsu Province (CXZZ12 -0817), Science and Technology Innovation Team Building Program of Soochow University (SDT2012B02), and Project for Excellent Doctoral Dissertation Topic in Soochow University (23320216).


Xi Wang

Jianxi Fan
email: jxfan@suda.edu.cn

Baolei Cheng
email: chengbaolei@suda.edu.cn

Wenjun Liu

Yan Wang
email: wangyanme@suda.edu.cn

One-to-One Disjoint Path Covers in DCell

Keywords: DCell, Data Center Network, Disjoint Path Covers, Hamiltonian

DCell has been proposed for one of the most important data center networks as a server centric data center network structure. DCell can support millions of servers with outstanding network capacity and provide good fault tolerance by only using commodity switches. In this paper, we prove that there exist r vertex disjoint paths {Pi|1 ≤ i ≤ r} between any two distinct vertices u and v of DCell k (k ≥ 0) where r = n + k -1 and n is the vertex number of DCell0. The result is optimal because of any vertex in DCell k has r neighbors with r = n + k -1.

Introduction

Data centers become more and more important with the development of cloud computing. Specifically, in recent years, data centers are critical to the business of companies such as Amazon, Google, FaceBook, and Microsoft, which have already owned tremendous data centers with more than hundreds of thousands of servers. Their operations are important to offer both many on-line applications such as web search, on-line gaming, email, cloud disk and infrastructure services such as GFS [START_REF] Ghemawat | The Google file system[END_REF], Map-reduce [START_REF] Dean | MapReduce: Simplified data processing on large clusters[END_REF], and Dryad [START_REF] Isard | Dryad: distributed data-parallel programs from sequential building blocks[END_REF].

Researches showed that the traditional tree-based data center networks [START_REF] Guo | Dcell: a scalable and fault-tolerant network structure for data centers[END_REF] have issues of bandwidth bottleneck, failure of single switch, etc.. In order to solve the defects of tree-based data center networks, there are many data center networks which have been proposed such as DCell [START_REF] Guo | Dcell: a scalable and fault-tolerant network structure for data centers[END_REF], BCube [START_REF] Guo | BCube: a high performance, server-centric network architecture for modular data centers[END_REF], and FiConn [START_REF] Li | FiConn: Using backup port for server interconnection in data centers[END_REF][START_REF] Li | Scalable and cost-effective interconnection of data-center servers using dual server ports[END_REF]. DCell has many good properties including exponential scalability, high network capacity, small diameter, and high fault tolerantly. In comparison with good capabilities of DCell, BCube is meant for container-based data center networks which only supports thousands of servers, and FiConn is not a regularly network which may raises the construction complexity.

DCells use servers as routing and forwarding infrastructure, and the multicast routing frequency between servers are quite high in data center networks. Multi-cast routing algorithms in DCells can be based on the Hamiltonian model as methods on [START_REF] Lin | Deadlock-free multicast wormhole routing in 2-D mesh multicomputers[END_REF][START_REF] Wang | Multicast communication in wormhole-routed symmetric networks with hamiltonian cycle model[END_REF]. One-to-one disjoint path covers (also named spanning connectivity [START_REF] Lin | On the spanning connectivity of graphs, Discrete Mathematicsl[END_REF][START_REF] Lin | On spanning connected graphs[END_REF]) are the extension of the Hamiltonian-connectivity which could as well as used on multi-cast routing algorithms in DCells to largely decrease deadlock and congestion, compared with tree-based multi-cast routing. However, the problem of finding disjoint path covers is NP-complete [START_REF] Park | Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements[END_REF]. Therefore, a large amount researches on problems of disjoint path covers focused on different special networks, such as hypercubes [START_REF] Park | Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements[END_REF][START_REF] Caha | Spanning multi-paths in hypercubes[END_REF][START_REF] Chen | Many-to-many disjoint paths in faulty hypercubes[END_REF][START_REF] Chen | Paired many-to-many disjoint path covers of hypercubes with faulty edges[END_REF], their variants [START_REF] Park | Many-to-many disjoint path covers in the presence of faulty elements[END_REF][START_REF] Ma | The spanning connectivity of folded hypercubes[END_REF][START_REF] Shih | One-to-one disjoint path covers on k-ary n-cubes[END_REF], and others [START_REF] Hsu | The spanning connectivity of the (n, k)-star graphs[END_REF][START_REF] Chen | Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs[END_REF][START_REF] Huanga | The spanning connectivity of line graphs[END_REF].

So far there is no work reported about the one-to-one disjoint path cover properties of DCell. In this paper, we prove that there exist r vertex disjoint paths {P i |1 ≤ i ≤ r} between any two distinct vertices u and v of DCell k (k ≥ 0) where n is the vertex number of DCell 0 and r = n + k -1. The result is optimal because of any vertex in DCell k has r neighbors with r = n + k -1.

This work is organized as follows. Section 2 provides the preliminary knowledge. Some basic one-to-one disjoint path covers properties are given in Section 3. We make a conclusion in Section 4.

Preliminaries

A data center network can be represented by a simple graph G = (V (G) , E (G)), where V (G) represents the vertex set and E (G) represents the edge set, and each vertex represents a server and each edge represents a link between servers (switches can be regarded as transparent network devices [START_REF] Guo | Dcell: a scalable and fault-tolerant network structure for data centers[END_REF]). The edge from vertex u to vertex v is denoted by (u, v). In this paper all graphs are simple and undirected.

We use

G 1 ∪ G 2 to denote the subgraph induced by V (G 1 ) ∪ V (G 2 ) of G. For U ⊆ V (G), we use G[U ] to denote the subgraph induced by U in G, i.e., G[U ] = (U, E ′ ), where E ′ = {(u, v) ∈ E(G)|u, v ∈ U }.
A path in a graph is a sequence of vertices, P :< u 0 , u 1 , . . . , u j , . . . u n-1 , u n >, in which no vertices are repeated and u j , u j+1 are adjacent for 0 ≤ j < n. Let V (P ) denote the set of all vertices appearing in P . We call u 0 and u n the terminal vertices of P . P can be denoted by P (u 0 , u n ), which is a path beginning with u 0 and ending at u n . Let P 1 denote < u 1 , u 2 , . . . , u k-1 , u k > and P 2 denote < u k , u k+1 , . . . , u k+n >, then P 1 + P 2 denotes the path < u 1 , u 2 , . . . , u k , u k+1 , . . . , u k+n >. If e = (u k , u k+1 ), then P 1 + e denote the path < u 1 , u 2 , . . . , u k , u k+1 >. Furthermore, if e = (u k-1 , u k ), P 1 -e denote the path < u 1 , u 2 , . . . , u k-1 >.

A path in a graph G containing every vertex of G is called a Hamiltonian path (HP ). HP (u, v, G) can be denoted by a Hamiltonian path beginning with a vertex u and ending with another vertex v in graph G. We say a set of r paths between u and v is an r-disjoint path cover in G if the r paths do not contain the same vertex besides u and v and their union covers all vertices of G. An r-disjoint path cover is abbreviated as an r-DPC for simplicity.

Obviously, if (v, u) ∈ E(G), then HP (u, v, G) + (v, u) is a Hamiltonian cycle in G. A
A graph G is one-to-one r-disjoint path coverable (r-DPC-able for short) if there is an r-DPC between any two vertices of G. In this paper G is r-DPC-able is not same as G is (r + 1)-DPC-able.

For any other fundamental graph theoretical terminology, please refer to [START_REF]West and others: Introduction to graph theory[END_REF]. DCell uses recursively-defined structure to interconnect servers. Each server connects to different levels of DCell through multiple links. We build high-level DCell recursively form many low-level ones. Due to this structure, DCell uses only mini-switches to scale out instead of using high-end switches to scale up, and it scales doubly exponentially with server vertex degree.

We use DCell k to denote a k-dimension DCell (k ≥ 0), DCell 0 is a complete graph on n vertices (n ≥ 2). Let t 0 denote the number of vertices in a DCell 0 , where t 0 = n. Let t k denote the number of vertices in a DCell k (k ≥ 1), where

t k = t k-1 × (t k-1 + 1). The vertex of DCell k can be labeled by [α k , α k-1 , • • • , α i , • • • , α 0 ], where α i ∈ {0, 1, • • • , t i-1 }, i ∈ {1, 2, • • • , k}, and α 0 ∈ {0, 1, • • • , t 0 -1}.
According to the definition of DCell k [START_REF] Guo | Dcell: a scalable and fault-tolerant network structure for data centers[END_REF][START_REF] Kliegl | Rincon: Generalized DCell structure for load-balanced data center networks[END_REF], we provide the recursive definition as Definition 1.

Definition 1. The k-dimensional DCell, DCell k , is defined recursively as follows.

(

) DCell 0 is a complete graph consisting of n vertices labeled with [0],[1],• • • ,[n- 1]. (2) For any k ≥ 1, DCell k is built from t k-1 + 1 disjoint copies DCell k-1 1
, according to the following steps.

(2.1) Let DCell 0 k-1 denote the graph obtained by prefixing the label of each vertex of one copy of DCell k-1 with 0. Let DCell 1 k-1 denote the graph obtained by prefixing the label of each vertex of one copy of DCell k-1 with 1.

• • • . Let DCell t k-1
k-1 denote the graph obtained by prefixing the label of each vertex of one copy of DCell k-1 with t k-1 . Clearly, DCell 0

k-1 ∼ = DCell 1 k-1 ∼ = • • • ∼ = DCell t k-1 k-1 . (2.2) For any α k , β k ∈ {0, 1, • • • , t k-1 } and α k ≥ β k (resp. α k < β k ), con- necting the vertex [α k , α k-1 , • • • , α i , • • • , α 1 , α 0 ] of DCell α k k-1 with the vertex [β k , β k-1 , • • • , β i , • • • , β 1 , β 0 ] of DCell β k k-1 as follow:              α k = β 0 + k-1 ∑ j=1 (β j × t j-1 ) + 1 β k = α 0 + k-1 ∑ j=1 (α j × t j-1 ) (1) (resp.              α k = β 0 + k-1 ∑ j=1 (β j × t j-1 )
β k = α 0 + k-1 ∑ j=1 (α j × t j-1 ) + 1 (2)
), where 1(1), 1(2), and 1(3) demonstrate DCell 0 , DCell 1 , and DCell 2 with t 0 = 2 respectively. 1(4) and 1(5) demonstrate DCell 0 and DCell 1 with t 0 = 3 respectively.

α i , β i ∈ {0, 1, • • • , t i-1 }, i ∈ {1, 2, • • • , k}, and α 0 , β 0 ∈ {0, 1, • • • , t 0 -1}. By Definition 1, DCell α k k-1 is a subgraph of DCell k , where α k ∈ {0, 1, • • • , t k-1 }. Figure

Main results

In this section, we will study one-to-one disjoint path cover properties of DCell.

Theorem 1. DCell k (k ≥ 0) is Hamiltonian-connected with t 0 ≥ 2 except for DCell 1 with t 0 = 2 . In other word, DCell k (k ≥ 0) is 1-DPC-able with t 0 ≥ 2 except for DCell 1 with t 0 = 2.

P roof . We omit the proof due to the page limitation. 2 Theorem 2. DCell k is a Hamiltonian graph for any k ≥ 0. In other word, DCell k is 2-DPC-able for any k ≥ 0.

P roof . We omit the proof due to the page limitation. 2 Lemma 1. DCell 0 is (t 0 -1)-DPC-able with t 0 ≥ 2. P roof . The lemma holds for DCell 0 which is a complete graph [START_REF]West and others: Introduction to graph theory[END_REF].

2 Lemma 2. DCell 1 is 2-DPC-able with t 0 = 2. P roof . DCell 1 is a cycle with 6 vertices. Therefore, DCell 1 is 2-DPC with t 0 = 2 [START_REF]West and others: Introduction to graph theory[END_REF].

2 Lemma 3. DCell 2 is 3-DPC-able with t 0 = 2. P roof . For t 0 = 2, we use construction method to proof this lemma. We can construct an 3-DPC between u and v in DCell 2 for any pair of vertices {u, v} ∈ V (DCell 2 ).

For example, the 3-DPC {P 1 , P

2 , P 3 } (resp. {R 1 , R 2 , R 3 }, {T 1 , T 2 , T 3 }, {S 1 , S 2 , S 3 }, {U 1 , U 2 , U 3 }) from [0, 0, 0] to [0, 0, 1] (resp. [0, 1, 0], [0, 1, 1], [0, 2, 0], [0, 2, 1]
) whose union covers V (DCell 2 ) with t 0 = 2 are listed below (Similarly for the other cases). [6, 1, 1], [6, 1, 0], [6, 0, 0], [6, 0, 1], [6, 2,

P 1 =< [0, 0, 0], [0, 0, 1] >, P 2 =< [0, 0, 0], [0, 1, 0], [0, 1, 1], [0, 2, 1], [0, 2, 0], [0, 0, 1] >, P 3 =< [0, 0, 0], [1, 0, 0], [1, 0, 1], [2, 0, 1], [2, 2, 0], [2, 2, 1], [2, 1, 1], [4, 1, 0], [4, 0, 0], [4, 0, 1], [4, 2, 0], [5, 2, 0], [5, 2, 1], [6, 2, 1], [6, 1, 1], [6, 1, 0], [6, 0, 0], [6, 0, 1], [6, 2, 0], [4, 2, 1], [4, 1, 1], [3, 1, 1], [3, 2, 1], [3, 2, 0], [5, 1, 1], [5, 1, 0], [5, 0, 0], [5, 0, 1], [1, 2, 0], [1, 2, 1], [1, 1, 1], [1, 1, 0], [3, 0, 1], [3, 0, 0], [3, 1, 0], [2, 1, 0], [2, 0, 0], [0, 0, 1] >. R 1 =< [0, 0, 0], [0, 1, 0] >, R 2 =< [0, 0, 0], [0, 0, 1], [0, 2, 0], [0, 2, 1], [0, 1, 1], [0, 1, 0] >, R 3 =< [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 2, 0], [1, 2, 1], [1, 1, 1], [1, 1, 0], [3, 0, 1], [3, 2, 0], [3, 2, 1], [3, 1, 1], [4, 1, 1], [4, 2, 1], [6, 2, 0], [6, 0, 1], [6, 0, 0], [6, 1, 0], [6, 1, 1], [6, 2, 1], [5, 2, 1], [5, 1, 1], [5, 1, 0], [5, 0, 0], [5, 0, 1], [5, 2, 0], [4, 2, 0], [4, 0, 1], [4, 0, 0], [4, 1, 0], [2, 1, 1], [2, 2, 1], [2, 2, 0], [2, 0, 1], [2, 0, 0], [2, 1, 0], [3, 1, 0], [3, 0, 0], [0, 1, 0] >. T 1 =< [0, 0, 0], [0, 1, 0], [0, 1, 1] >, T 2 =< [0, 0, 0], [0, 0, 1], [0, 2, 0], [0, 2, 1], [0, 1, 1] >, T 3 =< [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 2, 0], [1, 2, 1], [1, 1, 1], [1, 1, 0], [3, 0, 1], [3, 0, 0], [3, 1, 0], [2, 1, 0], [2, 0, 0], [2, 0, 1], [2, 2, 0], [2, 2, 1], [2, 1, 1], [4, 1, 0], [4, 1, 1], [3, 1, 1], [3, 2, 1], [3, 2, 0], [5, 1, 1], [5, 1, 0], [5, 0, 0], [5, 0, 1], [5, 2, 0], [5, 2, 1], [6, 2, 1],
0], [4, 2, 1], [4, 2, 0], [4, 0, 1], [4, 0, 0], [0, 1, 1] >. S 1 =< [0, 0, 0], [0, 0, 1], [0, 2, 0] >, S 2 =< [0, 0, 0], [0, 1, 0], [0, 1, 1], [0, 2, 1], [0, 2, 0] >, S 3 =< [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 2, 0], [1, 2, 1], [1, 1, 1], [1, 1, 0], [3, 0, 1], [3, 0, 0], [3, 1, 0], [3, 1, 1], [4, 1, 1], [4, 1, 0], [4, 0, 0], [4, 0, 1], [4, 2, 0], [4, 2, 1], [6, 2, 0], [6, 0, 1], [6, 0, 0], [6, 1, 0], [2, 2, 1], [2, 1, 1], [2, 1, 0], [2, 0, 0], [2, 0, 1], [2, 2, 0], [5, 1, 0], [5, 1, 1], [3, 2, 0], [3, 2, 1], [6, 1, 1], [6, 2, 1], [5, 2, 1], [5, 2, 0], [5, 0, 1], [5, 0, 0], [0, 2, 0] >. U 1 =< [0, 0, 0], [0, 0, 1], [0, 2, 0], [0, 2, 1] >, U 2 =< [0, 0, 0], [0, 1, 0], [0, 1, 1], [0, 2, 1] >, U 3 =< [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 2, 0], [1, 2, 1], [1, 1, 1], [1, 1, 0], [3, 0, 1], [3, 0, 0], [3, 1, 0], [2, 1, 0], [2, 0, 0], [2, 0, 1], [2, 2, 0], [5, 1, 0], [5, 0, 0], [5, 0, 1], [5, 2, 0], [4, 2, 0], [4, 0, 1], [4, 0, 0], [4, 1, 0], [2, 1, 1], [2, 2, 1], [6, 1, 0], [6, 1, 1], [6, 2, 1], [5, 2, 1], [5, 1, 1], [3, 2, 0], [3, 2, 1], [3, 1, 1], [4, 1, 1], [4, 2, 1], [6, 2, 0], [6, 0, 1], [6, 0, 0], [0, 2, 1] >. 2 Lemma 4. For any α, β ∈ {0, 1, • • • , t k }, m ∈ {1, 2, • • • , t k -3}, and α ̸ = β, let x ∈ V (DCell α
k ) be an arbitrary white vertex, y ∈ V (DCell β k ) be an arbitrary black vertex, and

G 0 = DCell α k ∪ DCell β k ∪ ( ∪ m θ=0 DCell ω θ k ), where DCell α k , DCell β k , DCell ω0 k , • • • , DCell ωi k , • • • , DCell ωm k are internally vertex-independent with i ∈ {0, 1, • • • , m} and ω i ∈ {0, 1, • • • , t k }.
Then there exists a path between x and y that containing every vertex in DCell k [V (G 0 )] where k ≥ 1 and t 0 = 2.

P roof . Let G 1 = DCell α k ∪DCell β k . Select z ∈ V (DCell α k ) and u ∈ V (DCell γ k ), such that z ̸ = x, (u, z) ∈ E(DCell k ), and DCell γ k ⊆ G 0 , where two graphs G 1 and DCell γ k are internally vertex-independent. Select ω ∈ V (DCell β k ) and v ∈ V (DCell δ k ), such that ω ̸ = y, (ω, v) ∈ E(DCell k )
, and DCell δ k ⊆ G 0 where three graphs G 1 , DCell γ k , and DCell δ k are internally vertex-independent. According to Theorem 1, there exists a path P from x to z that containing every vertex in DCell α k and a path Q from ω to y that containing every vertex in

DCell β k . Let G 2 = G 0 [V ( ∪ m θ=0 DCell ω θ k )].
We can construct a path S from u to v that containing every vertex in G 2 which is similar to Theorem 1. Then there exists a path P + (z, u) + S + (v, ω) + Q between x and y that containing every vertex in DCell k [V (G 0 )] where k ≥ 1 and t 0 = 2. 2 Lemma 5. DCell k is (k + 1)-DPC-able with k ≥ 2 and t 0 = 2. P roof . We will prove this lemma by induction on the dimension k of DCell. By lemma 3, the lemma holds for t 0 = 2 and k = 2. For t 0 = 2, supposing that the lemma holds for k = τ (τ ≥ 2), we will prove that the lemma holds for k = τ + 1.

For any vertex x, y

∈ V (DCell τ +1 ) with x ̸ = y. Let x ∈ V (DCell α τ ) and y ∈ V (DCell β τ ) with α, β ∈ {0, 1, • • • , t τ }.
We can identity α and β as follows. Case 1. α = β. There exist (τ + 1) vertex disjoint paths {P i |1 ≤ i ≤ τ + 1} between any two distinct vertices x and y of DCell α τ . Select u ∈ V (DCell γ τ ) and v ∈ V (DCell δ τ ), such that (x, u), (y, v) ∈ E(DCell τ +1 ), where three graphs DCell α τ , DCell γ τ , and DCell δ τ are internally vertex-independent. According to Lemma 4, there exists a path P τ +2 from u to v that visits every vertex in

DCell τ +1 [V (DCell τ +1 -DCell α τ )]. Then there exist (τ +2) vertex disjoint paths {P i |1 ≤ i ≤ τ + 2} between any two distinct vertices x and y of DCell τ +1 . Case 2. α ̸ = β and (x, y) ∈ E(DCell τ +1 ). Let P 1 =< x, y >. Select x 0 ∈ V (DCell α τ ) (resp. y 0 ∈ V (DCell β τ )), such that (x, x 0 ) ∈ E(DCell α τ ) (resp. (y, y 0 ) ∈ E(DCell β τ )).
According to the induction hypothesis, there exist (τ + 1) vertex disjoint paths

{P ′ i |2 ≤ i ≤ τ + 2} (resp. {Q ′ j |2 ≤ j ≤ τ + 2}
) between any two distinct vertices x and x 0 (resp. y 0 and y) in DCell α τ (resp.

DCell β τ ). Let P ′′ 2 =< x, x 0 > (resp. Q ′′ 2 =< y 0 , y >), P ′ i =< x, • • • , x i , x 0 > (resp. Q ′ j =< y 0 , y j , • • • , y >)
, and

P ′′ i = P ′ i -(x i , x 0 ) (resp. Q ′′ j = Q ′ j -(y 0 , y j )) with 3 ≤ i ≤ τ +2 (resp. 3 ≤ j ≤ τ +2). Furthermore, let z i ∈ V (DCell γi τ ) (resp. w j ∈ V (DCell δj τ )) with 2 ≤ i ≤ τ + 2 (resp. 2 ≤ j ≤ τ + 2) and (x i , z i ) ∈ E(DCell τ +1 ) (resp. (y i , w j ) ∈ E(DCell τ +1 )). Let W 0 = ∪ τ +2 θ=2 DCell γ θ τ , W 1 = ∪ τ +2 θ=2 DCell δ θ τ and W = W 0 ∪ W 1 ∪ DCell α τ ∪ DCell β τ . For 2 ≤ i ≤ τ + 2
, we can claim the following two subcases with respect to DCell γi τ . Case 2.1.

DCell γi τ ⊆ W 1 . Select w j ∈ V (DCell γi τ ) such that 2 ≤ j ≤ τ + 2.
According to Theorem 1, there exists path a S from z i to w j in DCell γi τ . Furthermore, let W = W ∪ DCell γi τ and

P i = P ′′ i + (x i , z i ) + S + (w j , y j ) + Q ′′ j . Case 2.2. DCell γi τ ̸ ⊆ W 1 . Select DCell δj τ +1 ̸ ⊆ W such that 2 ≤ j ≤ τ + 2.
Then, choose DCell p τ and DCell q τ , such that three graphs DCell p τ , DCell q τ , and W are are internally vertex-independent with p, q ∈ {0, 1, ) are internally vertex-independent. We can claim the following three subcases with respect to u and v. Case 3.1. u ∈ V (DCell β τ ). Select x 0 ∈ V (DCell α τ ), such that (x, x 0 ) ∈ E(DCell α τ ). Let y 0 = u. According to the induction hypothesis, there exist (τ + 1) vertex disjoint paths {P ′ i |2 ≤ i ≤ τ + 2} (resp. {Q ′ j |1 ≤ j ≤ τ + 1}) between any two distinct vertices x and x 0 (resp. y 0 and y) in DCell α τ (resp.

• • • , t k }. Let W ′ i = DCell γi τ ∪ DCell δj τ ∪ DCell p τ ∪ DCell q τ , according to Lemma 4, there exists a path S from z i to w j in DCell τ [W ′ i ]. Furthermore, let W = W ∪ W ′ i and P i = P ′′ i + (x i , z i ) + S + (w j , y j ) + Q ′′ j . Furthermore, select P i , such that z i ̸ ∈ V (W 1 ) and w j ∈ V (W ′ i ) where 2 ≤ i ≤ τ + 2 and 2 ≤ j ≤ τ + 2. According to Lemma 4, there exists path S from z i to w j in DCell τ +1 [V (W ′ i ) ∪ (V (DCell τ +1 ) -V (W ))].
DCell β τ ). Let P 1 = (x, y 0 ) + Q ′ 1 and Q ′′ τ +2 = ∅. Then, let P ′′ 2 =< x, x 0 >, P ′ i =< x, • • • , x i , x 0 > (resp. Q ′ j =< y 0 , y j , • • • , y >), and P ′′ i = P ′ i -(x i , x 0 ) (resp. Q ′′ j = Q ′ j -(y 0 , y j )) with 3 ≤ i ≤ τ + 2 (resp. 2 ≤ j ≤ τ + 1). Further- more, let z i ∈ V (DCell γi τ ) (resp. w j ∈ V (DCell δj τ )), where 2 ≤ i ≤ τ + 2 (resp. 1 ≤ j ≤ τ + 1), w τ +2 = v ∈ V (DCell δτ+2 τ
), and (x i , z i ) ∈ E(DCell τ +1 ) (resp. (y i , w j ) ∈ E(DCell τ +1 )). The required {P i |2 ≤ i ≤ τ + 2} paths can be derived by the similar approach as the Case 2, so we skip it.

According to discussions in Case 3 and Case 3.1, there exist (τ + 2) vertex disjoint paths {P i |1 ≤ i ≤ τ + 2} between any two distinct vertices x and y of DCell τ +1 .

Case 3.2. v ∈ V (DCell α τ ). The required paths can be derived by the similar approach as the Case 3.1, so we skip it.

Case

3.3. u ̸ ∈ V (DCell β τ ) and v ̸ ∈ V (DCell α τ ). Let P ′′ 1 = Q ′′ 1 = ∅, x 1 = x, z 1 = u, w 1 = v and y 1 = y. Select x 0 ∈ V (DCell α τ ) (resp. y 0 ∈ V (DCell β τ )), such that (x, x 0 ) ∈ E(DCell α τ ) (resp. (y, y 0 ) ∈ E(DCell β τ )).
According to the induction hypothesis, there exist (τ + 1) vertex disjoint paths

{P ′ i |2 ≤ i ≤ τ + 2} (resp. {Q ′ j |2 ≤ j ≤ τ + 2}
) between any two distinct vertices x and x 0 (resp. y 0 and y) in DCell α τ (resp. DCell β τ ). Let

P ′′ 2 =< x, x 0 > (resp. Q ′′ 2 =< y 0 , y >), P ′ i =< x, • • • , x i , x 0 > (resp. Q ′ j =< y 0 , y j , • • • , y >), and P ′′ i = P ′ i -(x i , x 0 ) (resp. Q ′′ j = Q ′ j -(y 0 , y j )) with 3 ≤ i ≤ τ + 2 (resp. 3 ≤ j ≤ τ + 2). Furthermore, let z i ∈ V (DCell γi τ +1 ) (resp. w j ∈ V (DCell δj τ )), where 2 ≤ i ≤ τ + 2 (resp. 2 ≤ j ≤ τ + 2) and (x i , z i ) ∈ E(DCell τ +1 ) (resp. (y i , w j ) ∈ E(DCell τ +1 )). The required {P i |1 ≤ i ≤ τ + 2}
paths can be derived by the similar approach as the Case 2, so we skip it.

According to discussions in Case 3 and Case 3.3, there exist (τ + 2) vertex disjoint paths {P i |1 ≤ i ≤ τ + 2} between any two distinct vertices x and y of DCell τ +1 .

In summary, for any two distinct vertices x, y ∈ V (DCell τ +1 ), there exist (τ + 2) vertex disjoint paths {P i |1 ≤ i ≤ τ + 2} between any two distinct vertices x and y of DCell τ +1 .

2 Lemma 6. For any t 0 ≥ 3 and k ≥ 0, DCell k is (k + t 0 -1)-DPC-able. P roof . We will prove this lemma by induction on the dimension k of DCell. For any t 0 ≥ 3, by Lemma 1, the lemma holds for k = 0. For any t 0 ≥ 3, supposing that the lemma holds for k = τ , where τ ≥ 0, the proof that the lemma holds for k = τ + 1 is similar to that of lemma 5 and thus omitted. 2 Theorem 3. DCell k is (k + t 0 -1)-DPC-able with k ≥ 0. P roof . By Lemma 1, the theorem holds for k = 0 and t 0 ≥ 2. By Lemma 2, the theorem holds for k = 1 and t 0 = 2. By Lemma 5, the theorem holds for k ≥ 2 and t 0 = 2. By Lemma 6, the theorem holds for t 0 ≥ 3 and k ≥ 0. 2

Conclusions

DCell has been proposed for one of the most important data center networks and can support millions of servers with outstanding network capacity and provide good fault tolerance by only using commodity switches. In this paper, we prove that there exist r vertex disjoint paths {P i |1 ≤ i ≤ r} between any two distinct vertices u and v of DCell k (k ≥ 0) where n is the vertex number of DCell 0 and r = n + k -1. The result is optimal because of any vertex in DCell k has r neighbors with r = n + k -1. According to our result, the method in [START_REF] Lin | Deadlock-free multicast wormhole routing in 2-D mesh multicomputers[END_REF][START_REF] Wang | Multicast communication in wormhole-routed symmetric networks with hamiltonian cycle model[END_REF] can be used to decrease deadlock and congestion in multi-cast routing in DCell.

Fig. 1 .

 1 Fig. 1. (1), (2), and (3) demonstrate DCell0, DCell1, and DCell2 with t0 = 2 respectively. (4) and (5) demonstrate DCell0 and DCell1 with t0 = 3 respectively.

  Furthermore, let P i = P ′′ i + (x i , z i ) + S + (w j , y j ) + Q ′′ j . According to above discussions, there exist (τ + 2) vertex disjoint paths {P i |1 ≤ i ≤ τ + 2} between any two distinct vertices x and y of DCell τ +1 . Case 3. α ̸ = β and (x, y)̸ ∈ E(DCell τ +1 ). Select u ∈ V (DCell τ +1 ) (resp. v ∈ V (DCell τ +1 )), such that (x, u) ∈ E(DCell τ +1 ) (resp. (y, v) ∈ E(DCell τ +1 )), u ∈ DCell ϕ τ (resp. v ∈ DCell ψ τ ),and ϕ, ψ ∈ {0, 1, • • • , t k }, where DCell α τ and DCell ϕ τ (resp. DCell β τ and DCell ψ τ

  Hamiltonian graph is a graph containing a Hamiltonian cycle. G is called a Hamiltonianconnected graph if there exists a Hamiltonian path between any two different vertices of G. Obviously, if G is a Hamiltonian-connected graph, then G must be the Hamiltonian graph. Suppose that u and v are two vertices of a graph G.

Acknowledgments

This work is supported by National Natural Science Foundation of China (61170021), Specialized Research Fund for the Doctoral Program of Higher Education (20103201110018), Application Foundation Research of Suzhou of China (SYG201240), and Graduate Training Excellence Program Project of Soochow University (58320235).


Waseem Ahmed

Yong Wei Wu

Probabilistic QoS Analysis of Web Services

Keywords: Hidden states, Probability, Quality of Service

In such a competitive world, quality assurance can make the difference between a successful business and bankruptcy. For Internet services, the presence of low performance servers, high latency or overall poor service quality can translate into lost sales, user frustration and customers lost. In this paper, we propose a novel method for QoS metrification based on Hidden Markov Models. The techniques we show can be used to measure and predict the behavior of Web Services under several criteria, and can thus be used to rank services quantitatively rather than just qualitatively. We demonstrate the feasibility and usefulness of our methodology by drawing experiments on real world data. Our results have shown how our proposed methods can help the user to automatically select the best available Web Service based on several metrics, among them system predictability and response times variability.

Introduction

The Internet made the world a smaller place. Companies from all around the world may now compete over different service offerings not only with their local adversaries, but do now under a global scale. Escalating the competition and lead in industry segment can often be a matter of offering and, perhaps even most importantly, assuring the good quality of the services offered. In the Web this should be no different; controlling quality for Web Services (WS) is done by enforcing Quality of Service (QoS) policies and assuring needed quality conditions are always met.

On the user's side, the increased number of services means more and more offerings to choose from. Unfortunately, due the explosive growth in the number of WSs available in the world, selecting the best WS to solve a given task has become a quite challenging task. Currently, users cast their choice based on the reviews and experiences of other users. User-created ranks are often the first resource for finding reliability information regarding a particular service, often given in terms of response time, throughput, availability, security and reliability. Interestingly enough, data quality has never been considered as a key factor when analyzing QoS parameters.

There is no standard way, however, for the users to weigh their options directly and individually, for themselves. This paper aims to fill this gap providing a standard way to measure and assess WS quality using Hidden Markov Model (HMM). Although web service reliability can be defined as producing cohesive results when invoked by different users with similar parameters [START_REF] Askaroglu | Automatic QoS evaluation method for web services[END_REF], even though, sometimes web service even with best rank provides different results to end users. Systems which are designed to produce different results to different users at same time interval are out of the scope of this paper.

Existing papers such as [START_REF] Askaroglu | Automatic QoS evaluation method for web services[END_REF][START_REF] D"ambrogio | A Model-driven Approach to Describe and Predict the Performance of Composite Services[END_REF][START_REF] Yilei | WSPred: A Time-Aware Personalized QoS Prediction Framework for Web Services[END_REF][START_REF] Zibin | Distributed QoS Evaluation for Real-World Web Services[END_REF][START_REF] Maheswari | QoS Based Efficient Web Service Selection[END_REF][START_REF] Menasce | QoS issues in Web services[END_REF] have discussed in detail QoS attributes of web services in terms of response time, throughput, reliability, availability. Nonetheless, there is still a lack of analyzing quality of data received from web services. Users across the IT industry associate bad quality of data or difference in response of web services against same request at same time with improper use of technology such as:

 Improper use of instance variables  Incorrect caching  Wrong mapping of data in lookup tables (in case of DB operation)  Service is unable to recognize received category  Servers are behind cluster and node responsible for reply during time t behaves badly  Improper or mutated coding However, as web services are owned and hosted by other organizations, most of the above mentioned aspects are difficult to monitor. In this paper we have designed a framework based on Hidden Markov Model (HMM) that will help end users to find a relation among web service responses and different hidden states producing them. Later, we have further extended this framework to predict behavioral patterns of these hidden states that will help users in making decision for web service selection. In our framework, we have randomly selected web services with similar functionality (e.g. in our case it represent weather forecasting) from the list provided by [START_REF] Zibin | Distributed QoS Evaluation for Real-World Web Services[END_REF] (who have claimed to have almost all available services by crawling web) and webserviceslist.com to analyze quality of data, that were ranked as best by different users around the world (as shown in table1). Status of all selected web services with similar functionality is more or less similar as described in [START_REF] Zibin | Distributed QoS Evaluation for Real-World Web Services[END_REF]. Our contribution in this paper can be summarized as below:  We have analyzed the reason of variation in data generated by web service when invoked by different users at the same time with same input parameters.  Defined a mechanism to build a relation among web service response / result and various hidden states responsible for producing it.  Predicted the probability of variation in data / response of web services during nth time interval to select WS with better QoS attributes in terms of data. The rest of the paper is organized as follows: section 2 introduces related work section 3 describes details about our conceptual framework section 4 presents our experiment and results and finally section 5 concludes the paper. Temperature (T) 3.

Visibility (V) 4.

Due Point (D) 5.

Humidity(H) 6.

Wind(W) 7.

Pressure (P) [START_REF] Askaroglu | Automatic QoS evaluation method for web services[END_REF] proposed a method where they tracked QoS parameters automatically when required. However the issue with this approach is that, they did not consider network latency or communication delay in their calculations. Daniel A. Menascé [START_REF] Menasce | QoS issues in Web services[END_REF] have proposed a way to calculate throughput of web services that have been used in single web service to accomplish its task. Ping Wang [START_REF] Ping | A Fuzzy Model for Selection of QoS-Aware Web Services[END_REF] has used fuzzy logic to locate and select web services based on user ratings. Other papers that have been produced to estimate QoS attributes to select better web service for integration are San-Yih Hwang [START_REF] San-Yih | A probabilistic approach to modeling and estimating the QoS of web-servicesbased workflows[END_REF], Vuong Xua [START_REF] Tran | A new QoS ontology and its QoS-based ranking algorithm for Web services[END_REF], Xifeng [START_REF] Xifeng | Ontology-Based Reliability Evaluation for Web Service[END_REF] ,Hong Qing [START_REF] Hong Qing | A Method for Automated Web Service Selection[END_REF], Chunli [START_REF] Chunli | A Staged Model for Web Service Reliability[END_REF], Wei, Z. [START_REF] Wei | QoS-Based Dynamic Web Service Composition with Ant Colony Optimization[END_REF].

#
Hidden Markov Model has already been used in analyzing quality factors of distributed computing systems. Nonetheless, they have their own issues, constraints and shortcomings. For instance Vathsala and Hrushikesha [START_REF] Vathsala | Using HMM for predicting response time of web services[END_REF] have used HMM for predicting response time pattern of web services for different network"s hidden states, however they did not consider the reliability of various hidden states with in the remote web service as discussed in Table II. As survivability also affects performance of any application, LeiLei Chen [START_REF] Leilei | Evaluating the Survivability of SOA Systems Based on HMM[END_REF] has designed a framework to evaluate survivability of SOA based application using Hidden Markov Model. The main idea of their framework revolves around monitoring activities based on service logs or run time statistics provided by service provider. The problem with this approach is that it is restricted to statistics which have been provided by the service provider itself. Besides, the author did not provide a discussion about the possible hidden states and other probabilistic characteristics inherent to WSs. The HMM has also been successfully used in the prediction of other QoS aspects for SOA applications. One of such works is the work by Rahnavard and Meisam [START_REF] Rahnavard | A method to evaluate Web Services Anomaly Detection using Hidden Markov Models[END_REF], who have used HMMs to detect WS anomalies, such as intrusion detection. However, their strategy could not be used to gauge arbitrary QoS attributes of WSs. Similarly, Flex Selfner [START_REF] Salfner | Predicting Failures with Hidden Markov Models[END_REF] has proposed the use of HMMs to categorize and distinguish error patterns leading to failures. This author also suggested a mechanism for predicting the future occurrence of failures or errors. Zaki Malik [START_REF] Zaki | Web Services Reputation Assessment Using a Hidden Markov Model[END_REF] has used HMM to assess failures during certain time in future.

In short HMM has been successfully used to analyze various aspects in distributed computing systems. The reliability of a WS can be established only once the reliability of hidden states have been ensured [START_REF] Ahmed | A survey on reliability in distributed systems[END_REF]. In this paper we have design a framework based on HMM for estimating probabilistic insight details of web service.

HMM Based Quality of Service Estimation

For probabilistic QoS analysis of web services in terms of data variation, our strategy is based on following steps:

 Analyzing variation among data values of web services response when invoked by a number of users with similar input parameters.  Estimating current state of internal system of WS using HMM and then defining probabilistic relationship among data values and various hidden states.  Predicting behavioral pattern of hidden states for analyzing data variance during nth time interval.

Similarity Analysis

Estimating QoS attribute in terms of data variance requires us to elucidate web service response into a set of independent variables. This will help us to analyze data variation in more detail. For instance in case of weather forecasting, the consequent response can be divided into N number of different independent variables as defined in table 2. As each web service is being invoked by M number of users and we have K number of web services having similar functionalities. To find the similarity among such data values we can represent above information in 3-dimentional N x M x K matrix. Web services with higher rank were invoked by 500 parallel threads with same input parameters in distributed environment and results were analyzed as shown in Fig. 1. It is apparent from Fig. 1 that web services even with higher rank are replying with uncertain results during time interval t. Fig. 1a shows variation in status (Sunny, Rainy, Partially cloudy, Cloudy) received by different users for same request parameters, whereas Fig. 1 (b, c andd) depicts variation in independent variables (Wind, Visibility, and Temperature). For proof of concept we have shown only some independent variables, nonetheless, we have found variation in all independent variables. Region specific WS for instance weather forecast (US only) have produced better performance in comparison to other web services.

Quality of Service Analysis with Hidden Markov Model

Similarity analysis shows that independent variables can have different values within one observation when invoked in parallel with same request parameters. To figure out consequent data categories, it is therefore essential to analyze QoS attributes in terms of data variance. Then computing most likely hidden states and observation sequence using HMM, these categories can be linked with certain hidden states inside a WS. For instance, if observations for weather forecasting WS (as shown in table II), produced by finite number of hidden states (as shown in table III), then HMM can help us to establish a probabilistic relation between hidden states and consequent sequence of observations. There are two fundamental assumptions in our approach:  Consequent observations are linked with execution pattern of hidden states with in a remote web service. This linkage can give us probability of possible scenarios used in implementation of WS. "Execution pattern" defines situation where sometime more than one hidden state is producing similar observations. It is important to analyze relevant hidden states along with other QoS attributes such as response time and throughput, which will further help us to predict probability of scalability of hidden states in future.



States responsible for generating data are hidden and unknown. The HMM have been successfully used in pattern recognition applications [START_REF] Salfner | Predicting Failures with Hidden Markov Models[END_REF]. The first assumption is based on the fact that every hidden state has some special functionality linked with it. For instance, sometimes it is required to connect with database to verify certain results or call another web service or performing heavy calculations etc. Based on the execution of a certain hidden state the system may lead to a similar pattern of data output. As per first assumption these states can be identified by recognizing execution pattern. Whereas the second assumption perfectly matches with definition of HMM, as these states are hidden and produce results in time t. Furthermore, any hidden state can generate results when invoked during WS execution or access from other hidden states during error propagation, so model is of ergodic type. Based on these assumptions we have used HMM to find insight details of remote web service. Estimating QoS attribute of WS in terms of data variance requires analyzing response time, throughput and quality of result produced. Response time represents duration which a web service is taking in executing some operation excluding network latency and communication delay. Throughput is the amount of work done by the web service within specified period of time. It is possible for certain hidden states to produce similar observations despite of having different implementation. Thus for a given time interval during various service invocations we can define feature vector including values defined in table III and by considering WS description to predict probability of implementation of hidden states. Because of difference in implementation of hidden states clear identification among feature values is required which in machine learning is referred to as Feature Normalization [START_REF] Hoecke | Modeling the performance of the Web service platform using Layered Queueing Networks[END_REF]. These features may be categorized in terms of data mapping, server clustering, mutated coding, calling other web services. This will help to define initial transition and emission probabilities of hidden states. Fig. 2 shows general implementation of a web service with different observation sym-Fig. 2. Mappy variance in generating results to hidden markov model Fig. 3: Training sequence bols dependent on hidden states. In our framework, status(s) (as defined in table II) can be further divided into sub categories such as sunny, rainy, partially cloudy, and mostly cloudy. At the time user receives inconsistent data set underlying hidden state transits to an unreliable state, labeled as Surel . Any state defined in Table III can be transit to an unreliable state. By initializing HMM parameters it can be ensured that the model transits to unreliable state once inconsistent data occurs in the training sequence. Emission probabilities are represented by relevant hidden state and output value. For instance, probability of output value "Mostly Cloudy" from hidden state "mutated coding" is represented by b_m(M). Here b represents observation probability matrix, m shows "mutated coding and M represents output value "Mostly Cloudy". So we can define various parameters of HMM as:  States: S number of states where each state will have unique output dependent on its functionality (Fig. 2).



Here δ t (i) represents the state of WS i.e. it represent maximum probability (computing maximum over all possible hidden states sequences) that the model went through hidden states HS1, HS2 ,…, HSn-1 and the system is in state i at hidden state n. i.e. HSn= i while observing O1, O2,..., On. To detect data quality one has to define valid data values for each data element collected so that the system would know what we are measuring against. In our framework, we are concerned only with data variance so we counted them where independent variables had differences in values when invoked by same input parameters by multiple threads (as shown in Fig. 1). The data with maximum count i.e. received by most of the users in parallel invocation is considered to be reliable. Later we linked each of the counted value with corresponding hidden state using Eq.2. Now if we define criteria for valid data values then it can be analyzed that which particular state is not producing data as required. However in this paper, we are dealing only with data variance and this can be computed by verifying data values of all independent variables available in the data as defined in Section III-A using relation below:

Rel (D) = 1 - 0 i n ( i V / k D ) (3)
Here Vi represents the number of independent variable (as mentioned in table-1) in data Dk produced during time interval k. The eq.3 can be used recursively to find data variance in whole data D. The Rel(D) will be considered as unreliable, provided one or more independent variable in eq.3 will have invalid value. The probability Purel(sk) is calculated by "First Passage Time Distribution". Let Tk be the time (known as First Passage Time) when hidden state sk produces data Dsk then:

k T = MIN (Rel (Dsk): Sk = Surel) (4)
Where S urel represents the unreliable state, which implies hidden state Sk has produced unreliable data Dsk during time interval k. Probability distribution among hidden states can be computed as below:

urel P ( k S ) =  0 i n P ( k T  n | j S = i) P ( j S = i) s. t. j=0 (5)
Where P (Sj= i) is the probability that WS is in hidden state j at current time as computed in eq.2, and P (T k <= n | Sj = i) is the probability of going through hidden state S urel and computing data reliability during kth time interval starting from j=0 which can be recursively computed with the help of the Baum-Welch algorithm [START_REF] Ramage | Hidden Markov Models Fundamentals[END_REF]. The eq.5 represents probability distribution that the system produces unreliable results S urel during nth time interval at time k which can be further scrutinized using dynamic programming to efficiently compute for various time intervals.

Training the Model

To train the model we have used observation sequences obtained during real web services invocations as described in similarity analysis section i.e. Section 3.1. These sequences are first labeled as "unreliable" using Eq.3, where at least one observation symbol i.e. independent variable has inconsistent value. In our framework such res-ponses are modeled and represented by hidden state S urel as shown in Fig. 2. Whenever data with uncertain results is obtained, underlying state transits to unreliable state, i.e. S urel. The hidden state S urel can be any state which is defined in Table III. Observation sequence having uncertain values is shown in Fig. 1 (b, c andd) where occurrence of uncertainty is indicated by difference in values. Training sequences from this information can be obtained by defining "R" for reliable and "UR" for unreliable value in observation sequence using the strategy defined in Section 3.4 as shown in Fig. 3. Each column in Fig. 3 represents the data consistency of the WS invocations. Each row in Fig. 3 represents responses of single service invoked by 500 parallel threads; however, for proof of concept we have shown only a few values. Then by initializing HMM parameters in Eq.1 i.e. initial, transition and emission probabilities, such that states representing as unreliable S urel are the only states that produce results with "UR", it can be ensured that model transits to unreliable state when uncertainty appears in the training sequence.

Experiments and Results

Based on domain information about implementation complexity of various computing techniques as described in table 1, initial guesses for probabilities can be exploited to:

 Adjust model parameters and determine current state of the system. Find the relation among output value and hidden states  Predict QoS attributes of various hidden states using training sequences based on real data for various web services having similar functionality and select the WS with better QoS attribute. In our experiment we have selected two web services with higher rank as mentioned in table-2 and invoked them using 500 parallel threads in a distributed environment. Fig. 4b and Fig. 5b represent data variance of independent variables Wind and Status (sunny, rain, cloudy, partially cloudy) respectively, as defined in table-1. Purpose of this experiment was to use our proposed model for analyzing their QoS attribute in terms of variance of data for selecting better web services and to predict their QoS values for anytime in the future.

Adjusting the Model Parameters

To predict the QoS attribute of hidden states, it is necessary to train the model to get estimated transition and emission probabilities. These values are then used in eq.

Current State

The state of component web service during time interval t is a vector of probabilities that system is in the hidden state HSi when observation Oi is observed. VITERBI algorithm is used to calculate the most probable hidden state sequence (as discussed in section 3.3) that has generated the training sequence as shown in Fig. 4 & Fig. 5. Fig. 4d and Fig. 5d represent the current state of various hidden states of two web services W1 and W2 respectively. It can be analyzed that both web services produce variance in data because of inconsistent behavior of hidden states 1 and 2. Although these services are ranked as best by service users, even though both the services are producing over 50% data variance when invoked in parallel with same input parameters at the same time. To select better WS we further elucidated received results in more detail i.e. which particular hidden state of both web services is producing relatively better result. For instance, State1 of WS2 in Fig. 5d shows that it has produced 44% of successful results whereas State1 of WS1 in Fig. 4d indicates that it has produced 30% of overall successful result. This implies that if we can analyze or predict QoS attribute of each hidden state during the nth time interval, then we can select a better WS among the list of functionally equivalent web services.

Predicting Data Variance in Terms of Hidden States

As HMM is normally used to recognize patterns, therefore to predict behavior of the hidden states, idea is to classify suspicious data patterns i.e. patterns with observation symbols "UR". This classification will indicate upcoming suspicious patterns. As per proposed technique, data values in a training sequence are divided into equal lengths slots. These slots having observations symbol "UR" are termed as "unreliable". First the model is trained using training sequences. Then based on trained HMM current status of the hidden state"s behavior is analyzed using VITERBI algorithm. Later, based on current state, future behavior of hidden states is predicted by calculat-ing "first passage time distribution" into unreliable state. Fig. 4 (f andh) and Fig. 5 (f andh) represent the predicted and actual state of hidden states of web services WS1 and WS2 respectively. It can be observed from the predicted value of WS1 in Fig. 4f that only State1 and State3 will produce consistent results during time interval t. Nonetheless, State2 and State4 will produce inconsistent results. These predictions will help end users to design their system in a way that can entertain responses produced by only State1 and State3. Fig. 4h shows actual values of the same web services W1 during time interval t. It can be seen that predicted values are almost similar to actual values except some consistent values which were also produced by State4. However, this is a small number which can be ignored to make the system reliable. Whereas, Fig. 5f and h shows predicted and actual values of web service WS2 responses during time interval t. Predicted and actual values are almost similar in numbers except a marginal difference which can be ignored, however, in this case State2 and State4 have inconsistent behavior. Both the states are randomly generating consistent and inconsistent results which are hard to ignore during the live execution of the system. Therefore, it will be easy for end users to decide which particular web service can incorporated in the system. Such as in this case study WS1 appears to be more suitable compared to WS2. With these results it is apparent that HMM can predict probabilistic QoS attributes of remote WS in terms of data variance, for any time interval in the future. Our model can be used to further analyze probabilistic scalability of various hidden states under specified circumstances such as by increasing user load or increasing communication delay.

Conclusion

In this paper we have explained with experiments how HMM can be used to analyze and predict QoS attribute of a web services in terms of data discrepancy. Predicting QoS attributes will then help end users to select a better web service among the list of functionally equivalent web services. We have performed our experiments on real world web services. Later, we have analyzed in detail the behavior of web services for a different set of users having similar input parameters. Our framework gives information about the probabilistic insight of any remote web service. It can further predict QoS attribute of these hidden states in terms of data variance and can help to further examine scalability of these hidden states.

Fig. 1 .

 1 Fig. 1. Variance in result when WS invoked by more than 500 parallel threads.

Fig. 4 :

 4 Fig. 4: QoS attribute of Web services (WS1)

Fig. 5 :

 5 Fig. 5: QoS attribute of Web service (WS2)

Table 1

 1 Web services with similar functionality along with their Ranks

	Web Services	Count
	Total web services with similar functionality(Weather forecasting)	23
	Available	11
	Broken link	8
	Resource Cannot be found	3
	Security exception	1
	With HMM QoS attribute of WS in terms of data can be analyzed in two stages.
	 Stage one will require us finding relations among hidden states in a remote WS
	and different data categories produced by web services.
	 The second stage requires us to use this information to find probability of re-
	sult produced by hidden states in future.

Table 2 .

 2 Independent Variables

Table 3 .

 3 Common Hidden States

	#	Independent variables
	1.	Status (S)
	2.

  Ai,j represents transitional probability of hidden state Si following Sj.  Bi,jrepresents probability of hidden state generating output being produced from state Sj.  Initial state distribution  States as defined in table III may exist in one web service or there may have at least one or more states available. As per definition of HMM we have: State of WS during time interval t producing data D can be considered as vector of probabilities that WS is in hidden state Si during time interval having observations o={O1, O2,..., On}. Current state of WS can lead us to predict Purel (sk) of WS during kth time interval under various operational conditions. Where Purel (sk) is the probability of state sk that the Markov process defined by Hidden states produces data dk during time interval k is unreliable. Current state of WS during time interval t can be computed with the help of HMM i.e using VITERBI algorithm:

							λ = (A, B,)	(1)
	3.3	Data Quality Prediction
		)  = (i t	1 HS	,	HS	,..., HS Max 2	n		1	P (HS1, HS2,…, HSn-1, HSn = i , O1, O2,..., On |  )

Observations: Distinct output observations V i.e. categories defined in table I, such that output observation at time t is O t where sequence of observation is O= O1, O2,..., Ot 

  2 to compute most probable hidden state sequences. Purpose of training the model is to find the optimal HMM parameters i.e. A, B & π such that the model best fits the training sequences. Baum-Welch algorithm a particular case of expectation-maximization (EM) is used to train the model. It iteratively improves the basic model which provides convergence to local optima. After training the model, current and future state is predicted using VITERBI algorithm as discussed above. b. # of records for each independent variable d. # of records emitted by each hidden state f. Predicted records emitted by each hidden state h. Actual records emitted by each hidden state

Acknowledgment:

I am extremely grateful to Cesar Roberto de Souza (Federal University of Sao Carlos) and for his support, encouragement & proofreading of the draft version of my paper.