We introduce a new geometric robot-routing problem which arises in data-muling applications where a mobile robot is charged with collecting data from stationary sensors. The objective is to compute the robot’s trajectory and download sequence so as to minimize the time to collect data from all of the sensors. The total data collection time has two components:the robot’s travel time and the download time. The time to download data from a sensor s is a function of the location of the robot and s: if the robot is a distance rin away from s, it can download the sensor’s data in Tin units of time. If the distance is greater than rin but less than rout, the download time is Tout > Tin. Otherwise, the robot can not download the data from s. Here, rin, rout, Tin and Tout are input parameters. We refer to this model, which is based on recently developed experimental models for sensor network deployments, as the two-ring model, and the problem of downloading data from a given set of sensors in minimum amount of time under this model as the two-ring tour (TRT) problem.
We present approximation algorithms for the general case which uses solutions to the traveling salesperson with neighborhoods (TSPN) Problem as subroutines. We also present effcient solutions to special, but practically important versions of the problem such as grid-based and sparse deployments. The approach is validated in outdoor experiments.
AkkayaKYounisM (2005) A survey on routing protocols for wireless sensor networks. Ad Hoc Networks3(3): 325–349.
2.
AnastasiGContiMDi FrancescoM (2008) Data collection in sensor networks with data mules: An integrated simulation analysis. In: IEEE symposium on computers and communications, Marrakech, Morocco, 6–9 July 2008, pp. 1096–1102. Washington DC: IEEE Computer Society.
3.
AnastasiGContiMMonaldiEPassarellaA (2007) An adaptive data-transfer protocol for sensor networks with data mules. In: IEEE international symposium on a world of wireless, mobile and multimedia networks, Helsinki, Finland, 18–21 June 2007, pp. 1–8. Washington DC: IEEE Computer Society.
4.
ArkinEMHassinR (1995) Approximation algorithms for the geometric covering salesman problem. Discrete Applied Mathematics55: 197–218.
5.
AroraS (1998) Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the Association for Computing Machinery45(5): 753–782.
6.
BeaufourALeopoldMBonnetP (2002) Smart-tag based data dissemination. In: 1st ACM international workshop on wireless sensor networks and applications, Atlanta, USA, 28 September 2002, pp. 68–77. New York: ACM.
7.
BhadauriaDTekdasOIslerV (2011) Robotic data mules for collecting data over sparse sensor fields. Journal of Field Robotics28(3): 388–404.
8.
BölöniLTurgutD (2008) Should I send now or send later? A decision-theoretic approach to transmission scheduling in sensor networks with mobile sinks. Wireless Communications and Mobile Computing8(3): 385–403.
9.
ChakrabartiASabharwalAAazhangB (2003) Using predictable observer mobility for power efficient design of sensor networks. In: 2nd international conference on information processing in sensor networks, Palo Alto, USA, 22–23 April 2003, pp. 129–145. Berlin: Springer-Verlag.
10.
ChenYTerzisA (2009) On the spatial characteristics of the gray region for 802.15.4 radios. In: international conference on information processing in sensor networks, San Francisco, USA, 13–16 April 2009, pp. 393–394. New York: ACM.
11.
ChristofidesN (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Carnegie Mellon University,USA.
12.
DiggaviSGrossglauserMTseD (2002) Even one-dimensional mobility increases ad hoc wireless capacity. In: IEEE international symposium on information theory Lausanne, Switzerland, 30 June – 5 July 2002, p. 352. Washington DC: IEEE Computer Society.
13.
DumitrescuAMitchellJSB (2003) Approximation algorithms for TSP with neighborhoods in the plane. Journal of Algorithms48(1): 135–159.
14.
DunbabinMCorkePVasilescuIRusD (2006) Data muling over underwater wireless sensor networks using an autonomous underwater vehicle. In: IEEE international conference on robotics and automation, Orlando, USA, 15–19 May 2006, pp. 2091–2098. Washington DC: IEEE Computer Society.
15.
EkiciEGuYBozdagD (2006) Mobility-based communication in wireless sensor networks. IEEE Communications Magazine44(7): 56.
16.
ElbassioniKFishkinAVSittersR (2006) On approximating the TSP with intersecting neighborhoods. In: 17th annual international symposium on algorithms and computation, Kolkata, India, 18–20 December 2006, pp. 213–222. Berlin: Springer-Verlag.
17.
GuYBozdagDEkiciEOzgunerFLeeC (2005) Partitioning based mobile element scheduling in wireless sensor networks. In: 2nd annual IEEE communications society conference on sensor and ad hoc communications and networks, Santa Clara, USA, 26–29 September 2005, pp. 386–395. Washington DC: IEEE Computer Society.
18.
JeaDSomasundaraASrivastavaM (2005) Multiple controlled mobile elements (data mules) for data collection in sensor networks. In: international conference on distributed computing in sensor systems, Marina del Rey, USA, June 30 – July 1 2005, pp. 244–257. New York: Springer.
19.
JuangPOkiHWangYMartonosiMPehLRubensteinD (2002) Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet. Operating Systems Review36(5): 96–107.
20.
KansalASomasundaraAAJeaDDSrivastavaMBEstrinD (2004) Intelligent fluid infrastructure for embedded networks. In: international conference on mobile systems, applications, and services, Boston, USA, 6–9 June 2004, pp. 111–124. New York: ACM.
21.
LuoJHubauxJP (2005) Joint mobility and routing for lifetime elongation in wireless sensor networks. In: 24th annual joint conference of the IEEE computer and communications societies, Miami, USA, 13–17 March 2005, pp. 1735–1746. Washington DC: IEEE Computer Society.
22.
MeguerdichianSKoushanfarFPotkonjakMSrivastavaMB (2001) Coverage problems in wireless ad-hoc sensor networks. In: 20th annual joint conference of the IEEE computer and communications societies, Anchorage, Alaska, 22–26 April 2001, pp. 1380–1387. Washington DC: IEEE Computer Society.
23.
MitchellJSB (2011) Personal communication.
24.
MitchellJSB (1999) Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, -MST, and related problems. SIAM Journal on Computing28(4): 1298–1309.
25.
MitchellJSB (2007) A PTAS for TSP with neighborhoods among fat regions in the plane. In: 18th annual ACM-SIAM symposium on discrete algorithms, New Orleans, USA, 7–9 January 2007, pp. 11–18. New York: ACM.
ShahRRoySJainSBrunetteW (2003) Data MULEs: modeling and analysis of a three-tier architecture for sparse sensor networks. Ad Hoc Networks1(2–3): 215–233.
28.
SugiharaRGuptaR (2009) Optimal speed control of mobile node for data collection in sensor networks. IEEE Transactions on Mobile Computing9(1): 127–139.
29.
TekdasOLimJTerzisAIslerV (2008) Using mobile robots to harvest data from sensor fields. IEEE Wireless Communications16(1): 22–28.
30.
TirtaYLiZLuYHBagchiS (2004) Efficient collection of sensor data in remote fields using mobile collectors. In: international conference on computer communications and networks, Chicago, USA, 11–13 October 2004, pp. 515–519. Washington DC: IEEE Computer Society.
31.
WangWSrinivasanVChuaK (2005) Using mobile relays to prolong the lifetime of wireless sensor networks. In: 11th annual international conference on mobile computing and networking, Cologne, Germany, 28 August – 2 September 2005, p. 283. New York: ACM.
32.
WuFHuangCTsengY (2009) Data gathering by mobile mules in a spatially separated wireless sensor network. In: international conference on mobile data management: systems, services and middleware, Taipei, Taiwan, 18–20 May 2009, pp. 293–298. Washington DC: IEEE Computer Society.
33.
XingJWangHHanKRayDHuangCChemnickLStewartCDisotellTRyderOBatzerM (2005) A mobile element based phylogeny of old world monkeys. Molecular Phylogenetics and Evolution37(3): 872–880.
34.
YuanBOrlowskaMSadiqS (2007) On the optimal robot routing problem in wireless sensor networks. IEEE Transactions on Knowledge and Data Engineering19(9): 1252–1261.
35.
ZhaoJGovindanR (2003) Understanding packet delivery performance in dense wireless sensor networks. In: 1st international conference on embedded networked sensor systems, Los Angeles, USA, 5–7 November 2003, pp. 1–13. New York: ACM.
36.
ZhaoWAmmarMZeguraE (2004) A message ferrying approach for data delivery in sparse mobile ad hoc networks. In: 5th ACM international symposium on mobile ad hoc networking and computing, Tokyo, Japan, 24–26 May 2004, pp. 187–198. New York: ACM.
