# Introduction any typical applications of wireless sensor networks (WSNs) involve the collection of data obtained by sensor nodes at a pre-defined sink. This is normally achieved by wireless transmission of the data, possibly over several hops (especially in applications where the sensors are deployed in a hostile or hard-to-access environment). In many cases, the wireless communication results in a major energy expenditure that limits the operational lifetime of the network. Even worse, in multi-hop scenarios, the depletion of the sensors' energy sources (such as batteries) is non-uniform, as nodes that are close to the sink are required to forward all the data traffic and are likely to be the first to run out of energy. Once these sensors fail, other nodes can no longer reach the sink, and the network ceases to operate even though ample energy remains at nodes further away from the sink. This common problem occurs largely independently of the communication protocols used in the network. In general, the use of Mobile Elements (MEs) [1], [2], [3] can significantly increases the lifetime of the network. Mobile element roams in the network and collects data from sensors via short range communication, the energy cost of which is considerably lower. Thus, the lifetime of the network increases by avoiding multi-hop communication. The main drawback for this approach is the increased latency of the data collection. Typically, the speed of mobile element can be about 0:1-2 m/s [4], [5], resulting in substantial traveling time for the ME and, correspondingly, delay in gathering the sensors' data. In practice, often the ME tour length is bounded by a predetermined time deadline, either due to timeliness constraints on the sensor data or a limit on the amount of energy available to the ME itself. A possible solution is to employ more than one ME; however, this solution is often impractical due to the high cost of MEs, and may not in fact help at all if some sensors are beyond reach due to ME battery limitations in the first place. To address this problem, several proposals presented a hybrid approach, which combines multihop forwarding with the use of mobile elements. In this approach, mobile element visits subset of the nodes termed as caching points. These caching points stores the data of the nodes that are not included in the tour of the mobile element. Once a mobile element become within the transmission range of a caching point, the caching point transmit its data to the mobile element. By adopting such an approach, the mobile element gather the data of the entire without the need of visiting each node physically. In this direction, we investigate the problem of designing the tours for the mobile elements and the data forwarding trees, with the objective of minimizing the distance between nodes not included in the tour and the tour itself. We propose a heuristicbased solution that creates its solution by partition the network into clusters. The in each cluster a tour will be constructed to satisfy the objective. The results show that our scheme significantly outperforms the best comparable scheme in the literature. The rest of the paper is organized as follows. Section 2 presents the related work in this research area. Section 3 presents the Problem definition. In Section 4, we present the details of our algorithmic solution. Section 5 presents the evaluation. Finally, Section 6 concludes the paper. # II. # Related Work There have been many proposals in recent literature that studied using mobile element(s) to prolong the lifetime of the network. Based on the categorization given in [3], we review three major approaches. In a typical flat-topology network, the nodes around the sink are likely to be the first to die due to having to forward the data traffic from all other sensors. Based on this observation, several proposals [6], [7] have investigated using mobile sink(s) to reduce the energy consumption in the network. By varying the path to the sink(s), the residual energy in the nodes becomes more evenly balanced throughout the network, leading to a higher network's lifetime. However, in order to be effective, this technique requires the sink location (and routes thereto) to change regularly, which places a potentially prohibitive overhead on the nodes due to the frequent re-computation of the routes. Zhao et al [8], [9] investigated the problem of maximizing the overall network utility. Accordingly, they presented two distributed algorithms for data gathering where the mobile sink stays at each anchor point (gathering point) for a period of sojourn time and collects data from nearby sensors via multi-hop communications. They considered the cases where the sojourn time is fixed as well as variable. In the second approach, mobile elements travel across the network and gather each sensors data via single-hop, short-range communication. In this scenario, the problem of computing the ME tours is exactly the Traveling Salesman Problem (TSP) [10], with the possibility of adding additional constraints to capture the limitations of the nodes buffer size. In [11], [12], [13], [14], [15] several heuristics have been proposed to that effect, so that each sensor is visited before its buffer is full. Although this approach substantially reduces the energy consumption by avoiding multi-hop communications, it incurs a high delay when the network area is large, because of the requirement that the MEs physically visit all sensor nodes. Finally, the third approach is a hybrid that combines multihop forwarding with data collection by mobile elements. Our work falls into this category. Some earlier works, e.g. [16], [17], [18], assumed the mobile route to be predetermined and were mainly concerned with the timing of transmissions, aiming to minimize the need for in-network caching by timing the transmissions to coincide with the passing of the tour. In [19], [20], the minimum-energy Rendezvous Planning Problem (RPP) is introduced. This problem deals with determining the set of rendezvous points constructing the ME tour. In RPP, the goal is to minimize the Euclidean distance between the source nodes and the tour. Path finding algorithms based on maxflow computations have been considered by [21]. In that work, the authors use a standard maxflow formulation to represent the sensor network. However the problem they consider is finding a path through anywhere in the network area, which does not need to move from a sensor location to another sensor location. Xu et al [22] also proposed a tour finding algorithm in which nodes away from the caching points send their data to the caching points using multi-hop communication. The main concept of their algorithm is to find a tour that satisfies the transit constraint such that the depth of the routing trees connected to this tour are bounded by pre-determined variable h. this algorithm starts by setting the value of h to 1 and increasing it gradually, until such a tour is found. By bounding the depth of the routing tress, the algorithm aims to reduce the energy consumption due to multi-hop forwarding. However, important factors in determining the lifetime of the network such as structure of routing tress, the energy level of the nodes, and the distribution of the caching points were not mainly considered in this algorithm. Liang et al [23] investigated similar problem where the depth of the routing trees were bounded by pre-determined variable. The problem presented in this work shares some similarities with the Vehicle Routing Problem (VRP) [24]. Given a fleet of vehicles assigned to a depot, VRP deals with determining the fleet routes to deliver goods from a depot to customers while minimizing the vehicles' total travel cost. # III. # Problem Definition We are given an undirected graph G = (V, E), where V is the set of vertices representing the locations of the sensors in the network, and E is the set of edges that represents the communication network topology, i.e. (v i , v j ) ? E if and only if v i and v j are within each others communication range. In addition, we are given k, that represents the number of tours need to be constructed. The complete graph G' = (V, E'), where E' = V × V, represents the possible movements of the mobile elements. Each edge (v i , v j ) ? E' has a length r ij , which represents the time needed by a mobile element to travel between sensor v i and v j . The data of all sensors must be uploaded to a mobile element periodically at least once in L time units, where L is determined from the application requirements and the sensors buffer size. In other words, we assume that each mobile element conducts its tour periodically, with L being a constraint on the maximum tour length. In this paper, for simplicity, we assume that the mobile element travels at constant speed, and that, therefore, the travelling times between sensors (r ij ) correspond directly to their respective Euclidean distances; however, this assumption is not essential to our algorithms and can be easily dropped if necessary. In our problem, we seek to find the k tours, where the length of the tour is bounded by L, such that the number of hops between any node and its caching point is minimized. IV. # TOURS AND FORWARDING TREES The goal of our algorithm is to find the tours for the given k mobile elements such that distance between the nodes not included in the tours and the tours are Year minimized. In this direction, we first partition the network into k partitions. The underling goal for the partitioning processes is to minimize the distance between nodes belong to the same cluster. By adopting such a process, we aim to minimize the distance between the nodes and the tours in each cluster. Once the clusters are constructed, the tour building step works to create a tour in each cluster with the aim of minimizing the total distance of the routing trees. # a) Clustering Step The clustering step attempts to find a given number of clusters such that the sum of hop-distances among nodes belonging to the same cluster is minimized. The clustering process start by selecting a node randomly as a cluster centroid. Once a centroid node is identified it will be added to list termed R. Then, the process works by identifying k-1 cluster centroids, where in each iteration, a node is identify as centroid if it has the maximum total hop-distance to all nodes stored in R. Once all k clusters are identified, each node not chosen Figure 1 : The clustering step a centroid will be assign to its nearest cluster centroid. By adopting such a mechanism, we aim to direct the partitioning to group the nodes into clusters based on their distribution. Figure 1 outlines the process of this step. # b) Caching point identification step Now, in each cluster subset of nodes will be selected as caching points. These caching points will store the other nodes data and will be used to construct the mobile element tour. In each cluster, this process works by first identifying the center node. The center node is defined as the node that has the minimum total hop-distance to all other nodes in the cluster. Then, it works to constructs Minimum Spanning Tree (MST) rooted at the cluster center node. Once this MST is constructed the process proceeds to traverse the constructed tree using BST mechanism. This traversing stops once the total distance of the visited edges reach (L. 2/3). As we will see in the tours constructing step, this condition depends on the employed TSP algorithm. The last step in this process is to identify the visited nodes in the traversing mechanism as caching points. # c) Constructing the tour The tour construction phase uses the nodes identified as caching points in the previous step and can be based on any TSP algorithm or heuristic. We use the Christofides approximation algorithm here, as it is known algorithm with 2/3 approximation factor. # V. # Experimental Evaluation To evaluate the presented algorithm's performance, we conducted an extensive set of experiments using the J-sim simulator [25]. We used the following parameters: (1) The area of the network is 250,000m 2 . (2) The tour length constraint L is set to 0:05 ? s ? T L , where s = 1 m/s is the speed of the mobile element, and T L is the total length of the edges in the minimum spanning tree that connects all nodes, for 500 nodes in the network. (3) The starting value of M is chosen to be 0:5 ? T H , where T H is the number of hops between the farthest nodes in the network. ( 4) The radio parameters are set according to the MICAz data sheet [26], namely: the radio bandwidth is 250 Kbps, the transmission power is 21 mW, the receiving power is 15 mW, and the initial battery power is 10 Joules. For simplicity, we only account for the radio receiving and transmitting energy. We are particularly interested in investigating the performance of the presented algorithm in terms of the lifetime of the network and the total distance of the routing trees. We consider the following deployment scenarios: 1. Uniform density deployment: in this scenario, we assume that the nodes are uniformly deployed in a square area of 500×500m 2 . 2. Variable density deployment: in this scenario, we divide the network into a 10×10 grid of squares, Select the node with the maximum distance as new centroid 6 Add the select node to R 7 Until k centroid is selected 8 assign each node to its nearest centroid 9 identify each centroid and the nodes assigned to it as a cluster where each square is 50×50m 2 . We randomly choose 30 of the squares, and in each one of those we fix the node density to be x times the density in the remaining squares. x is a density parameter, which in most experiments (unless mentioned otherwise) is set to x = 5. We compare our algorithm to a modified version of the FFT algorithm [27], we refer to this version as V-FFT. In the original FFT algorithm, a new node is added to the tour based on benefit function. The benefit value of each node depends on the distance between this node and the currently constructed tour as well as the number of nodes it covers. The number of nodes that are covered by any tour node is controlled by the parameter h ? 1. This parameter refers to the maximum number of hops allowed between any two nodes: a tour node can cover any node at most h hops away. Initially, h = 1 and in each round the value of h is incremented by one until a tour that satisfies the transit constraint is determined. In the modified version of the FFT algorithm (V-FFT), we h to be 0:5 the maximum distance between any two nodes inside any cluster obtained by our heuristic. Then, we start by constructing the first tour. Each selected caching point and the neighbor of this caching points, will be removed from consideration at later stage. This tour will be extended, based on the given cost function, until the constructing tour cannot be extended without violating the transit constraint. Once such a tour is obtained, a new tour will be constructed using the same mechanism. We evaluate the impact of the number of nodes on the lifetime of the network and the total size of the routing trees each algorithm obtains. Figure 2, Figure 3, Figure 5 and Figure 5 show the results for deployment scenarios. In the uniform deployment scenario, we can see that increasing the number of nodes increases the gap between the algorithm performances. In this deployment scenario, since we deal with uniformly deployment scenario, the locality of each cluster obtained by the proposed algorithm is expected to be the same. Such behavior results in creating a relatively linear relationship between network lifetime and the number of node. This can be noticed in the results of the routing trees size experiments. In the V-FFT algorithm, the benefit function takes into account the number of nodes covered by the considered nodes as well as the distance between this node and the current constructed tour. And considering the number of covered-nodes as well as the stochastic behavior of such benefit function are the factor behind the seen performance. In the variable deployment scenario, we can see that increasing the number of nodes results in slightly reducing the gap between the algorithms performances. To understand this behavior, let us discuss the main mechanism behind each algorithm performance. In the proposed algorithm, the obtained clusters is expected to be centralized at the dense grids. This is expected to significantly reduce the lifetime of the network, since in each cluster the tour will be saturated with nodes very closed to each other. This become more obvious while increasing the number of tours. In the V-FFT algorithm, as we mentioned, the benefit function take into consideration the number of neighboring nodes covered by a node as well as the distance between the node and the current constructed tour. In this deployment scenario, considering the number of neighboring nodes during the construction of the tours is expected to improve the V-FFT performance, since it will avoid adding caching node that is very closed to the current constructed tour. These can mainly describe the seen performance. # VI. # Conclusions In this paper, we consider the problem of designing the mobile elements tours such that total size of the routing trees is minimized. In this work, we present an algorithmic solution that create its solution by partitioning the network, then in each clusters, a tour will be constructed based on the distribution of the nodes. An interesting open problem would be to consider application scenarios where the data gathering latency requirements vary in the network. For example, some areas in the network need to send data more frequently than others. In this case the tour length constraints would be different for different areas. ![2013 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XIII Issue XII Version I](image-2.png "©") 2![Path-Constrained Data Gathering Scheme Input: G (topology graph), c (number of clusters to be established) Output: a set of clusters 1 Randomly choose a centroid centers and add it to R 2 Do 3 for all nodes in G 4 calculate the distance to all nodes in R (in terms of hop-distance) 5](image-3.png "2 E") 2![Figure 2 : Network lifetime against the number of nodes, for the uniform density deployment scenario](image-4.png "Figure 2 :") 345![Figure 3 : Network lifetime against the number of nodes, for the variable density deployment scenario](image-5.png "Figure 3 :Figure 4 :Figure 5 :") EPath-Constrained Data Gathering Scheme © 2013 Global Journals Inc. (US) EPath-Constrained Data Gathering Scheme EPath-Constrained Data Gathering Scheme ## Data Collection in Wireless Sensor Networks with Dynamic Deadlines," in Real-Time Systems Symposium, 2004. Proceedings. 25th IEEE International. IEEE Press, 2004, pp. 296-305. * Robotics and Microelectronics: Mobile Robots as Gateways into Wireless Sensor Networks JButler Technology@Intel Magazine 2003 * Making sensor networks practical with robots ALamarca WBrunette DKoizumi MLease SSigurdsson KSikorski DFox GBorriello 2002 Lecture notes in computer science * Mobility-based communication in wireless sensor networks EEkici YGu DBozdag IEEE Communications Magazine 44 7 2006 * Robomote: enabling mobility in sensor networks KDantu MRahimi HShah SBabel ADhariwal GSukhatme Proceedings of the 4th international symposium on Information processing in sensor networks (IPSN) the 4th international symposium on Information processing in sensor networks (IPSN) IEEE Press 2005 * Networked infomechanical systems: a mobile embedded networked sensor platform RPon MBatalin JGordon AKansal DLiu MRahimi LShirachi YYu MHansen WKaiser Others Proceedings of the 4th international symposium on Information processing in sensor networks the 4th international symposium on Information processing in sensor networks IEEE Press 2005 * Energy efficient schemes for wireless sensor networks with multiple mobile base stations SGandham MDawande RPrakash SVenkatesan Proceedings of IEEE Globecom IEEE Globecom IEEE 2003 1 * Exploiting sink mobility for maximizing sensor networks lifetime ZWang SBasagni EMelachrinoudis CPetrioli Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS) the 38th Annual Hawaii International Conference on System Sciences (HICSS) 2005 9 * 10.1109/HICSS.2005.259 * Optimization-Based Distributed Algorithms for Mobile Data Gathering in Wireless Sensor Networks MZhao YYang IEEE Transactions on Mobile Computing 11 10 2012 * Efficient data gathering with mobile collectors and space-division multiple access technique in wireless sensor networks IEEE Transactions on Computers 60 3 2011 * Worst-case analysis of a new heuristic for the traveling salesman problem NChristofides 1976 * Mobile element scheduling with dynamic deadlines ASomasundara ARamamoorthy MSrivastava IEEE transactions on Mobile Computing 6 4 2007 * Mobile Element Scheduling for Efficient ASomasundara ARamamoorthy BSrivastava * Partitioning based mobile element scheduling in wireless sensor networks YGu DBozdag EEkici FOzguner CLee Sensor and Ad Hoc Communications and Networks, 2005. IEEE SECON 2005. 2005 Second Annual IEEE Communications Society Conference on 2005 * Periodic Mobile Multi-Gateway Scheduling KAlmi'ani SSelvadurai AViglas Proceedings of the Ninth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT) the Ninth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT) IEEE 2008 * Data gathering in wireless sensor networks with mobile collectors MMa YYang 2008 IEEE International Symposium on Parallel and Distributed Processing Apr. 2008 * Controllably mobile infrastructure for low energy embedded networks ASomasundara AKansal DJea DEstrin MSrivastava IEEE Transactions on Mobile Computing 5 8 2006 * Data MULEs: Modeling a Three-tier Architecture for Sparse Sensor Networks RShah SRoy SJain WBrunette Proceedings of the First IEEE Workshop on Sensor Network Protocols and Applications the First IEEE Workshop on Sensor Network Protocols and Applications 2003 * Available * Multiple controlled mobile elements (data mules) for data collection in sensor networks DJea ASomasundara MSrivastava Lecture Notes in Computer Science 3560 2005 * Rendezvous planning in wireless sensor networks with mobile elements GXing TWang ZXie WJia IEEE Transactions on Mobile Computing 7 12 Dec. 2008 * Available * Rendezvous design algorithms for wireless sensor networks with a mobile base station GXing TWang WJia MLi Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing (MobiHoc) the 9th ACM international symposium on Mobile ad hoc networking and computing (MobiHoc)New York, NY, USA ACM 2008 * Available * SenCar: An Energy-Efficient Data Gathering Mechanism for Large-Scale Multihop Sensor Networks MMa YYang IEEE Transactions on Parallel and Distributed Systems 18 10 Oct. 2007 * Network Lifetime Maximization in Delay-Tolerant Sensor Networks With a Mobile Sink ZXu WLiang YXu Proceedings of the 8th IEEE International Conference on Distributed Computing in Sensor Systems the 8th IEEE International Conference on Distributed Computing in Sensor Systems 2012 * Network Lifetime Maximization in Sensor Networks with Multiple Mobile Sinks WLiang JLuo Proceedings of the 36 th IEEE Conference on Local Computer Networks (LCN) the 36 th IEEE Conference on Local Computer Networks (LCN) * The Vehicle Routing Problem PToth DVigo Society for Industrial & Applied Mathematics (SIAM) 2001 * J-Sim: A Simulation and emulation environment for wireless sensor networks JHou LKung NLi HZhang WChen HTyan HLim 2006 IEEE Wireless Communications Magazine 13 * Mica: A wireless platform for deeply embedded networks JHill DCuller IEEE micro 22 6 2002 * Network Lifetime Maximization in Delay-Tolerant Sensor Networks With a Mobile Sink ZXu WLiang YXu Proceedings of the 8th IEEE International Conference on Distributed Computing in Sensor Systems the 8th IEEE International Conference on Distributed Computing in Sensor Systems 2012