臺灣博碩士論文加值系統

無線感測網路已成為近年來一門新興的科技，能夠改善並豐富我們的日常生活。無線感測網路是由眾多無線裝置所組成，其中每個裝置皆具有從環境收集資訊、並且互相溝通的能力。在本論文中，我們將探討行動無線感測網路下的佈建、派遣、與封包排程三大議題，其中所謂的行動無線感測網路指的是網路中部份或是全部的節點具有移動的能力。特別來講，佈建的議題主要是探討給予一個佈署區域，如何決定最少數量的感測器以及其佈建位置，使得這個區域內任何一點都可
以被感測器所涵蓋到、且形成的網路具有連結性；派遣的議題則是研究如何有效率安排行動感測器拜訪特定的位置去執行某些任務，使得這些行動感測器所剩有的電量能夠儘量被保存；當網路建構完畢後、或是行動感測器到達目的地時，封包排程的議題則是討論如何管理來至感測器數據的回報，使得重要的即時訊息不會被延遲、且其他非即時訊息的傳輸仍然被保障。

針對佈建的議題，我們首先提出一套通用的佈建方案，而這套方案容許佈署區域的形狀任意、且其中可能包含障礙物；我們所提出的佈建方案亦允許感測器的通訊距離和感測距離可以隨意，而這點是被以前的文獻所忽略的。我們的佈建方案先是根據佈署區域的狀況以及感測器的通訊距離與感測距離之關係來計算放置最少數量的感測器之位，然後我們再派遣感測器去這些位置，其中派遣的方式必需滿足某些特定的電源消耗之目標函數；藉由這個方式，我們的佈建方案將可以改善之前文獻的限制並對佈建之議題研究更加的完善。

在本論文中，我們進一步研究如何佈建一個具有多重涵蓋性的感測網路，而這個多重涵蓋性則是許多無線感測網路的應用或協定所必要的假設。針對這個佈建問題，我們亦提出了一套通用的方案能夠允許任意關係的感測器通訊距離與感測距離；我們所提出的佈建方案可以使用較少的感測器，此外，我們也提出了兩套分散式的感測器派遣方法來協助網路的佈建。

針對派遣的議題，我們提出了一個感測器派遣方法可以有效安排行動感測器拜訪不同的事件發生地點，我們所提出的派遣方法可以允許不同數量的行動感測器以及事件地點，這套派遣方法不但可以均衡行動感測器的移動距離，並且能夠儘量保存它們的電量；藉由這個方式，我們將能在行動感測器有限電量的限制下，儘量延長行動感測器的使用期限。

針對封包排程的議題，我們提出兩套無線封包公平排程演算法：TD-FQ與MR-FQ。TD-FQ在排程封包時考量到資料流的特性，它藉由給予即時性資料流較高的優先權以減緩其延遲時間，然而它仍保障全體資料流傳輸的公平性。MR-FQ則考量一個較複雜的無線傳輸環境，其中感測器可以根據目前傳輸頻道的狀況來調整其傳輸速率；MR-FQ可以根據資料流目前的傳輸頻道狀況以及其滯延程度來調整它的傳輸速率；藉由這個方式，MR-FQ可以同時保障資料流傳輸的公平性以及提升整體的系統效能。

在本論文中，我們亦實作了一套稱為iMouse系統的行動感測器平台，這套系統結合了無線感測網路的環境感知能力以及監控系統，以便取得環境中重要資訊並立即通報人們，因此iMouse系統可以改善傳統視訊監控系統的分析負擔；在本論文中，我們將展示iMouse系統在家庭/辦公室安全使用上的應用。

Wireless sensor networks have become one emerging technology that greatly enrich our life. Such a network consists of many tiny, wireless devices that can gather information from the environment and communicate with each other. In this dissertation, we will study the deployment, dispatch, and packet-scheduling issues of a mobile wireless sensor network, in which some or all nodes in the network have a mobile capability. In particular, the deployment issue discusses how to determine the minimum number of sensors and their locations to be placed in the region of interest so that every point in the region can be covered by sensors and the network is connected. The dispatch issue addresses how to efficiently schedule mobile sensors to reach certain locations to perform some missions so that their energies can be conserved as much as possible. After
the network is constructed or mobile sensors arrive at their
destinations, the packet-scheduling issue considers how to manage the messages reported from sensors so that the delays of important real-time messages can be bounded while other non-real-time messages will not be starved.

For the deployment issue, we first propose a general deployment solution that allows the deployed region to be arbitrary-shaped and possibly contain obstacles. Our solution also allows an arbitrary relationship of sensors' communication distances rc and their sensing distances rs, which is ignored by previous works. Our solution first computes the positions to place the least number of sensors according to the condition of deployed region and the relationship of rc and rs. Then we dispatch sensors to these locations under certain constraints of energy consumptions. In this way, our solution can relax the limitations of previous works and is more complete to the deployment problem.

In this dissertation, we further investigate how to deploy a
sensor network for multi-level coverage, which is an essential assumption required by many applications and protocols in wireless sensor networks. For this deployment problem, we also propose a general solution in which the relationship of rc and rs can be arbitrary. Our solution can use fewer sensors compared with other schemes. In addition, we also propose two distributed dispatch schemes to help deploy sensors.

For the dispatch issue, we propose an efficient dispatch method for mobile sensors to visit event locations in a hybrid sensor network. Our dispatch method is general in which the numbers of event locations and mobile sensors can be arbitrary. Our dispatch method can balance the moving distances of mobile sensors while preserve their energies as much as possible during each round of dispatch. In this way, we can maximize the system time for mobile sensors to perform their missions with their limited energies.

For the packet-scheduling issue, we propose two wireless packet fair scheduling algorithms, Traffic-Dependent wireless Fair Queuing (TD-FQ) and Multi-Rate wireless Fair Queuing (MR-FQ). TD-FQ takes traffic types of flows into account when scheduling packets. It gives a higher priority for real-time flows to alleviate their queuing delays, but still guarantees the fairness among all flows. MR-FQ considers a more complicated multi-rate environment in which sensors can adopt different modulation techniques to transmit their packets under different channel conditions. MR-FQ adjusts a flow's transmission rate according to the flow's channel condition and its lagging degree, so that both fairness and system performance can be taken care of.

In this dissertation, we also implement a mobile sensor platform, called the integrated mobile surveillance and wireless sensor (iMouse) system. The iMouse system integrates the context-aware capability of wireless sensor network into surveillance system so that the real critical information in the environment can be retrieved and
immediately send to users. In this way, the overheads of
traditional visual surveillance systems can be reduced. We
demonstrate the iMouse system with a home/office security scenario in this dissertation.

摘要 i
Abstract iii
誌謝......................................................v
Contents.................................................vi
List of Figures...........................................x
List of Tables...........................................xv
1 Introduction............................................1
1.1 Background andMotivations.............................1
1.2 Contributions of the Dissertation.....................4
1.3 Organization of the Dissertation......................8
2 Preliminaries..........................................10
2.1 Deployment Issue.....................................10
2.1.1 Related Computation Geometric Problems.............10
2.1.2 Placements of Wireless Sensor Networks.............13
2.1.3 Self-deployments with Mobile Sensors...............16
2.2 Dispatch Issue.......................................20
2.3 Packet-scheduling Issue..............................26
2.3.1 Algorithms with Error-free Reference Models........27
2.3.2 Algorithms with Explicit Compensation Mechanisms...29
2.3.3 Algorithms withWeight Adjustment Mechanisms........33
2.3.4 Algorithms that Consider Traffic Types of Flows....34
2.4 Implementations of Mobile Sensor Platforms...........36
3 Deployment of a Wireless Sensor Network for Single-level Coverage.................................................41
3.1 Problem Statement....................................42
3.1.1 The Sensor Placement Problem.......................42
3.1.2 The Sensor Dispatch Problem........................42
3.2 Solutions to the Sensor Placement Problem............44
3.2.1 Partitioning the Sensing Field.....................46
3.2.2 Placing Sensors in Single-row Regions..............47
3.2.3 Placing Sensors in Multi-row Regions...............47
3.2.4 Adapting to the Probabilistic Sensing Model........50
3.3 Solutions to the Sensor Dispatch Problem.............52
3.3.1 A Centralized Dispatch Solution....................53
3.3.2 A Distributed Dispatch Solution....................57
3.4 Experimental Results.................................58
3.4.1 Effectiveness of the Proposed Placement Schemes....58
3.4.2 Evaluations of the Proposed Dispatch Schemes.......59
3.5 Summary..............................................59
4 Deployment of a Wireless Sensor Network for Multi-level Coverage.................................................63
4.1 Problem Statement....................................64
4.2 k-Coverage Sensor Placement Schemes..................65
4.2.1 A Naive Duplicate Scheme...........................65
4.2.2 An Interpolating Placement Scheme..................65
4.3 Distributed Sensor Dispatch Schemes..................68
4.3.1 A Competition-based Dispatch Scheme................69
4.3.2 A Pattern-based Dispatch Scheme....................72
4.4 Experimental Results.................................74
4.4.1 Evaluations of the Proposed Placement Schemes......74
4.4.2 Performances of the Proposed Dispatch Schemes......76
4.4.3 Effect of Seed Locations on the Pattern-based
Scheme...................................................78
4.5 Summary..............................................78
5 Dispatch of Mobile Sensors with Energy-efficient Consideration............................................80
5.1 Problem Statement....................................82
5.2 TheMobile Sensor Dispatch (MSD)Method................84
5.2.1 Case of |S| >= |L|.................................84
5.2.2 Case of |S| < L|...................................88
5.3 Experimental Results.................................89
5.3.1 Performance of theMSDMethod........................90
5.3.2 Effect of the Clustering Scheme....................92
5.3.3 Analysis on the Coefficient α......................93
5.4 Summary..............................................93
6 Packet Scheduling for Data Aggregators in a Wireless Sensor Network...........................................95
6.1 The TD-FQ Algorithm..................................96
6.1.1 SystemModel........................................96
6.1.2 Scheduling Policy..................................97
6.1.3 Gradual Degradation Scheme........................100
6.1.4 Compensation Scheme...............................101
6.1.5 Lag Redistributing Scheme.........................103
6.2 TheMR-FQ Algorithm..................................104
6.2.1 SystemModel.......................................104
6.2.2 Service Fairness vs. Time Fairness................104
6.2.3 Scheduling Policy.................................105
6.2.4 Rate Selection Scheme.............................108
6.2.5 Multi-rate Compensation Scheme....................108
6.3 Theoretical Analyses on Fairness and Delay Bounds...110
6.3.1 Analyses of TD-FQ.................................110
6.3.2 Analyses ofMR-FQ..................................112
6.4 Experimental Results................................114
6.4.1 Performance Evaluation of TD-FQ...................114
6.4.2 Performance Evaluation ofMR-FQ....................117
6.5 Summary.............................................121
7 Implementation of a Mobile Sensor Platform: the iMouse System..................................................122
7.1 Motivation..........................................122
7.2 The System Architecture.............................123
7.3 Design of the iMouse System.........................126
7.3.1 System Operations and Control Flows...............126
7.3.2 Implementation Details and User Interface.........128
7.4 Experimental Results................................131
7.5 Summary.............................................133
8 Conclusions and Future Directions.....................135
8.1 Conclusions.........................................135
8.2 Future Directions...................................137
Appendices..............................................139
A Theoretical Analyses of TD-FQ.........................139
A.1 Fundamental Lemmas..................................139
A.2 Fairness Properties.................................142
A.3 Delay Bounds........................................146
B Theoretical Analyses of MR-FQ.........................151
B.1 Fundamental Lemmas..................................151
B.2 Fairness Properties.................................154
B.3 Delay Bounds........................................159
Bibliography............................................163
Curriculum Vitae........................................174
Publication List........................................176

[1] D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn, "Popular matchings," in ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 424–432.
[2] Acroname, "Garcia robot," http://www.acroname.com/garcia/garcia.html.
[3] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," IEEE Communications Magazine, vol. 40, no. 8, pp. 102–114, 2002.
[4] G. W. Allen, K. Lorincz, M. Welsh, O. Marcillo, J. Johnson, M. Ruiz, and J. Lees, "Deploying a wireless sensor network on an active volcano," IEEE Internet Computing,
vol. 10, no. 2, pp. 18–25, 2006.
[5] J. Aslam, Z. Butler, F. Constantin, V. Crespi, G. Cybenko, and D. Rus, "Tracking a moving object with a binary sensor network," in International Conference on
Embedded Networked Sensor Systems, 2003, pp. 150–161.
[6] F. Aurenhammer, "Voronoi diagrams – a survey of a fundamental geometric data structure," ACM Computing Surveys, vol. 23, no. 3, pp. 345–405, 1991.
[7] D. Avis and G. T. Toussaint, "An optimal algorithm for determining the visibility of a polygon from an edge," IEEE Transactions on Computers, vol. 30, no. 12, pp. 910–914, 1981.
[8] K. Balachandran, S. R. Kadaba, and S. Nanda, "Channel quality estimation and rate adaptation for cellular mobile radio," IEEE Journal on Selected Areas in Communications,
vol. 17, pp. 1244–1256, 1999.
[9] P. Basu and J. Redi, "Movement control algorithms for realization of fault-tolerant ad hoc robot networks," IEEE Network, vol. 18, no. 4, pp. 36–44, 2004.
[10] V. Bharghavan, S. Lu, and T. Nandagopal, "Fair queuing in wireless networks: issues and approaches," IEEE Personal Communications, vol. 6, pp. 44–53, 1999.
[11] M. Blaser, "A new approximation algorithm for the asymmetric TSP with triangle inequality," in ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 638–645.
[12] G. Brasseur, "Robust automotive sensorsy," in IEEE Instrumentation and Measurement Technology Conference (IMTC), vol. 2, 1997, pp. 1278–1283.
[13] N. Bulusu, J. Heidemann, and D. Estrin, "GPS-less low-cost outdoor localization for very small devices," IEEE Personal Communications, vol. 7, no. 5, pp. 28–34, 2000.
[14] Z. Butler and D. Rus, "Controlling mobile sensors for monitoring events with coverage constraints," in IEEE International Conference on Robotics and Automation, 2004, pp. 1568–1573.
[15] Z. Butler and D. Rus, "Event-based motion control for mobile-sensor networks," IEEE Pervasive Computing, vol. 2, no. 4, pp. 34–42, 2003.
[16] Y. Cao and V. O. K. Li, "Scheduling algorithms in broadband wireless networks," in Proceedings of the IEEE, vol. 89, no. 1, 2001, pp. 76–87.
[17] M. Cardei, M. T. Thai, Y. Li, and W. Wu, "Energy-efficient target coverage in wireless sensor networks," in IEEE INFOCOM, 2005, pp. 1976–1984.
[18] L. G. Casado, I. Garcia, P. G. Szabo, and T. Csendes, "Packing equal circles in a square II.—new results for up to 100 circles using the TAMSASS-PECS algorithm," Optimization Theory: Recent Developments from Matrahaza, pp. 207–224, 2001.
[19] K. Chakrabarty, S. S. Iyengar, H. Qi, and E. Cho, "Grid coverage for surveillance and target location in distributed sensor networks," IEEE Transactions on Computers, vol. 51, no. 12, pp. 1448–1453, 2002.
[20] J. H. Chang and L. Tassiulas, "Maximum lifetime routing in wireless sensor networks," IEEE/ACM Transactions on Networking, vol. 12, no. 4, pp. 609–619, 2004.
[21] K. Chintalapudi, T. Fu, J. Paek, N. Kothari, S. Rangwala, J. Caffrey, R. Govindan, E. Johnson, and S. Masri, "Monitoring civil structures with a wireless sensor
network," IEEE Internet Computing, vol. 10, no. 2, pp. 26–34, 2006.
[22] V. Chvatal, "A combinatorial theorem in plane geometry," Journal of Combinatorial Theory, Series B, vol. 18, pp. 39–41, 1975.
[23] T. Clouqueur, K. K. Saluja, and P. Ramanathan, "Fault tolerance in collaborative sensor networks for target detection," IEEE Transactions on Computers, vol. 53,
pp. 320–333, 2004.
[24] Crossbow, "MICA2 Series,"
http://www.xbow.com/Products/productsdetails.aspx?sid=72.
[25] Crossbow, "MICAz ZigBee Series,"
http://www.xbow.com/Products/productsdetails.aspx?sid=101.
[26] Crossbow, "Stargate Gateway,"
http://www.xbow.com/Products/productsdetails.aspx?sid=85.
[27] G. M. Dai, A. H. Du, Q. H. Li, and M. C. Wang, "Planning of moving path based on simplified terrain," in International Conference on Machine Learning and Cybernetics, vol. 3, 2003, pp. 1915–1918.
[28] M. Demirbas, A. Arora, and M. Gouda, "A pursuer-evader game for sensor networks," in Sixth Symposium on Self-Stabilizing Systems, 2003, pp. 1–16.
[29] S. S. Dhillon and K. Chakrabarty, "Sensor placement for effective coverage and surveillance in distributed sensor networks," in IEEE Wireless Communications
and Networking, 2003, pp. 1609–1614.
[30] R. Diestel, "Graph theory," Graduate Texts in Mathematics, 1997.
[31] E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik, vol. 1, pp. 269–271, 1959.
[32] D. Du, F. Hwang, and S. Fortune, "Voronoi diagrams and Delaunay triangulations," Euclidean Geometry and Computers, 1992.
[33] X. Du and F. Lin, "Improving sensor network performance by deploying mobile sensors," in IEEE International Performance, Computing, and Communications
Conference (IPCCC), 2005, pp. 67–71.
[34] T. Dubejko and K. Stephenson, "Circle packing: experiments in discrete analytic function theory," Experimental Mathematics, vol. 4, pp. 307–348, 1995.
[35] S. Dulman, P. Havinga, and J. Hurink, "Wave leader election for wireless sensor networks," in International Symposium on Mobile Muiltimedia Systems & Applications,
2002, pp. 43–50.
[36] D. A. Eckhardt and P. Steenkiste, "Effort-limited fair (ELF) scheduling for wireless networks," in IEEE INFOCOM, 2000, pp. 1097–1106.
[37] Y. Fang, W. E. Dixon, D. M. Dawson, and P. Chawda, "Homography-based visual servo regulation of mobile robots," IEEE Transactions on Systems, Man and Cybernetics, Part B, vol. 35, no. 5, pp. 1041–1050, 2005.
[38] W. C. Feng, E. Kaiser, W. C. Feng, and M. L. Baillif, "Panoptes: scalable lowpower video sensor networking technologies," ACM Transactions on Multimedia
Computing, Communications, and Applications, vol. 1, no. 2, pp. 151–167, 2005.
[39] S. Fisk, "A short proof of Chvatal's watchman theorem," Journal of Combinatorial Theory, Series B, vol. 24, p. 374, 1978.
[40] F. Fodor, "The densest packing of 19 congruent circles in a circle," Geometriae Dedicata, vol. 74, pp. 139–145, 1999.
[41] J. A. George, J. M. George, and B. W. Lamar, "Packing different-sized circles into a rectangular container," European Journal of Operational Research, vol. 84, pp.
693–712, 1995.
[42] M. Goldberg, "Packing of 14, 16, 17 and 20 circles in a circle," Mathematics Magazine, vol. 44, pp. 134–139, 1971.
[43] S. J. Golestani, "A self-clocked fair queueing scheme for broadband applications," in INFOCOM, 1994, pp. 12–16.
[44] P. Goyal, H. M. Vin, and H. Chen, "Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks," IEEE/ACM Transactions on
Networking, vol. 5, no. 5, pp. 690–704, 1997.
[45] R. L. Graham and B. D. Lubachevsky, "Dense packings of equal disks in an equilateral triangle: from 22 to 34 and beyond," The Electronic Journal of Combinatorics, vol. 2, 1995.
[46] R. L. Graham, B. D. Lubachevsky, K. J. Nurmela, and P. R. J. Ostergard, "Dense packings of congruent circles in a circle," Discrete Mathematics, vol. 181, no. 1-3, pp. 139–154, 1998.
[47] C. Gui and P. Mohapatra, "Power conservation and quality of surveillance in target tracking sensor networks," in ACM/IEEE International Conference on Mobile
Computing and Networking, 2004, pp. 129–143.
[48] J. Han and M. Kamber, Data Mining: Concepts and Techniques, D. D. Cerra, Ed. Academic Press, 2001.
[49] T. He, S. Krishnamurthy, J. A. Stankovic, T. Abdelzaher, L. Luo, R. Stoleru, T. Yan, L. Gu, J. Hui, and B. Krogh, "Energy-efficient surveillance system using
wireless sensor networks," in ACM International Conference on Mobile Systems, Applications, and Services (MobiSys), 2004, pp. 270–283.
[50] N. Heo and P. K. Varshney, "Energy-efficient deployment of intelligent mobile sensor networks," IEEE Transactions on Systems, Man and Cybernetics, Part A, vol. 35, no. 1, pp. 78–92, 2005.
[51] A. Heppes and J. B. M. Melissen, "Covering a rectangle with equal circles," Periodica Mathematica Hungarica, vol. 34, no. 1–2, pp. 65–81, 1996.
[52] F. Hoffmann, M. Kaufmann, and K. Kriegel, "The art gallery theorem for polygons with holes," in IEEE Symposium on Foundations of Computer Science, 1991, pp. 39–48.
[53] B. Hofmann-Wellenhof, H. Lichtenegger, and J. Collins, Global Positioning System: Theory and Practice. 4th ed., Springer Verlag, 1997.
[54] G. Holland, N. Vaidya, and P. Bahl, "A rate-adaptive MAC protocol for multi-Hop wireless networks," in ACM Internationl Conference on Mobile Computing and Networking (MobiCom), 2001, pp. 236–251.
[55] A. Hoover and B. D. Olsen, "Sensor network perception for mobile robotics," in IEEE International Conference on Robotics and Automation, 2000, pp. 83–88.
[56] L. Hu and D. Evans, "Localization for mobile sensor networks," in International Conference on Mobile Computing and Networking, 2004, pp. 45–57.
[57] S. Hwang and B. P. Kintigh, "Implementation of an intelligent roving robot using multiple sensors," in IEEE International Conference on Multisensor Fusion and
Integration for Intelligent Systems (MFI), 1994, pp. 763–770.
[58] J. O'Rourke, Art gallery theorems and algorithms. Oxford University Press, Inc., 1987.
[59] M. R. Jeong, H. Morikawa, and T. Aoyama, "Wireless packet scheduler for fair service allocation," in Fifth Asia-Pacific Conference and Fourth Optoelectronics and
Communications Conference, 1999, pp. 794–797.
[60] X. Ji, H. Zha, J. J. Metzner, and G. Kesidis, "Dynamic cluster structure for object detection and tracking in wireless ad-hoc sensor networks," in IEEE International
Conference on Communications, 2004, pp. 3807–3811.
[61] D. Johnson, T. Stack, R. Fish, D. M. Flickinger, L. Stoller, R. Ricci, and J. Lepreau, "Mobile Emulab: a robotic wireless and sensor network testbed," in IEEE
INFOCOM, 2006.
[62] K. Kar and S. Banerjee, "Node placement for connected coverage in sensor networks," in Proceedings of the Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), 2003, pp. 50–52.
[63] L. A. Klein, "A boolean algebra approach to multiple sensor voting fusion," IEEE Transactions on Aerospace and Electronic Systems, vol. 29, no. 2, pp. 317–327, 1993.
[64] H. W. Kuhn, "Hungarian method for the assignment problem," Naval Research Logistics Quarterly, vol. 2, pp. 83–97, 1955.
[65] H. T. Kung and D. Vlah, "Efficient location tracking using sensor networks," in Wireless Communications and Networking, 2003, pp. 1954–1961.
[66] LAN/MAN Standards Committee of the IEEE Computer Society, "IEEE Std 802.15.4-2003, Wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (LR-WPANs)," IEEE,
2003.
[67] B. J. Lee, J. H. Lee, and G. T. Park, "The resource sharing architecture of mobile robots in the home network environment using Jini," in International Symposium
on Robotics, 2001, pp. 233–238.
[68] J. H. Lee and H. Hashimoto, "Controlling mobile robots in distributed intelligent sensor network," IEEE Transaction on Industrial Electronics, vol. 50, no. 5, pp.
890–902, 2003.
[69] S. Lee, K. Kim, and A. Ahmad, "Channel error and handoff compensation scheme for fair queueing algorithms in wireless networks," in IEEE International Conference
on Communications (ICC), 2002, pp. 3128–3132.
[70] C. W. Lin, D. H.Wang, H. C. Wang, and H. D.Wu, "Prototype development of digital spirometer," in International Conference of the IEEE Engineering in Medicine
and Biology Society, vol. 4, 1998, pp. 1786–1788.
[71] F. Y. S. Lin and P. L. Chiu, "A near-optimal sensor placement algorithm to achieve complete coverage/discrimination in sensor networks," IEEE Communications Letters, vol. 9, no. 1, pp. 43–45, 2005.
[72] J. Liu, M. Chu, J. Liu, J. Reich, and F. Zhao, "Distributed state representation for tracking problems in sensor networks," in Information Processing in Sensor Networks, 2004, pp. 234–242.
[73] Y. H. Liu and S. Arimoto, "Finding the shortest path of a disc among polygonal obstacles using a radius-independent graph," IEEE Transactions on Robots and
Automation, vol. 11, pp. 682–691, 1995.
[74] L. Lofdahl, G. Stemme, and B. Johansson, "Turbulence measurements using sensors based on silicon technology," in IEEE International Congress on Instrumentation in Aerospace Simulation Facilities (ICIASF), 1989, pp. 95–103.
[75] S. Lu, V. Bharghavan, and R. Srikant, "Fair scheduling in wireless packet networks," IEEE/ACM Transactions on Networking, vol. 7, no. 4, pp. 473–489, 1999.
[76] S. Lu, T. Nandagopal, and V. Bharghavan, "A wireless fair service algorithm for packet cellular networks," in ACM International Conference on Mobile Computing and Networking (MobiCom), 1998, pp. 10–20.
[77] A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk, and J. Anderson, "Wireless sensor networks for habitat monitoring," in ACM International Workshop on Wireless
Sensor Networks and Applications (WSNA), 2002, pp. 88–97.
[78] V. S. Mansouri, B. Afsari, and H. Shahmansouri, "A simple transport protocol for wireless sensor networks," in IEEE International Conference on Intelligent Sensors,
Sensor Networks and Information Processing (ICC), 2005, pp. 127–131.
[79] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, "Coverage problems in wireless ad-hoc sensor networks," in IEEE INFOCOM, 2001, pp. 1380–1387.
[80] H. Melissen, "Loosest circle coverings of an equilateral triangle," Mathematics Magazine, vol. 70, no. 2, pp. 118–124, 1997.
[81] J. B. M. Melissen, "Densest packing of eleven congruant circles in a circle," Geometriae Dedicata, vol. 50, pp. 15–25, 1994.
[82] J. B. M. Melissen and P. C. Schuur, "Improved coverings of a square with six and eight equal circles," Electronic Journal of Combinatorics, vol. 3, no. 1, 1996.
[83] J. B. M. Melissen and P. C. Schuur, "Packing 16, 17 or 18 circles in an equilateral triangle," Discrete Mathematics, vol. 145, pp. 333–342, 1995.
[84] MINDSTORM, "Robotics Invention System,"
http://mindstorms.lego.com.
[85] A. Nasipuri and K. Li, "A directionality based location discovery scheme for wireless sensor networks," in ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), 2002, pp. 105–111.
[86] T. S. E. Ng, I. Stoica, and H. Zhang, "Packet fair queueing algorithms for wireless networks with location-dependent errors," in IEEE INFOCOM, 1998, pp. 1103–1111.
[87] D. Nicules and B. Nath, "Ad-hoc positioning system (APS) using AoA," in IEEE INFOCOM, 2003, pp. 1734–1743.
[88] D. Niculescu, "Communication paradigms for sensor networks," IEEE Communications Magazine, vol. 43, no. 3, pp. 116–122, 2005.
[89] K. J. Nurmela and P. R. J. Ostergard, "Covering a square with up to 30 equal circles," Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, Research Report A62, June 2000.
[90] J. O'Rourke, "Galleries need fewer mobile guards: A variation on Chv´atal’s theorem," Geometriae Dedicata, vol. 14, no. 3, pp. 273–283, 1983.
[91] Ozgur B. Akan and I. F. Akyildiz, "Event-to-sink reliable transport in wireless sensor networks," IEEE/ACM Transactions on Networking, vol. 13, no. 5, pp. 1003–1016,
2005.
[92] A. K. Parekh and R. G. Gallager, "A generalized processor sharing approach to flow control in integrated services networks: the single-node case," IEEE/ACM Transactions on Networking, vol. 1, no. 3, pp. 344–357, 1993.
[93] G. J. Pottie and W. J. Kaiser, "Wireless integrated network sensors," Communications of the ACM, vol. 43, no. 5, pp. 51–58, 2000.
[94] K. Premaratne, J. Zhang, and M. Dogruel, "Location information-aided taskoriented self-organization of ad-hoc sensor systems," IEEE Sensors Journal, vol. 4, no. 1, pp. 85–95, 2004.
[95] P. Ramanathan and P. Agrawal, "Adapting packet fair queuing algorithms to wireless networks," in ACM International Conference on Mobile Computing and Networking
(MobiCom), 1998, pp. 1–9.
[96] P. Ramanathan and P. Agrawal, "The havana framework for supporting application and channel dependent QoS in wireless networks," in IEEE International Conference on Network Protocols (ICNP), 1999, pp. 235–244.
[97] D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis, "An analysis of several heuristics for the traveling salesman problem," SIAM Journal on Computing, vol. 6, no. 3, pp. 563–581, 1977.
[98] I. B. Sachs and D. L. Souvaine, "An efficient algorithm for guard placement in polygons with holes," Discrete & Computational Geometry, vol. 13, pp. 77–109,
1995.
[99] B. Sadeghi, V. Kanodia, A. Sabharwal, and E. Knightly, "Opportunistic media access for multirate ad hoc networks," in ACM Internationl Conference on Mobile
Computing and Networking (MobiCom), 2002, pp. 24–35.
[100] A. Savvides, C. C. Han, and M. B. Strivastava, "Dynamic fine-grained localization in ad-hoc networks of sensors," in ACM International Conference on Mobile Computing and Networking (MobiCom), 2001, pp. 166–179.
[101] C. Sharp, S. Schaffert, A. Woo, N. Sastry, C. Karlof, S. Sastry, and D. Culler, "Design and implementation of a sensor network system for vehicle tracking and autonomous interception," in European Workshop on Sensor Networks, 2005, pp. 93–107.
[102] T. C. Shermer, "Recent results in art galleries," Proceedings of the IEEE, vol. 80, no. 9, pp. 1384–1399, 1992.
[103] J. P. Sheu, P. W. Cheng, and K. Y. Hsieh, "Design and implementation of a smart mobile robot," in IEEE International Conference on Wireless And Mobile Computing,
Networking And Communications (WiMob), 2005, pp. 422–429.
[104] E. Shih, S. H. Cho, N. Ickes, R. Min, A. Sinha, A. Wang, and A. Chandrakasan, "Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks," in ACM International Conference on Mobile Computing and Networking (MobiCom), 2001, pp. 272–287.
[105] M. Shreedhar and G. Varghese, "Efficient fair queuing using deficit round-robin," IEEE/ACM Transactions on Networking, vol. 4, no. 3, pp. 375–385, 1996.
[106] S. Slijepcevic and M. Potkonjak, "Power efficient organization of wireless sensor networks," in IEEE International Conference on Communications (ICC), 2001, pp.
11–14.
[107] K. Sohrabi, J. Gao, V. Ailawadhi, and G. J. Pottie, "Protocols for self-organization of a wireless sensor network," IEEE Personal Communications, vol. 7, pp. 16–27, 2000.
[108] K. Stephenson, Introduction to circle packing: the theory of discrete analytic functions. Cambridge University Press, 2004.
[109] L. Stoica, A. Rabbachin, H. O. Repo, T. S. Tiuraniemi, and I. Oppermann, "An ultrawideband system architecture for tag based wireless sensor networks," IEEE
Transactions on Vehicular Technology, vol. 54, no. 5, pp. 1632–1645, 2005.
[110] K. Sugihara, M. Sawai, H. Sano, D. S. Kim, and D. Kim, "Disk packing for the estimation of the size of a wire bundle," Japan Journal of Industrial and Applied Mathmatics, vol. 21, pp. 259–278, 2004.
[111] T. Sun, L. J. Chen, C. C. Han, and M. Gerla, "Reliable sensor networks for planet exploration,” in IEEE International Conference On Networking, Sensing and Control, 2005, pp. 816–821.
[112] P. G. Szabo, T. Csendes, L. G. Casado, and I. Garcia, "Packing equal circles in a square I. — problem setting and bounds for optimal solutions," Optimization
Theory: Recent Developments from M´atrahaza, pp. 191–206, 2001.
[113] R. Szewczyk, E. Osterweil, J. Polastre, M. Hamilton, A. Mainwaring, and D. Estrin, "Habitat monitoring with sensor networks," Communications of the ACM, vol. 47,
no. 6, pp. 34–40, 2004.
[114] D. Tian and N. D. Georganas, "A coverage-preserving node scheduling scheme for large wireless sensor networks," in ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), 2002, pp. 32–41.
[115] T. Ue, S. Sampei, N. Morinaga, and K. Hamaguchi, "Symbol rate and modulation level-controlled adaptive modulation/TDMA/TDD system for high-bit-rate wireless data transmission," IEEE Transactions on Vehicular Technology, vol. 47, pp. 1134–1147, 1998.
[116] M. Valera and S. A. Velastin, "Intelligent distributed surveillance systems: a review," IEE Proceedings – Vision, Image and Signal Processing, vol. 152, no. 2, pp. 192–204, 2005.
[117] A. Verma, H. Sawant, and J. Tan, "Selection and navigation of mobile sensor nodes using a sensor network," in IEEE International Conference on Pervasive Computing
and Communications (PerCom), 2005, pp. 41–50.
[118] G. Wang, G. Cao, and T. L. Porta, "Movement-assisted sensor deployment," in IEEE INFOCOM, 2004, pp. 2469–2479.
[119] G. Wang, G. Cao, T. L. Porta, and W. Zhang, "Sensor relocation in mobile sensor networks," in IEEE INFOCOM, 2005, pp. 2302–2312.
[120] K. C. Wang and Y. L. Chin, "A fair scheduling algorithm with adaptive compensation in wireless networks," in IEEE Global Telecommunications Conference (GLOBECOM), 2001, pp. 3543–3547.
[121] R. Williams, The geometrical foundation of natural structure: a source book of design. Dover, New York, 1979.
[122] A. Woo and D. E. Culler, "A transmission control scheme for media access in sensor networks," in ACM International Conference on Mobile Computing and Networking
(MobiCom), 2001, pp. 221–235.
[123] J. Wu and S. Yang, "SMART: a scan-based movement-assisted sensor deployment method in wireless sensor networks," in IEEE INFOCOM, 2005, pp. 2313–2324.
[124] W. Ye, J. Heidemann, and D. Estrin, "Medium access control with coordinated adaptive sleeping for wireless sensor networks," IEEE/ACM Transactions on Networking,
vol. 12, no. 3, pp. 493–506, 2004.
[125] H. H. Yen, F. Y. S. Lin, and S. P. Lin, "Efficient data-centric routing in wireless sensor networks," in IEEE International Conference on Communications (ICC), vol. 5, 2005, pp. 3025–3029.
[126] Y. Yi, Y. Seok, T. Kwon, Y. Choi, and J. Park, "W2F2Q: packet fair queuing in wireless packet networks," in ACM International Workshop on Wireless Mobile
Multimedia (WOWMOM), 2000, pp. 2–10.
[127] H. Zhang, "Service disciplines for guaranteed performance service in packetswitching networks," Proceedings of the IEEE, vol. 83, pp. 1374–1396, 1995.
[128] H. Zhang and J. C. Hou, "Maintaining sensing coverage and connectivity in large sensor networks," in NSF International Workshop on Theoretical and Algorithmic
Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks, 2004.
[129] W. Zhang and G. Cao, "DCTC: dynamic convoy tree-based collaboration for target tracking in sensor networks," IEEE Transactions on Wireless Communications, vol. 3, no. 5, pp. 1689–1701, 2004.
[130] S. Q. Zheng, J. S. Lim, and S. S. Iyengar, "Finding obstacle-avoiding shortest paths using implicit connection graphs," IEEE Transactions on Computer-Aided Design
of Integrated Circuits and Systems, vol. 15, pp. 103–110, 1996.
[131] S. Zhou, M. Y. Wu, and W. Shu, "Finding optimal placements for mobile sensors: wireless sensor network topology adjustment," in IEEE Circuits and Systems
Symposium on Emerging Technologies: Frontiers of Mobile and Wireless Communication,
2004, pp. 529–532.
[132] Y. Zou and K. Chakrabarty, "Sensor deployment and target localization based on virtual forces," in IEEE INFOCOM, 2003, pp. 1293–1303.
[133] Y. Zou and K. Chakrabarty, "A distributed coverage- and connectivity-centric technique for selecting active nodes in wireless sensor networks," IEEE Transactions on
Computers, vol. 54, pp. 978–991, 2005.