摘要
传感器网络在许多领域得到了广泛应用,例如环境监测、战场监测、健康护理等。一个传感器网络有大量的小的传感器节点组成,这些传感器节点由感知、处理和通信模块等组成。一方面,由于传感器节点可能是随机分布的,所以覆盖问题是传感器网络中一个十分重要的课题。传感器网络的覆盖反映了感兴趣的区域或目标的监测效果的好坏。另一方面,节能也是无线传感器网络中一个重要的问题。首先,大部分传感器节点只有有限的电量并且不可充电。其次,由于在很多情况下,环境恶劣或者是人力不可达到的,很难去更换传感器节点的电池。在本论文中,我们主要考虑以下问题。
首先,我们定义并研究了基于目标的有向传感器网络中的寻找一个覆盖集的问题,即有向覆盖集问题(directional cover set problem (DCS))。与传统的具有全向感知能力的全向传感器相比,由于技术的限制以及价格因素的考虑,有向传感器只有有限角度的感知范围。一个有向传感器网络由大量有向传感器节点组成,此类有向传感器可以切换到不同的方向,从而扩展其感知能力以覆盖给定区域内的所有目标。与全向传感器相比,有向传感器的感知角度较小,甚至在布置后不能覆盖任何目标,因此我们需要对网络中的传感器进行调度使之朝向某些方向,从而覆盖所有的目标。DCS问题寻找一个覆盖集,该覆盖集为可以覆盖所有目标的有向传感器的方向的一个子集。我们证明了DCS问题为NP完全问题,提出了两个算法并证明了其正确性。仿真结果表明了这些算法的性能。
其次,我们定义并研究了基于目标的有向传感器网络中的寻找多个可相交覆盖集、且为每个覆盖集分配一段工作时间,从而最大化网络寿命的问题,即多重有向覆盖集问题(multiple directional cover sets problem (MDCS))。在MDCS问题中,我们把网络中传感器的方向组织到可相交的子集中,其中每个子集都是一个覆盖集,并且给每个覆盖集分配一段工作时间。我们轮流在每个时刻只使用一个覆盖集。当我们使用一个覆盖集时,有方向在该覆盖集中的传感器处于活跃状态且工作在该方向上,其他所有的传感器都处于睡眠状态。我们证明了MDCS问题为NP完全问题,并提出了多个算法。通过仿真,我们详尽地比较了这些算法的性能。
最后,我们为基于面积的全向传感器网络提出了一个精确的节能的覆盖控制算法,即基于面积的协作睡眠算法(area-based collaborative sleeping algo-rithm(ACOS))。该算法基于传感器的净覆盖面积,通过精确控制传感器节点的状态,最大化传感器网络的面积覆盖的同时也最小化能量消耗。传感器网络的面积覆盖用被覆盖区域的大小来衡量。一个传感器的净覆盖面积是指只被该传感器覆盖的区域的面积。同时,传感器节点间的协作也被引入该算法中,以平衡节点间的能量消耗。仿真结果表明在唤醒更少节点的情况下,ACOS算法可以提供比其他睡眠算法更好的覆盖。
Sensor networks have emerged as promising platforms for many applications, such asenvironmental monitoring, battlefield surveillance, and health care. A sensor network mayconsist of a large number of small sensor nodes that are composed of sensing, processing andcommunicating components. On one hand, as sensors may be distributed arbitrarily, one ofthe fundamental issues in wireless sensor networks is the coverage problem. The coverageof a sensor network, represents how well the interested region or targets are monitored. Onthe other hand, power conservation is another important issue in wireless sensor networksdue to the following reasons. First, most sensor nodes have limited power sources and arenon-rechargeable. Also, the batteries of the sensor nodes are hard to replace due to hostileor inaccessible environments in many scenarios. In this dissertation, we mainly consider thefollowing problems.
Firstly, we define and solve the problem of finding a cover set, called directional coverset problem (DCS), in target-oriented directional sensor networks. Unlike convectionalomni-directional sensors that always have an omni-angle of sensing range, directional sen-sors may have a limited angle of sensing range due to technical constraints or cost consid-erations. A directional sensor network consists of a number of directional sensors, whichcan switch to several directions to extend their sensing ability to cover all the targets in agiven area. Because a directional sensor has a smaller angle of sensing range than an omni-directional sensor or even does not cover any target when it is deployed, we need to schedulesensors in the network to face to certain directions to cover all the targets. The DCS is tofind a cover set that is a subset of directions of the sensors, in which the directions cover allthe targets. We prove the DCS to be NP-complete and propose two algorithms for the DCS.We also prove the correctness of the proposed algorithms. Simulation results are presentedto demonstrate the performance of these algorithms.
Secondly, we define and solve the problem of finding non-disjoint cover sets and al-locating the work time for each of them to maximize the network lifetime, called multipledirectional cover sets problem (MDCS), in target-oriented directional sensor networks. InMDCS, we organize the directions of sensors into non-disjoint subsets, each of which is acover set, and allocate the work time for each cover set. We alternately activate only onecover set at any time. When one cover set is activated, each sensor that has a direction in thiscover set is in the active state and works in this direction, while all the other sensors are inthe sleep state. We prove the MDCS to be NP-complete and propose several algorithms forthe MDCS. We compare the performance of these algorithms by simulations exhaustively.
Thirdly, we propose a precise and energy-aware coverage control algorithm, namedarea-based collaborative sleeping (ACOS) algorithm, for area-oriented omni-directional sen-sor networks. This algorithm precisely controls the mode of sensors to maximize the areacoverage and minimize the energy consumption based on the net sensing area of a sensor.The area coverage of a sensor network is measured by the fraction of the region covered.The net sensing area of a sensor is the area of the region exclusively covered by the sensoritself. If the net sensing area of a sensor is less than a given threshold, the sensor will goto sleep. Collaboration is introduced to the algorithm to balance the energy consumptionamong sensors. Performance study shows that ACOS has better coverage of the surveillancearea while waking fewer sensors than other state-of-the-art sleeping algorithms.
引文
[1] M. Weiser. The computer for the twenty-first century. Scientific American, 265(3):94–104, 1991.
[2] G. Pottie and W. Kaiser. Wireless integrated network sensors. Communications of the ACM, 2000.
[3] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. A survey on sensor networks. ACMTransactions on Multimedia Computing, Communications and Applications, 40(8):102–114, Aug2002.
[4] A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, and J. Anderson. Wireless sensor networksfor habitat monitoring. In Proceedings of First ACM International Workshop on Wireless SensorNetworks and Applications (WSNA), 2002.
[5]曹彦川,陶然.无线传感器网络的研究进展.科技导报, 23(9), 2005.
[6]芦东昕,徐文龙,王利存.无线传感器网络.工业控制计算机, 18(4):24–25, 2005.
[7]马祖长,孙怡宁,梅涛.无线传感器网络综述.通信学报, 25(4), 2004.
[8]盛超华,陈章龙.无线传感器网络及应用.微型电脑应用, 21(6), 2005.
[9]任丰原,黄海宁,林闯.传感器网络.软件学报, 14(7), 2003.
[10]孙利民,李建中,陈渝,朱红松.无线传感器网络.清华大学出版社, 2005.
[11] F. Zhao and L. Guibas. Wireless Sensor Networks: An Information Processing Approach.Elsevier/Morgan-Kaufmann, 2004.
[12] J. A. Gutierrez. IEEE 802.15.4: A developing standard for low-power, low-cost wireless personalarea networks,”. IEEE Network, 15(5):12–19, 2001.
[13] A. Woo and D. E. Culler. A transmission control scheme for media access in sensor networks. InProceedings of ACM MobiCom, 2001.
[14] W. Ye, J. Heidemann, and D. Estrin. An energy-efficient mac protocol for wireless sensor network.In Proceedings of IEEE INFOCOM, 2002.
[15] T. v. Dam and K. Langendoen. An adaptive energy-efficient MAC protocol for wireless sensor net-works. In Proceedings of the 1st international conference on Embedded networked sensor systems(SenSys 03), pages 171–180, New York, NY, USA, 2003. ACM.
[16] Z. Zuniga. Integrating future large-scale wireless sensor networks with the internet. USC ComputerScience, Technical Report, 2003.
[17] W.R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication proto-col for wireless microsensor networks. In Proceedings of the Hawaii International Conference onSystem Sciences, 2000.
[18] M. Y. K. Arisha and M. Younis. Energy-aware TDMA-based MAC for sensor networks. In Pro-ceedings of IEEE Workshop on Integrated Management of Power Aware Communications, Com-puting and NeTworking (IMPACCT 2002), 2002.
[19] J. Li and G. Lazarou. A bit-map-assisted energy-efficient MAC scheme for wireless sensor net-works. In Proceedings of The 3rd International Symposium on Information Processing in SensorNetworks (IPSN04), 2004.
[20] K. Sohrabi and G. J. Pottie. Performance of a novel self-organization protocol for wireless ad hocsensor networks. In Proceedings of the IEEE 50th Vehicular Technology Conference, 1999.
[21] E. Shih, S. Cho, N. Ickes, R. Min, A. Sinha, A. Wang, and A. Chandrakasan. Physical layer drivenprotocol and algorithm design for energy-efficient wireless sensor networks. In Proceedings ofACM MobiCom, 2001.
[22] I. Stojmenovic and X. Lin. Loop-free hybrid single-path/?ooding routing algorithms with guar-anteed delivery for wireless networks. IEEE Transactions on Parallel and Distributed Systems,12(10):1023–1032, 2001.
[23] W. Heinzelman, J. Kulik, and H. Balakrishnan. Adaptive protocols for information disseminationin wireless sensor networks. In Proceedings of ACM MobiCom, 1999.
[24] K. Sohrabi, J. Gao, V. Ailawadhi, and G.J. Pottie. Protocols for self-organization of a wirelesssensor network. IEEE Personal Communications, pages 16–27, October 2000.
[25] C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed diffusion: A scalable and robust com-munication paradigm for sensor networks. In Proceedings of ACM MobiCom, 2000.
[26] http://nms.lcs.mit.edu/projects/.
[27] A. Manjeshwar and D. P. Agrawal. Teen: A protocol for enhanced efficiency in wireless sensornetworks. In Proceedings of the 15th International Parallel & Distributed Processing Symposium,2001.
[28] S. Lindsey and C.S. Raghavendra. Pegasis: Power-efficient gathering in sensor information sys-tems. In Proceedings of IEEE Aerospace Conference, 2002.
[29] http://www.tinyos.net.
[30] C. Karlof, N. Sastry, and D. Wagner. Tinysec: a link layer security architecture for wireless sensornetworks. In Proceedings of the 2nd International Conference on Embedded Networked SensorSystems, 2004.
[31] S. R. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. TinyDB: an acquisitional queryprocessing system for sensor networks. ACM Transactions on Database Systems, 30(1):122–173,2005.
[32] http://telegraph.cs.berkeley.edu/tinydb/.
[33] P. Levis, N. Lee, M. Welsh, and D. Culler. Tossim: accurate and scalable simulation of entire tinyosapplications. In Proceedings of the 1st International Conference on Embedded Networked SensorSystems, 2003.
[34] W. F. Fung, D. Sun, and J. Gehrke. COUGAR: the network is the database. In Proceedings of the2002 ACM SIGMOD international conference on Management of data, pages 621–621, New York,NY, USA, 2002. ACM.
[35] http://www.cs.cornell.edu/database/cougar/.
[36] http://www.isis.vanderbilt.edu/projects/nest/.
[37] W. Su. Time-diffusion synchronization protocol for wireless sensor networks. IEEE/ACM Trans-actions on Networking, 13(2):384–397, 2005.
[38] Q. Shi. Performance analysis of relative location estimation for multihop wireless sensor networks.IEEE Journal on Selected Areas in Communications, 23(4):830–838, 2005.
[39] http://www.cens.ucla.edu/Research.
[40] http://www.intel.com/research/exploratory/sensornetwork operation.htm.
[41] J. Polastre, R. Szewczyk, and D. Culler. Telos: enabling ultra-low power wireless research. InProceedings of the 4th International Symposium on Information Processing in Sensor Networks(IPSN 05), 2005.
[42] Crossbow Technology. http://www.xbow.com.
[43] J. Hill and D. Culler. Mica: A wireless platform for deeply embedded networks. ACM Transactionson Multimedia Computing, Communications and Applications, 22(6):12–24, 2002.
[44] J. Lester, T. Choudhury, G. Borriello, S. Consolvo, J. Landay, K. Everitt, and I. Smith. Sensing andmodeling activities to support physical fitness. In Proceedings of Ubicomp Workshop: Monitoring,Measuring and Motivating Exercise: Ubiquitous Computing to Support Fitness, 2005.
[45] N. B. Priyantha, A. Chakraborty, and H. Balakrishnan. The cricket location-support system. InProceedings of ACM MobiCom, 2000.
[46] J. M. Kahn, R. H. Katz, and K. S. J. Pister. Next century challenges: mobile networking for s¨martdust”. In Proceedings of ACM MobiCom, 1999.
[47] N. Xu. A survey of sensor network applications. University of Southern California, TechnicalReport, 2002.
[48] http://www.alertsystems.org.
[49] R. Szewczyk, A. Mainwaring, J. Polastre, J. Anderson, and D. Culler. An analysis of a largescale habitat monitoring application. In Proceedings of ACM Conference on Embedded NetworkedSensor Systems (SenSys), 2004.
[50] H. Wang, J. Elson, L. Girod, D. Estrin, and K. Yao. Target classification and localization in habitatmonitoring. In Proceedings of IEEE ICASSP, 2003.
[51] E. Biagioni and K. Bridges. The application of remote sensor technology to assist the recovery ofrare and endangered species. Special issue on Distributed Sensor Networks for the InternationalJournal of High Performance Computing Applications, 16(3), August 2002.
[52] E. Biagioni and G. Sasaki. Wireless sensor placement for reliable and efficient data collection. InProceedings of the Hawaiii International Conference on Systems Sciences, 2003.
[53] G. Werner-Allen, K. Lorincz, J. Johnson, J. Lees, and M. Welsh. Fidelity and yield in a volcanomonitoring sensor network. In Proceedings of the 7th USENIX Symposium on Operating SystemsDesign and Implementation (OSDI 06), pages 27–27, Berkeley, CA, USA, 2006. USENIX Associ-ation.
[54] T. C. Henderson, E. Grant, K. Luthy, and J. Cintron. Snow monitoring with sensor networks.In Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks(LCN 04), pages 558–559, Washington, DC, USA, 2004. IEEE Computer Society.
[55] A. Rytter. Vibration based inspection of civil engineering structures. In Ph. D. Dissertation, Dept.of Building Technology and Structural Eng., Aalborg Univ., Denmark, 1993.
[56] http://www.citris.berkeley.edu/smartenergy/smartenergy.html.
[57] L. Schwiebert, S. K. S. Gupta, and J. Weinmann. Research challenges in wireless networks ofbiomedical sensors. In Proceedings of ACM MobiCom, 2001.
[58] M. B. Srivastava, R. R. Muntz, and M. Potkonjak. Smart kindergarten: sensor-based wireless net-works for smart developmental problem-solving environments. In Proceedings of ACM MobiCom,2001.
[59] M. Cardei and J.Wu. Coverage in Wireless Sensor Networks, Handbook of Sensor Networks. CRCPress, 2004.
[60] C. Huang and Y. Tseng. A survey of solutions to the coverage problems in wireless sensor networks.Journal of Internet Technology, 6(1):1–8, 2005.
[61]王燕莉,安世全.无线传感器网络的覆盖问题研究.传感技术学报, 18(2):307–312, 2005.
[62]任彦,张思东,张宏科.无线传感器网络中覆盖控制理论与算法.软件学报, (03), 2006.
[63]胡湘华,杨学军.传感网节点调度方法综述.计算机工程与科学, 30(3), 2008.
[64] B. Liu and D. Towsley. A study of the coverage of large-scale sensor networks. In Proceedings ofIEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), 2004.
[65] M. Rahimi, R. Baer, O. I. Iroezi, J. C. Garcia, J. Warrior, D. Estrin, and M. Srivastava. Cyclops: Insitu image sensing and interpretation in wireless sensor networks. In Proceedings of ACM SenSys,2005.
[66] W. Feng, E. Kaiser, W. C. Feng, and M. L. Baillif. Panoptes: Scalable low-power video sensornetworking technologies. ACM Transactions on Multimedia Computing, Communications andApplications, 1(2):151–167, May 2005.
[67] J. Djugash, S. Singh, G. Kantor, and W. Zhang. Range-only SLAM for robots operating cooper-atively with sensor networks. In Proceedings of IEEE International Conference on Robotics andAutomation, 2006.
[68] C. Gui and P. Mohapatra. Power conservation and quality of surveillance in target tracking sensornetworks. In Proceedings of ACM MobiCom, 2004.
[69] S. Kumar, T. H. Lai, and J. Balogh. On k-coverage in a mostly sleeping sensor network. InProceedings of ACM MobiCom, 2004.
[70] F. Ye, G. Zhong, J. Cheng, S.W. Lu, and L.X. Zhang. PEAS: a robust energy conserving protocolfor long-lived sensor networks. In Proceedings of IEEE International Conference on NetworkProtocols (ICNP), 2002.
[71] H. Liu, P. Wan, C. Yi, X. Jia, S. Makki, and P. Niki. Maximal lifetime scheduling in sensorsurveillance networks. In Proceedings of IEEE INFOCOM, 2005.
[72] M. X. Cheng, L. Ruan, and W. Wu. Achieving minimum coverage breach under bandwidth con-straints in wireless sensor networks. In Proceedings of IEEE INFOCOM, 2005.
[73] M. Cardei, M. T. Thai, Y. Li, and W. Wu. Energy-efficient target coverage in wireless sensornetworks. In Proceedings of IEEE INFOCOM, 2005.
[74] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava. Coverage problems in wirelessad-hoc sensor networks. In Proceedings of IEEE INFOCOM, 2001.
[75] S. Megerian, F. Koushanfar M. Potkonjak, and M. Srivastava. Worst and best-case coverage insensor networks. IEEE Transactions on Mobile Computing, 4(1):84–92, 2005.
[76] J. Cortes, S. Martinez, T. Karatas, and F. Bullo. Coverage control for mobile sensing networks.IEEE Transactions on Robotics and Automation, 20(2):243–255, 2004.
[77] X. Li, P. Wan, and O. Frieder. Coverage in wireless ad hoc sensor networks. IEEE Transactions onComputers, 52(6):753–763, 2003.
[78] S. Meguerdichian, F. Koushanfar, G. Qu, and M. Potkonjak. Exposure in wireless ad-hoc sensornetworks. In Proceedings of ACM MobiCom, 2001.
[79] S. Meguerdichian, S. Slijepcevic, V. Karayan, and M. Potkonjak. Localized algorithms in wirelessad-hoc networks: location discovery and sensor exposure. In Proceedings of the 2nd ACM interna-tional symposium on Mobile ad hoc networking & computing (MobiHoc 01), pages 106–116, NewYork, NY, USA, 2001. ACM.
[80] S. Adlakha and M. Srivastava. Critical density thresholds for coverage in wireless sensor networks.In Proceedings of IEEE Wireless Communications and Networking (WCNC), pages 1615–1620,2003.
[81] S. S. Dhillon. Sensor placement for effective coverage and surveillance in distributed sensor net-works. In Proc. of IEEE Wireless Communications and Networking Conference, pages 1609–1614,2003.
[82] K. Kar and S. Banerjee. Node placement for connected coverage in sensor networks. In Proc. ofthe Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, pages 50–52, 2003.
[83] F. Lin and P. Chiu. A near-optimal sensor placement algorithm to achieve complete cover-age/discrimination in sensor networks. IEEE Communications Letters, 9(1):43–45, 2005.
[84] S. Shakkottai, R. Srikant, and N. Shroff. Unreliable sensor grids: Coverage, connectivity anddiameter. In Proceedings of IEEE INFOCOM, 2003.
[85] K. Chakrabarty, S. Lyengar, H. Qi, and E. Cho. Grid coverage for surveillance and target locationin distributed sensor networks. IEEE Transactions on Computers, 51(12):1448–1453, 2002.
[86] S. Kumar, T. Lai, and A. Arora. Barrier coverage with wireless sensors. In Proceedings of ACMMobiCom, 2005.
[87] M. Cardei and D. Du. Improving wireless sensor network lifetime through power aware organiza-tion. ACM Wireless Networks, 11:333–340, 2005.
[88] C. Huang, Y. Tseng, and L. Lo. The coverage problem in three-dimensional wireless sensor net-works. Journal of Interconnection Networks, 8(3):209–227, 2007.
[89] V. Ravelomanana. Extremal properties of three-dimensional sensor networks with applications.IEEE Transactions on Mobile Computing, 3:246–257, 2004.
[90] B. Liu, P. Brass, O. Dousse, P. Nain, and D. Towsley. Mobility improves coverage of sensornetworks. In MobiHoc’05: Proceedings of the 6th ACM international symposium on Mobile adhoc networking and computing, pages 300–308, New York, NY, USA, 2005. ACM.
[91] G. Wang, G. Cao, and T. Porta. Movement-assisted sensor deployment. IEEE Transactions onMobile Computing, 5(6):640–652, 2006.
[92] X. Wang, Y. Yang, and Z. Zhang. A virtual rhomb grid-based movement-assisted sensor deploy-ment algorithm in wireless sensor networks. In Proceedings of the First International Multi-Symposiums on Computer and Computational Sciences (IMSCCS 06), pages 491–495, 2006.
[93]傅质馨,徐志良,黄成,吴晓蓓.无线传感器网络节点部署问题研究.传感器与微系统,27(3):116–120, 2008.
[94] L. Liu, F. Xia, Z. Wang, J. Chen, and Y. Sun. Deployment issues in wireless sensor networks. InProceedings of MSN 2005, pages 239–248, 2005.
[95] M. Cardei and J. wu. Energy-efficient coverage problems in wireless ad-hoc seusor networks.Computer Communications, 29(4):413–420, 2006.
[96] C. Huang and Y. Tseng. The coverage problem in a wireless sensor network. In Proceedings ofWSNA, 2003.
[97] X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C. Gill. Integrated coverage and connectivityconfiguration in wireless sensor networks. In Proceedings of ACM SenSys, 2004.
[98] H. Zhang and J. C. Hou. Maintaining sensing coverage and connectivity in large sensor networks.Ad Hoc & Sensor Wireless Networks, An International Journal, 1:89–124, 2005.
[99] M. Lu, J. Wu, M. Cardei, and M. Li. Energy-efficient connected coverage of discrete targets inwireless sensor networks. In Proceedings of the Third International Conference on Networkingand Mobile Computing, pages 43–52, 2005.
[100] http://www.xbow.com/products/Product pdf files/ Wireless pdf/MICA2 Datasheet.pdf.
[101]徐淑丽.基于无线传感器网络的覆盖问题的研究.山东大学硕士论文, 2007.
[102] L. Benini, A. Bogliolo, and G. De Micheli. A survey of design techniques for system-level dynamicpower management. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 8(3):299–316, 2000.
[103] C. Xian and Y. Lu. Dynamic voltage scaling for multitasking real-time systems with uncertainexecution time. In Proceedings of the 16th ACM Great Lakes symposium on VLSI (GLSVLSI 06),pages 392–397, 2006.
[104] T. Yan, T. He, and J. A. Stankovic. Differentiated surveillance for sensor networks. In Proceedingsof the 1st international conference on Embedded networked sensor systems (SenSys 03), pages51–62, New York, NY, USA, 2003. ACM.
[105] Y. Xu, J. Heidemann, and D. Estrin. Geography informed energy conservation for ad hoc routing.In Proceedings of ACM MobiCom, 2001.
[106] B. Chen, K. Jamieson, and H. Balakrishnan. Span: An energy efficient coordination algorithm fortopology maintenance in ad hoc wireless network. In Proceedings of ACM MobiCom, 2001.
[107] A. Cerpa and D. Estrin. Ascent: Adaptive self-configuring sensor networks topologies. In Pro-ceedings of IEEE INFOCOM, 2002.
[108] D. Tian and N. D. Georganas. A coverage-preserving node scheduling scheme for large wirelesssensor networks. In Proceedings of WSNA, 2002.
[109] B. Carbunar, A. Grama, J. Vitek, and O. Carbunar. Coverage preserving redundancy elimination insensor networks. In Proceedings of IEEE SECON, pages 377–386, 10 2004.
[110] R. Choudhury and R. Kravets. Location-independent coverage in wireless sensor networks. Tech-nical Report, UIUC, 2004.
[111] Kui Wu, Yong Gao, Fulu Li, and Yang Xiao. Lightweight deployment-aware scheduling for wire-less sensor networks. Mobile Networks and Applications, 10(6):837–852, 2005.
[112] S. Slijepcevic and M. Potkonjak. Power efficient organization of wireless sensor networks. InProceedings of IEEE International Conference on Communications, 2001.
[113] G. Lu, N. Sadagopan, B. Krishnamachari, and A. Goel. Delay efficient sleep scheduling in wirelesssensor networks. In Proceedings of IEEE INFOCOM, 2005.
[114] M. Chu, J. Reich, and F. Zhao. Distributed attention for large video sensor networks. In Proceedingsof Intelligent Distributed Surveilliance Systems, pages 61–65, Feb. 2004.
[115] W. Zhang, J. Djugash, and S. Singh. Parrots: A range measuring sensor network. Technical ReportCMU-RI-TR-06-05, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA,, 2007.
[116] J. Djugash, S. Singh, and B. Grocholsky. Decentralized mapping of robot-aided sensor networks.In IEEE International Conference on Robotics and Automation, May 2008.
[117] P. Dutta, M. Grimmer, A. Arora, S. Bibyk, and D. E. Culler. Design of a wireless sensor net-work platform for detecting rare, random, and ephemeral events. In Proceedings of the FourthInternational Symposium on Information Processing in Sensor Networks (IPSN), pages 497–502,2005.
[118] P. K. Dutta, A. K. Arora, and S. B. Bibyk. Towards radar-enabled sensor networks. In Proceedingsof The Fifth International Conference on Information Processing in Sensor Networks (IPSN), pages467–474, 2006.
[119] H. Ma and Y. Liu. On coverage problems of directional sensor networks. In Proceedings ofInternational Conference on Mobile Ad-hoc and Sensor Networks (MSN), 2005.
[120] J. Ai and A. A. Abouzeid. Coverage by directional sensors in randomly deployed wireless sensornetworks. Journal of Combinatorial Optimization, 11(1):21–41, February 2006.
[121] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms, SecondEdition. MIT Press, 2001.
[122] L. A. Wolsey and G. L. Nemhauser. Integer and Combinatorial Optimization. Wiley, 1999.
[123] Y. Ye. An O(n3L) potential reduction algorithm for linear programming. Mathematical Program-ming, 50:239–258, 1991.
[124] P. Bahl and V. N. Padmanabhan. Radar: An in-building rf-based user location and tracking system.In Proceedings of IEEE INFOCOM, 2000.
[125] K. Langendoen and N. Reijers. Distributed localization in wireless sensor networks: a quantitativecomparison. Computer Networks, pages 499–518, 2003.
[126] R. L. Moses, D. Krishnamurthy, and R. M. Patterson. A self-localization method for wireless sensornetworks. EURASIP J. Appl. Signal Process., pages 348–358, 2003.
[127] L. Hu and D. Evans. Localization for mobile sensor networks. In Proceedings of ACM MobiCom,2004.
[128] N. Patwari, A. O. Hero, M. Perkins, N. S. Correal, and R. J. O’Dea. Relative location estimation inwireless sensor networks. IEEE Transactions on Signal Processing, 51:2137–2148, 2003.