Transcription
2012 Proceedings IEEE INFOCOMMinimizing Data Collection Latency in WirelessSensor Network with Multiple Mobile ElementsDonghyun Kim , Baraki H. Abay , R.N. Uma , Weili Wu† , Wei Wang‡ , and Alade O. Tokuta Department of Mathematics and Computer Science, North Carolina Central University, Durham, NC 27707, USAE-mail: donghyun.kim@nccu.edu, babay@eagles.nccu.edu, {ruma, atokuta}@nccu.edu† Department of Computer Science, The University of Texas at Dallas, Richardson, Texas 75080, USAE-mail: weiliwu@utdallas.edu‡ Department of Mathematics, Xi’an Jiaotong University, Xi’an, P.R. of China, 710049E-mail: wang weiw@163.comAbstract—This paper considers the problem of computing theoptimal trajectories of multiple mobile elements (e.g. robots,vehicles, etc.) to minimize data collection latency in wirelesssensor networks (WSNs). By relying on slightly different assumption, we define two interesting problems, the k-travelingsalesperson problem with neighborhood (k-TSPN) and the krooted path cover problem with neighborhood (k-PCPN). Sinceboth problems are NP-hard, we propose constant factor approximation algorithms for them. Our simulation results indicate ouralgorithms outperform their alternatives.Index Terms—Approximation algorithm, graph theory, wireless sensor network, mobile elements, traveling salesperson problem with neighborhood, k-rooted tree cover problem.I. I NTRODUCTIONA wireless sensor network (WSN) consists of spatiallydistributed autonomous sensor nodes to cooperatively monitorphysical events or environmental conditions. In most WSNs,each node has a limited energy source, and thus energyefficiency is a crucial issue. Typically, the data producedby a node is sent to a designated data collector called asink via either long-range single-hop or short-range multihop routing path. In wireless communication, the amount ofenergy consumed to send a signal increases super-linearlyproportional to the travel distance of the signal. Therefore, thesingle-hop communication tends to be very energy-exhaustivein WSN. Meanwhile, the multi-hop communication makes thenodes near the sink deplete much faster than the other nodes,which results in shortening the lifetime of the WSN.To address this issue, several mobile element (e.g. robot,vehicles, etc.) based data collection strategies are introducedto WSN [1], [2], [3], [4], [5], [6], [7], [8], in which nosensor node performs multi-hop routing and one or moremobile elements move around the sensor nodes deployed overthe area of interest. Once a mobile element is within thecommunication range of a sensor node, the data accumulatedin the sensor node is forwarded to the mobile element. Incase that the mobile element has a long distance directcommunication channel to a sink, this data can be sent tothe sink immediately. Otherwise, the element must move tosome location to be connected to the sink. Clearly, suchmobile element based strategy alleviates the problem of themulti-hop communication scheme since no node needs to be978-1-4673-0775-8/12/ 31.00 2012 IEEEinvolved in energy-exhaustive multi-hop message forwarding.Furthermore, such method enables us to extract data even froma disconnected WSN. However, while this approach can extendthe lifetime of WSN greatly, it generally suffers from hugedata latency due to the slow speed of the mobile elements.Therefore, it is crucial to make the trajectories of the elementsshorter to minimize the latency.In the target WSN of our research, data is delivered fromeach node to the sink only through the mobile elements. Weassume there are k available mobile elements possibly locatedat different places. We consider following two probable cases:each mobile element is 1) only connected to the sink at theiroriginal position and 2) directly connected to the sink at anylocation. We also assume the speed of the mobile elements isfixed to some constant. In such models, the worst case datalatency is heavily dependent on the length of the trajectoriesof the mobile elements. Such a model has a wide range ofcommercial and military applications [1], [9], [10]. Finally,we assume the neighborhoods of any two nodes may overlapwith each other. Now, we list the contributions of this paper.5041) We propose two versatile problems, the k-traveling salesperson problem with neighborhood (k-TSPN) and the krooted path cover problem with neighborhood (k-PCPN).The common goal of both problems is to find the trajectories of the k mobile elements to collect data from then wireless sensor nodes on 2-D euclidean space suchthat the data collection latency (the length of the longesttrajectory among k trajectories ) is minimized. In detail, k-TSPN assumes each mobile element can transmitdata to the sink only at its original (starting) location,and therefore pursues k-rooted tours.k-PCPN assumes each mobile element is connectedto the sink at any location and thus seeks for k-rootedpaths.The neighborhood area of a node is defined as a circlecentered at the node with a constant radius no smallerthan one unit distance. Any two neighborhood areasmay overlap with each other. In both k-TSPN andk-PCPN, a mobile element collects data from a nodeonly if the neighborhood of the node is visited by
the element.Both problems are NP-hard since their subclasses areNP-hard (see Theorem 3.1 and Theorem 3.3). We wouldlike to emphasize that we assume each mobile elementmay start from different positions unlike [8], in whichall mobile elements are assumed to start from the sameposition.2) We introduce the k-rooted tree cover problem with neighborhood (k-TCPN), whose objective is similar to kPCPN and k-TSPN, but actually is to find k rootedtrees instead of paths (k-PCPN) or tours (k-TSPN). kTCPN is NP-hard since its subclass is NP-hard (seeTheorem 3.2). By Remark 1 and Remark 2, an 1.5αapproximation for k-PCPN and k-TSPN can be obtainedfrom an α-approximation for k-TCPN by utilizing the1.5-approximation of the traveling salesperson problem(TSP) by Christofides [17].3) We propose a constant factor approximation algorithm forthe general minimum spanning tree with neighborhood(GMSTN) problem, whose goal is, given a set of nodes,to find a minimum spanning tree (MST) of a set ofthe uniform circular overlapperable neighborhoods of thenodes. Based on this algorithm, we propose a constantfactor approximation for k-TCPN. As a result, we obtaina constant factor approximation for k-PCPN and k-TSPN.4) Given k roots and n nodes, the goal of the k-rooted treecover problem1 is to find k rooted trees such that theweight of the heaviest tree is minimized [13]. Naturally,any algorithm for this problem can be used to producea feasible solution of the k-TCPN, and thus is useful tosolve k-PCPN and k-TSPN. In simulation, we comparethe outputs of our approximation strategies for k-PCPNand k-TSPN with the k-paths and k-tours computed byutilizing the (4 )-approximation algorithm for thek-rooted tree cover problem [13]. Our simulation results indicate our algorithms outperform these alternativemethods.We claim k-TSPN and k-PCPN versatile since they can beused to model various problems outside wireless networkresearch community. For example, the problem of computingthe trajectories of multiple ground vehicles with video cameras(note that it is sufficient to be in the neighborhood of eachpoint of interest to take a picture) such that the time for theoperator to collect the information of the area of interests canbe minimized can be modeled using k-PCPN if the vehicleshave long range radio communication devices, otherwise usingk-TSPN since the vehicles must return back to their basestation.The rest of this paper is organized as follows. Section IIintroduces related work. In Section III, we introduce severalimportant notations, the definitions of the problems, and theirNP-hardness proofs. Our major contributions which include1 In [13], this problem is referred as the R-rooted tree cover problem. Inthis paper, we will use k instead of R to refer the number of available mobileelements (roots), while R is used to refer the set of k mobile elements.several constant factor approximation algorithms are introduced in Section IV. The simulation results are presented inSection V. Finally, Section VI concludes this paper.II. R ELATED W ORKLargely, existing mobility-assisted data collection strategiesare classified into following three categories [2]: randommobility, predictable mobility, and controlled mobility. DataMobile Ubiquitous LAN Extensions (MULEs) is one of theseminary works in the random mobility class, in which severalmobile nodes move around and collect data from the sensornodes [3]. Eventually, they meet a sink and deliver the data tothe sink. The authors in [4] used a queuing system to model thedata collection process using mobile elements with predictablemobility. In [5], the SenCar, a fully controllable mobile sink,is introduced to collect the data from sensor nodes. The workalso demonstrated the importance of finding a proper trajectoryfor the mobile element to accomplish its job successfully. Notethat our work is in the third category.In the traveling salesperson problem with neighborhood(TSPN), a set of nodes each of which has a uniform circularneighborhood with radius 1 is given and a tour visiting theneighborhood areas of all nodes with minimum total length issought. In [6], [7], the problem of finding the shortest tourof a single mobile element to collect the data from a setof uniform sensor nodes is modeled as TSPN and heuristicalgorithms are proposed. Dumitrescu and Mitchell proposed apolynomial time (π 8)(1 )-approximation algorithm forTSPN with overlappable circular neighborhoods, where is asmall positive constant [11]. In [19], Mitchell also introduceda constant factor approximation algorithm for TSPN withpairwise disjoint arbitrary-shaped connected neighborhoodssatisfying some condition. However, the existing algorithmsfor TSPN cannot be directly applied to our k-TSPN since wemay need to find k 1 tours.The k-traveling salesperson problem (k-TSP) is to find ktours originated from the same spot such that each node isvisited by at least one of the tours and the length of longesttour is minimized. The k-SPLITOUR by Frederickson et al. isthe first constant factor approximation for k-TSP [12]. In [8],k-SPLITOUR is used as a heuristic to find the tours of krobots to collect the data from sensor nodes. Note that ourk-TSPN is a generalization of their problem since in k-TSPN,the initial location of each robot may be different.In the k-rooted tree cover problem, a set of nodes and kroots, which are possibly at different locations, are given,and k rooted trees are sought such that each node is insome tree and the total edge weight of the heaviest tree isminimized. The authors in [13] proposed a polynomial time(4 )-approximation algorithm for this problem. The unrootedversion of the k-rooted tree cover problem is studied in [14],[15]. However, it is conjectured that a solution for the unrootedversion cannot be used for the rooted version [13]. Clearly,the (4 )-approximation algorithm can be used to obtain afeasible solution of our k-TCPN problem since a tree visiting505
the centers of a set of nodes also visits the neighborhoods ofall of the nodes.In the minimum spanning tree with neighborhood (MSTN)problem, a set of nodes each of which has a uniform circularneighborhood is given and an MST of the neighborhood areasof all nodes is sought. The authors of [16] assumed no twoneighborhood areas overlap with each other and proposed a7.4-approximation algorithm, two 3-approximation algorithms,and one polynomial time approximation scheme (PTAS) forMSTN. This algorithm cannot be used for k-TCPN sincethe neighborhoods of nodes may overlap with each otherin k-TCPN and we are interested in k rooted trees of theneighborhoods for some k 1.problem of finding a minimum total length path rooted at theonly root r and visiting all nodes in V . Now, from the k-PCPNSinstance, we construct a directed graph Gs with {r} V asits vertex set by establishing directed edges1) from r to each u V with edge cost Eucdist(r, u),2) from each node u V to r with edge cost 0, and3) from u V to v V with edge cost Eucdist(u, v) forevery possible u, v pair.Clearly, an exact algorithm for the special case of k-PCPN (i.e.k 1 and d 0) would solve the asymmetric TSP in Gs ,a very well-known NP-hard problem, within polynomial time.As a result, the special case of k-PCPN has to be NP-hard,and so does k-PCPN in general.III. N OTATIONS AND P ROBLEM D EFINITIONSIn this paper, V {v1 , v2 , · · · , vn } is the set of n sensornodes and R {r1 , r2 , · · · , rk } is the set of k mobileelements (or roots). For any vi V , N (vi ) is the disk (circularneighborhood area) which is centered at vi and whose radius isd 1. G (V, E) is a graph with a node set V V (G) andan edge (a straightline or a curve segment) set E E(G).PLen(G) (vi ,vj ) E(G) L(vi , vj ), where L(vi , vj ) is thelength of the edge between vi , vj V (G). Eucdist(vi , vj )is the eculidean distance of vi and vj . In this paper, we saytwo disks (or neighborhoods) are “touching” with each otherif their borders are adjacent with each other.Definition 3.1 (k-TSPN): Given a hV, Ri pair, the ktraveling salesperson problem with neighborhood (k-TSPN)is to find a set of k tours U {U1 , U2 , · · · , Uk } suchthat 1) each Ui starts from and ends at ri , 2) for eachvj V , u V (Ui ) for some i such that u is in (or onthe border of) N (vj ) , the neighborhood area of vj , and 3)Cost(U ) max1 i k Len(Ui ) is minimized.Definition 3.2 (k-PCPN): Given a hV, Ri pair, the k-rootedpath cover problem with neighborhood (k-PCPN) is to find aset of k paths P {P1 , P2 , · · · , Pk } such that 1) each Pi isrooted at ri , 2) for each vj V , u V (Pi ) for some i suchthat u is in (or on the border of) N (vj ), and 3) Cost(P ) max1 i k Len(Pi ) is minimized.Definition 3.3 (k-TCPN): Given a hV, Ri pair, the k-rootedtree cover problem with neighborhood (k-TCPN) is to find aset of k trees T {T1 , T2 , · · · , Tk } such that 1) each Ti isrooted at ri , 2) for each vj V , u V (Ti ) for some i suchthat u is in (or on the border of) N (vj ), and 3) Cost(T ) max1 i k Len(Ti ) is minimized.Theorem 3.1: k-TSPN is NP-hard.Proof: This is true since TSPN, which is a special caseof k-TSPN in which k 1, is NP-hard [11], [18].Theorem 3.2: k-TCPN is NP-hard.Proof: Since a special case of k-TCPN is NP-hard inwhich k 1, d 1, and no two different N (vi ) and N (vj )overlaps with each other [16], k-TCPN is NP-hard.Theorem 3.3: k-PCPN is NP-hard.Proof: Consider a special case of k-PCPN in which k is 1and d, the radius of the neighborhood area of each node, goesto zero. Under the restrictions, k-PCPN is equivalent to theIV. M AIN R ESULTSBefore presenting our main results, we would like toemphasize we assume that any pair of neighborhoods mayoverlap with each other. If we assume all neighborhoods arecompletely pairwise-disjoint, constant factor approximationsof k-TCPN, k-TSPN, and k-PCPN can be easily obtained asfollows.1) Given a set V of n nodes and a set R of k roots, applythe (4 )-approximation algorithm for the k-rooted treecover problem in [13]. As a result, we have k-rooted treesTc {T1 , T2 , · · · , Tk } such that each tree Ti is rootedat ri R and each node in V is visited by some tree inTc .2) For each rooted tree Ti Tc , apply the (1 )approximation algorithm for MSTN in [16] to ri andV (Ti ). As a result, we obtain a tree Ti0 spanning overri and the neighborhoods of all nodes in Ti .3) Convert each Ti0 into a tour or a path using the famous1.5-approximation for TSP by Christofides [17]. (SeeRemark 1 and Remark 2 for details).One can easily see the performance ratio of this strategy isroughly 4 · 1 4 for k-TCPN and 4 · 1 · 1.5 6 for kTSPN and k-PCPN. However, it is not practical to assumethat the neighborhood areas are always pairwise-disjoint. Thisis because many applications of WSN consider scenarios, inwhich a number of sensor nodes are randomly deployed. Ifsome pairs of neighborhoods overlaps with each other, this approximation strategy cannot be applied since the performanceanalysis in [13], [16] heavily relies on the pairwise-disjointnessof neighborhoods.In [16], the authors studied MSTN where no two neighborhoods overlap with each other. Let us call a variation of MSTNwhere the neighborhood areas of nodes in V may overlap andthe radius of each circular neighborhood is a constant d asthe general MSTN (GMSTN) problem. In Section IV-A, weintroduce GMSTNA, a constant factor approximation of theGMSTN problem. In Section IV-B, we exploit GMSTNA toobtain a constant factor approximation algorithm of k-TCPN,and further optimize this algorithm in Section IV-C. Finally,the constant factor approximations of k-TSPN and k-PCPNare proposed in Section IV-D.506
Algorithm 1 General Minimum Spanning Tree with Neighborhood Algorithm (GMSTNA) (V {v1 , · · · , vn })Let D {N (v1 ), · · · , N (vn )}. We compute I D, theset of maximal independent (pairwise-disjoint) neighborhoods of the nodes in V as follows (also, see Fig 1(a)).(a) Color all disks in D white.(b) Color one white disk N (vi ) black and every white diskN (vj ) which are overlapping (or touching) with N (vi )gray.(c) Repeat Step (c) until there is no white disk left.(d) Add all black disks to I.2: Compute an MST TIcenter of the centers of the disks in I(see Fig 1(b)).3: Let Tout be an empty graph. For each edge (vi , vj ) inTIcenter , add the external segment (type 1 edge) of theedge connecting N (vi ) and N (vj ) as an edge of Tout .Also, for each N (v) I, add the round tour (type 2edge) following N (v) as an edge of Tout . For each pointwhere a type 1 edge and a type 2 edge meet, we add thispoint as a vertex of Tout (see Fig 1(c)).4: Output Tout .vXvYvXvYvXvY1:A. GMSTNA: A Constant Factor Approximation of GMSTNIn this section, we propose a constant factor approximationalgorithm for the GMSTN problem, namely the general minimum spanning tree with neighborhood algorithm (GMSTNA).We would like to emphasize that GMSTN is for computing anMST of the neighborhoods of a set of nodes and there is noconcept of root node. GMSTNA consists of following threemajor steps. In the first step, a set I of the pair-wise disjointneighborhood areas of the nodes in V is identified by usinga 2-coloring strategy. In the second step, an MST TIcenter ofthe center of the disks in I is computed. At this point, TIcenteris spanning over every N (vi ) I, but may not cover someN (vj ) / I. Due to this reason, in the final step, we modifyTIcenter to Tout , which touches the neighborhood area of everynode in V . Algorithm 1 is the description of GMSTNA. Now,we show this is a constant factor approximation of the GMSTNproblem.centerLemma 4.1: Len(Tout ) (d(2π 1) 1)Len(Tmst I) center2πd, where Tmst I is the MST of the centers of the disks in Iin the first step of GMSTNA, Tout is an output of GMSTNA,and d is the radius of the circular neighborhood area (disk) ofeach node.centerProof: We first assume Tmst I 2. Considerthe center vi of a disk N (vi ) in I. Then, vi is concenternected to a set of nodes {w1 , w2 , · · · , wli } in Tmst I(see Fig 2). Let {(vi , w1 ), (vi , w2 ), · · · , (vi , wli )} and{p1 , p2 , · · · , pli } be the set of points where each edge in{(vi , w1 ), (vi , w2 ), · · · , (vi , wli )} intersects with the boundaryof N (vi ). Let {q1 , q2 , · · · , qli } be the points on the middle of each edge in {(vi , w1 ), (vi , w2 ), · · · , (vi , wli )}. Then,centerTmst Ican be partitioned into a set of clusters C(vi ) ofvZvZ(a)vZ(b)(c)Fig. 1. These figures illustrate how GMSTNA works. In Figure (a), a maximalpairwise-disjoint disks, each of which is centered at one of {v1 , v2 , v3 } areselected. In Figure (b), an MST TIcenter of {v1 , v2 , v3 } is computed. InFigure (c), for each N (vi ) in I, the internal segments of
Minimizing Data Collection Latency in Wireless Sensor Network with Multiple Mobile Elements Donghyun Kim , Baraki H. Abay , R.N. Uma , Weili Wuy, Wei Wangz, and Alade O. Tokuta Department of Mathematics and Computer Science, North Carolina Central University, Durham, NC 27707, USA
