Improved Algorithms for Data-Gathering Time in Sensor Networks II: Ring, Tree, and Grid Topologies

References

• Argy , J. R. , Clare , L. P. , Potty , G. J. and Romanov , N. P. 1999 . Development platform for self-organizing wireless sensor networks . Proceedings of SPIE, Unattended Ground Sensor Technologies and Applications , 3713 : 257 – 268 .
   Google Scholar
• Estrin , D. , Girod , L. , Pottie , G. and Srivastava , M. May 2001 . “ Instrumenting the world with wireless sensor networks ” . In Proceedings of ICASSP 2001 May , Salt Lake City, Utah
   Google Scholar
• Centintemel , U. , Filinders , A. and Sun , Y. September 19 2003 . “ Power-efficent data dissemination in wireless sensor networks ” . In MobiDE’ 03 September 19 , San Diego, California
   Google Scholar
• Revah , Y. and Segal , M. 2008 . Improved algorithm for data-gathering time in sensor networks,” accepted to Elsevier . Computer Commuications ,
   Google Scholar
• Sen , A. and Huson , M. 1997 . A new model for scheduling radio packet networks . Wireless Networks , 3 : 77 – 82 .
   Google Scholar
• Hammond , J. and Russell , H. 2004 . Properties of a transmission assignment algorithm for multiple-hop packet radio networks . IEEE Transactions Wireless Communications , 3 ( 4 ) : 1048 – 1052 .
   Google Scholar
• Rhee , I. and Lee , J. Distributed scalable TDMA scheduling algorithm . NCSU Tech. Rep. 2004-4-14 . Department of Computer Science, North Carolina State University
   Google Scholar
• Chou , A. and Li , V. 1991 . Fair spatial TDMA channel access protocols for multihop radio networks . Proc. IEEE INFOCOM , : 1064 – 1073 .
   Google Scholar
• Ramanathan , S. 1999 . A unified framework and algorithm for channel assignment in wireless Networks . Wireless Networks , vol 5 : 81 – 94 .
   Google Scholar
• Wang , G. and Ansari , N. 1997 . Optimal broadcast scheduling in packet radio networks using mean field annealing . IEEE Journal on Selected Areas in Communications , 15 ( 2 ) : 250 – 260 .
   Google Scholar
• Ma , X. and Lloyd , E. 1998 . An incremental algorithm for broadcast scheduling in packet radio networks . Proc. IEEE MILCOM ,
   Google Scholar
• Ma , X. and Lloyd , E. 1998 . A distributed protocol for adaptive broadcast scheduling in packet radio networks . Proc. ACM/IEEE DIALM for Mobility ,
   Google Scholar
• Chlamtac , I. and Farago , A. 1994 . Making transmission schedules immune to topology changes in multi-hop packet radio networks . IEEE/ACM Transactions on Networking , 2 ( 1 ) : 23 – 29 .
   Google Scholar
• Chlamtac , I. and Kutten , S. 1985 . A spatial reuse TDMA/FDMA for mobile multi-hop radio networks . Proc. IEEE INFOCOM , 1 : 389 – 394 .
   Google Scholar
• Ali , F. , Appani , P. , Hammond , J. , Mehta , V. , Noneaker , D. and Russel , H. 2002 . Distributed and adaptive TDMA algorithms for multi-hop mobile networks . Proc. IEEE MILCOM , : 546 – 551 .
   Google Scholar
• Ephremides , A. and Truong . 1990 . Scheduling broadcast in multihop radio networks . IEEE Transactions on Communications , 38 ( 4 ) : 456 – 460 .
   Google Scholar
• Ma , X. and Lloyd , E. 2001 . Evaluation of a distributed broadcast scheduling protocol for multihop radio networks . Proc. IEEE MILCOM , : 1 – 7 .
   Google Scholar
• Chlamtac , I. and Lerner , A. 1985 . A Link allocation protocol for mobile multi-hop radio networks . Proc. IEEE INFOCOM , : 238 – 242 .
   Google Scholar
• Liu , R. and Lloyd , E. 2001 . A distributed protocol for adaptive link scheduling in ad-hoc networks . Proc. IASTED International Conf. on Wireless and Optical Communications , : 43 – 48 .
   Google Scholar
• Ramanathan , S. and Lloyd , E. 1993 . Scheduling Algorithms for Multihop Radio Networks . IEEE/ACM Transactions on Networking , 1 ( 2 ) : 166 – 177 .
   Google Scholar
• Bao , L. and Aceves , J. J. 1998 . Channel access scheduling in ad-hoc networks with unidirectional links . Proc. ACM/IEEE DIALM for Mobility ,
   Google Scholar
• Busch , C. , Herlihy , M. and Wattenhofer , R. 2000 . Hard-potato routing . Proc. STOC , : 278 – 285 .
   Google Scholar
• Mansour , Y. and Patt-Shamir , B. 1995 . Many to one packet routing on grids . Proc. STOC , : 258 – 267 .
   Google Scholar
• Busch , C. 2004 . O(congestion + dilation) hot-potato routing on leveled networks . Theory of Computing Systems , 37 : 371 – 396 .
   Google Scholar
• Busch , C. , Ismail , M. , Mavronicolas , M. and Wattenhofer , R. 2003 . Greedy O(C+D) hot-potato routing on trees . Tech. Rep. TR, 03–07 , Rensselaer Computer Science Department
   Google Scholar
• Herlery , K. , Pietracaprina , A. and Pucci , G. 2001 . One-to-many routing on the mesh . SPAA , : 31 – 37 .
   Google Scholar
• Busch , C. , Herlihy , M. and Wattenhofer , R. 2000 . Randomized greedy hot-potato routing . Proc. SODA , : 458 – 466 .
   Google Scholar
• Rajasekaran , S. and Tsantilas , T. 1988 . Optimal routing algorithms for mesh-connected processor arrays . VLSI Algorithms and Architectures , : 411 – 422 .
   Google Scholar
• Dolev , S. , Kranakis , E. and Krizanc , D. 1996 . Baked potatoes: deadlock prevention via scheduling . Proc. PODC , : 210 – 219 .
   Google Scholar
• Ben-Dor , A. , Halevi , S. and Schuster , A. 1994 . Greedy hot-potato routing . Proc. PODC , : 225 – 234 .
   Google Scholar
• Mansor , Y. and Shamir , B. P. 1991 . Greedy packet scheduling on shortest paths . Proceeding of 10^th Annual ACM Symposium on Principles of Distributed Computing , : 169 – 175 .
   Google Scholar
• Bansal , R. 2002 . Online algorithm for routing and scheduling on ring networks . Tech Rep. , Denison University
   Google Scholar
• Havill , J. T. 2001 . Online packet routing on linear arrays and rings . Proc. 28^th ICALP , July 8–12 : 773 – 784 .
   Google Scholar
• Alstrup , S. and Holm , J. 1999 . Direct Routing on Trees”’ . Proc. SODA , : 342 – 349 .
   Google Scholar
• Choi , Y. , Gouda , M. G. , Zhang , H. and Arora , A. Routing on a Logical Grid in Sensor Networks . UTCS Tech. Rep. TR-04-49 .
   Google Scholar
• Sridhran , A. and Krishnamachari , B. 2004 . Max-min fair collision-free scheduling for wireless sensor networks . Proc. IEEE on Performance, Computing and Communications , : 585 – 590 .
   Google Scholar
• Franic , C. , Lau , M and Zhang , S.H . 2002 . Fast gossiping in squar meshes/tori with bounded-size packet . IEEE Transaction on Parallel and Distributed Systems , 13 ( 4 ) April
   Google Scholar
• Krumme , D. W. , Cybenko , G. and Venkataraman , K. N. Gossiping in Minimal Time . Tech. Rep. 1027 . August, 1990 . Center for Supercomputing Research and Development
   Google Scholar
• Gronkvist , J. 1998 . Traffic controlled reuse TDMA in multi-hop radio networks . Proc. IEEE PIMRC , : 1203 – 1207 .
   Google Scholar
• Bermond , J. C. , Correa , R. and Minli . 2006 . Gathering algorithms on paths under interference constraints . Proc. CIAC 2006 , : 115 – 126 . LNCS
   Google Scholar
• Bermond , J. C. and Peters , J. 2005 . Efficient gathering in radio grids with interference . Proc. ALGOTEL ,
   Google Scholar
• Bermond , J. C. , Galtier , J. , Klasing , R. , Morales , N. and Perennes , S. 2006 . Gathering in specific radio networks,” To appear . ALGOTEL ,
   Google Scholar
• Bermond , J. C. , Galtier , J. , Klasing , R. , Morales , N. and Perennes , S. 2006 . Hardness and approximation of gathering in static radio networks . Proc. PerCOM ,
   Google Scholar
• Florens , C. and McEliece , R. 2004 . Lower bounds on data collection time in sensory networks . IEEE Journal on Selected Areas in Communications , 22 ( 6 ) : 1110 – 1120 .
   Google Scholar