无线传感器网络层次型拓扑控制算法及相关问题的研究
|
摘要
无线传感器网络是一种通过组织大量具备感知、计算和无线通信能力的微型传感器节点协作地对物理区域中的事件进行监测和数据采集的新型网络，其逐渐展现出了巨大的应用前景。无线传感器网络的特点是节点硬件资源受限、网络规模巨大、拓扑动态变化、网络自组织和以数据为中心，而节能和延长网络生命周期是无线传感器网络研究的中心议题。层次型拓扑控制算法在满足网络覆盖度和连通度的前提下，通过选择部分节点处于工作状态并同时让剩余节点进入休眠状态，形成一个优化的数据转发结构，从而达到提高网络性能和降低网络能耗的目的。层次型拓扑控制算法主要分为两类：连通型和覆盖型。
本文对传感器网络层次型拓扑控制算法及其相关问题进行了研究：
首先，本文提出了一种新颖的连通型层次拓扑控制算法：基于可连Cell的拓扑控制算法(CCTC)。通过分析当前基于Cell的层次型拓扑控制算法的局限性，本文首先提出了1-con方法：当一个Cell的头节点被加入当前骨干网时，所有其可以连接的Cell使用该节点连入拓扑结构，而该新骨干网以分布式递归的方式继续扩大。然后，本文基于1-con思想设计了CCTC，并从理论上证明了CCTC不仅可以保证其所形成的拓扑结构维持网络连通，而且每一轮用于形成骨干网的工作节点很少，因此显著降低了网络工作能耗。CCTC的计算复杂度是线性的，空间复杂度和信息交换量为常数量级，非常适合传感器网络使用。实验结果同样表明，CCTC可以在提供良好鲁棒性和较少的消息交换量的情况下，更有效地节省节点能耗并延长网络生命周期。
其次，本文研究了传感器网络及普通节点，应当基于什么标准来进行连通型拓扑控制方式或覆盖型拓扑控制方式的选择的问题。当前，这两类拓扑算法的研究主要集中于如何优化各自的网络节能效果和算法复杂度，但是对于何时该选用连通型或覆盖型拓扑控制算法并没有理论上的分析。本文通过分析发现：随着物理事件发生频率的增长，采用覆盖型的方式比连通型的方式更加节能，反之亦然。通过定义物理事件发生密度ρ_e——单位时间单位面积的物理事件发生次数，本文首先在物理事件均匀分布的前提下推导出阈值ρ_e~*，即如果物理事件的发生密度ρ_e≥ρ_e~*，网络应当选用覆盖型算法，否则选用连通型算法；进而，本文得出普通节点的行为决策标准k~*，即如果其在一个周期T内，感应到物理事件e的总次数k满足k≥k~*，那么它就参与工作节点集合的覆盖算法，反之则休眠。仿真实验验证了本文分析的理论结果在拓扑控制算法的选择和节点的行为决策中具有一定指导意义。
基于以上理论结果，本文提出了一种基于Cell以感知质量(QoSE)为中心的无线传感器网络拓扑控制算法(CQCTC)，该算法在连通型和覆盖型两类算法中取得了一个平衡。本文首先提出了感知质量(QoSE)的概念——感知质量由节点感知到物理事件的频率和信号强度共同决定；普通节点通过对自己在下一个周期QoSE的预测结果来判断自己是否可以成为合法的候选工作节点，接下来每个Cell的头节点(CH)收集QoSE合法节点的覆盖情况，并选择一个优化子集来覆盖物理事件高发区域同时让剩余节点睡眠。通过仿真实验发现，CQCTC算法改善了连通型拓扑控制算法和覆盖型拓扑控制算法各自的缺点，允许传感器网络根据目标／事件的分布范围和发生频率动态调整拓扑结构，从而降低了每轮的工作能耗而且提高的数据准确率。
最后，本文研究了异构传感器网络的QoS路由算法。因为对于连续型查询或者快照查询的应用，用户可能对于关键数据的传输设定定量的延迟约束，本文针对该应用在异构网络模型中提出了满足并行查询延迟约束的最小能耗路由问题，并设计了一种分布式层次型路由协议。本文通过理论分析证明了该协议的正确性和无环性，而实验结果也表明该协议可以在满足延迟约束的条件下，比LEACH协议节省能耗3～8倍。
Wireless sensor network (WSN) is a kind of new network which could mointor and collect data from physical regions by coordinating plenty of tiny sensor nodes which are capable of sensing, computing and wireless communicating. This kind of networks has gradually demonstrated a promising applicational future. WSN has characteristics such as limited hardware resources, big network scale, dynamic topology, self-organization and data-centric, and the central issues of WSN researches are energy conservation and network lifetime prolonging. Hierarchical topology control algorithms could enhance network performances and decrease network energy costs by selecting a subset of nodes as working nodes while let the rest nodes go to sleep to form an optimized data transmission structure under certain coverage and connectivity degree. Basically, hierarchical topology control algorithms are classified as two types: connectivity type and coverage type.
This paper conducts researches on WSN hierarchical topology control algorithms and their related issues:
Firstly, this paper proposes a novel connectivity type hierarchical topology control algorithm: Connectible-Cell based Topology Control algorithm (CCTC). Initially, by analyzing the limitations of current Cell based hierarchical topology control algorithms, this paper proposes 1-con method: when a Cell Head is connected to the current backbone, all Cells that could be reached by this head will be connected to the topology structure through it, and then this new backbone expands itself distributedly and recursively in the same way. By leveraging 1-con method, CCTC is designed, and it is theoretically proved that CCTC could not only guarantee network connectivity, but also use fewer active nodes per round than other algorithms do to form backbone network, so the working energy is notably decreased. CCTC is suitable for WSN since its computing complexity is linear, and the storage space as well as the message amount is bounded by constant magnitude. Simulation results also validate that CCTC provides impressive energy conservation effect and long network lifetime with decent robustness and limited control overheads.
Afterwards, this paper focus on the problem that as far as a WSN and its normal nodes are concerned, which criteria should be adopted to determine whether to use the connectivity type topology algorithms or the coverage type topology algorithms. To the best of our knowledge, the current researches on these two types of hierarchical topology control algorithms mainly focus on the optimaization of energy cost and algorithm complexity, but no theoretical analysis has been conducted on when to use the connectivity type or coverage type. This paper discovers that with the increment of physical events frequencies, the coverage type algorithms are more energy efficient than the connectivity type be, and vice versa. By defining physical events densityρ_e---the times of events happening per unit time and unit area, this paper firstly gives the thresholdρ_e~* under the condition of events uniform distribution, i.e. if the physical events density satisfiesρ_e≥ρ_e~*, WSN should use coverage type, otherwise use connectivity type; then, this paper gives k~*: the action decision criterion for every normal node, i.e. if k---the total times of sensed events e of the node in a round ---satisfies k≥k~*, it should join in the coverage algorithm of working nodes set, otherwise it should go to sleep. Simulations validate that the theoretical results presented in this paper have decent significance on topology algorithm selection and nodes' action decision.
Based on the above theoretical results, a Cell-based QoSE-Centric Topology Control algorithm (CQCTC) is proposed in the paper, which provides a trade-off between the connectivity type and the coverage type. This paper firstly gives the concept of QoSE (Quality of SEnsing) --- QoSE consists of the sensed frequency and signal strength, and normal node uses its QoSE predicted for next round to judge whether it could play the role as a valid candidate working node; then, every Cell Head collects the coverage information of all valid nodes in its Cell to construct an optimized working set to cover the high event-frequency regions while let the rest of nodes go to sleep. Simulations indicate CQCTC exploits the advantages of both connectivity type and coverage type and forms proper topology structures dynamically according to the distributions and frequencies of the targets/events, therefore the working energy cost is decreased and the data accuracy is enhanced.
At last, this paper studies the QoS routing algorithms in heterogeneous WSN. Since users could set delay constraints for key data transmissions in continuous queries or snapshot queries, this paper propose the problem on how to find the least energy cost paths for simultaneously running queries under their delay constraints, and a distributed hierarchical routing protocol is given. Theoretical analysis proves that this protocol is correct and loop-free. Simulations also indicate that this protocol could save energy cost 3-8 times compared to LEACH with the delay constraints satisfied.
本文对传感器网络层次型拓扑控制算法及其相关问题进行了研究：
首先，本文提出了一种新颖的连通型层次拓扑控制算法：基于可连Cell的拓扑控制算法(CCTC)。通过分析当前基于Cell的层次型拓扑控制算法的局限性，本文首先提出了1-con方法：当一个Cell的头节点被加入当前骨干网时，所有其可以连接的Cell使用该节点连入拓扑结构，而该新骨干网以分布式递归的方式继续扩大。然后，本文基于1-con思想设计了CCTC，并从理论上证明了CCTC不仅可以保证其所形成的拓扑结构维持网络连通，而且每一轮用于形成骨干网的工作节点很少，因此显著降低了网络工作能耗。CCTC的计算复杂度是线性的，空间复杂度和信息交换量为常数量级，非常适合传感器网络使用。实验结果同样表明，CCTC可以在提供良好鲁棒性和较少的消息交换量的情况下，更有效地节省节点能耗并延长网络生命周期。
其次，本文研究了传感器网络及普通节点，应当基于什么标准来进行连通型拓扑控制方式或覆盖型拓扑控制方式的选择的问题。当前，这两类拓扑算法的研究主要集中于如何优化各自的网络节能效果和算法复杂度，但是对于何时该选用连通型或覆盖型拓扑控制算法并没有理论上的分析。本文通过分析发现：随着物理事件发生频率的增长，采用覆盖型的方式比连通型的方式更加节能，反之亦然。通过定义物理事件发生密度ρ_e——单位时间单位面积的物理事件发生次数，本文首先在物理事件均匀分布的前提下推导出阈值ρ_e~*，即如果物理事件的发生密度ρ_e≥ρ_e~*，网络应当选用覆盖型算法，否则选用连通型算法；进而，本文得出普通节点的行为决策标准k~*，即如果其在一个周期T内，感应到物理事件e的总次数k满足k≥k~*，那么它就参与工作节点集合的覆盖算法，反之则休眠。仿真实验验证了本文分析的理论结果在拓扑控制算法的选择和节点的行为决策中具有一定指导意义。
基于以上理论结果，本文提出了一种基于Cell以感知质量(QoSE)为中心的无线传感器网络拓扑控制算法(CQCTC)，该算法在连通型和覆盖型两类算法中取得了一个平衡。本文首先提出了感知质量(QoSE)的概念——感知质量由节点感知到物理事件的频率和信号强度共同决定；普通节点通过对自己在下一个周期QoSE的预测结果来判断自己是否可以成为合法的候选工作节点，接下来每个Cell的头节点(CH)收集QoSE合法节点的覆盖情况，并选择一个优化子集来覆盖物理事件高发区域同时让剩余节点睡眠。通过仿真实验发现，CQCTC算法改善了连通型拓扑控制算法和覆盖型拓扑控制算法各自的缺点，允许传感器网络根据目标／事件的分布范围和发生频率动态调整拓扑结构，从而降低了每轮的工作能耗而且提高的数据准确率。
最后，本文研究了异构传感器网络的QoS路由算法。因为对于连续型查询或者快照查询的应用，用户可能对于关键数据的传输设定定量的延迟约束，本文针对该应用在异构网络模型中提出了满足并行查询延迟约束的最小能耗路由问题，并设计了一种分布式层次型路由协议。本文通过理论分析证明了该协议的正确性和无环性，而实验结果也表明该协议可以在满足延迟约束的条件下，比LEACH协议节省能耗3～8倍。
Wireless sensor network (WSN) is a kind of new network which could mointor and collect data from physical regions by coordinating plenty of tiny sensor nodes which are capable of sensing, computing and wireless communicating. This kind of networks has gradually demonstrated a promising applicational future. WSN has characteristics such as limited hardware resources, big network scale, dynamic topology, self-organization and data-centric, and the central issues of WSN researches are energy conservation and network lifetime prolonging. Hierarchical topology control algorithms could enhance network performances and decrease network energy costs by selecting a subset of nodes as working nodes while let the rest nodes go to sleep to form an optimized data transmission structure under certain coverage and connectivity degree. Basically, hierarchical topology control algorithms are classified as two types: connectivity type and coverage type.
This paper conducts researches on WSN hierarchical topology control algorithms and their related issues:
Firstly, this paper proposes a novel connectivity type hierarchical topology control algorithm: Connectible-Cell based Topology Control algorithm (CCTC). Initially, by analyzing the limitations of current Cell based hierarchical topology control algorithms, this paper proposes 1-con method: when a Cell Head is connected to the current backbone, all Cells that could be reached by this head will be connected to the topology structure through it, and then this new backbone expands itself distributedly and recursively in the same way. By leveraging 1-con method, CCTC is designed, and it is theoretically proved that CCTC could not only guarantee network connectivity, but also use fewer active nodes per round than other algorithms do to form backbone network, so the working energy is notably decreased. CCTC is suitable for WSN since its computing complexity is linear, and the storage space as well as the message amount is bounded by constant magnitude. Simulation results also validate that CCTC provides impressive energy conservation effect and long network lifetime with decent robustness and limited control overheads.
Afterwards, this paper focus on the problem that as far as a WSN and its normal nodes are concerned, which criteria should be adopted to determine whether to use the connectivity type topology algorithms or the coverage type topology algorithms. To the best of our knowledge, the current researches on these two types of hierarchical topology control algorithms mainly focus on the optimaization of energy cost and algorithm complexity, but no theoretical analysis has been conducted on when to use the connectivity type or coverage type. This paper discovers that with the increment of physical events frequencies, the coverage type algorithms are more energy efficient than the connectivity type be, and vice versa. By defining physical events densityρ_e---the times of events happening per unit time and unit area, this paper firstly gives the thresholdρ_e~* under the condition of events uniform distribution, i.e. if the physical events density satisfiesρ_e≥ρ_e~*, WSN should use coverage type, otherwise use connectivity type; then, this paper gives k~*: the action decision criterion for every normal node, i.e. if k---the total times of sensed events e of the node in a round ---satisfies k≥k~*, it should join in the coverage algorithm of working nodes set, otherwise it should go to sleep. Simulations validate that the theoretical results presented in this paper have decent significance on topology algorithm selection and nodes' action decision.
Based on the above theoretical results, a Cell-based QoSE-Centric Topology Control algorithm (CQCTC) is proposed in the paper, which provides a trade-off between the connectivity type and the coverage type. This paper firstly gives the concept of QoSE (Quality of SEnsing) --- QoSE consists of the sensed frequency and signal strength, and normal node uses its QoSE predicted for next round to judge whether it could play the role as a valid candidate working node; then, every Cell Head collects the coverage information of all valid nodes in its Cell to construct an optimized working set to cover the high event-frequency regions while let the rest of nodes go to sleep. Simulations indicate CQCTC exploits the advantages of both connectivity type and coverage type and forms proper topology structures dynamically according to the distributions and frequencies of the targets/events, therefore the working energy cost is decreased and the data accuracy is enhanced.
At last, this paper studies the QoS routing algorithms in heterogeneous WSN. Since users could set delay constraints for key data transmissions in continuous queries or snapshot queries, this paper propose the problem on how to find the least energy cost paths for simultaneously running queries under their delay constraints, and a distributed hierarchical routing protocol is given. Theoretical analysis proves that this protocol is correct and loop-free. Simulations also indicate that this protocol could save energy cost 3-8 times compared to LEACH with the delay constraints satisfied.
引文
李建中，李金宝，石胜飞．2003．传感器网络及其数据管理的概念、问题与进展[J]．软件学报，14(10)：1717-1727． 李虹．2007．无线传感器网络中节能相关若干关键问题研究[D】：[博士】．合肥：中国科学??技术大学．
孙利民等．2005．无线传感器网络[M]．北京：清华大学出版社．王福豹，史龙，任丰原．2005．无线传感器网络中的自身定位系统和算法[J]．软件学报，16(05)：857-868．
杨文国，郭田德，赵彤．2007．异构监测传感器网络寿命最大化模型及其求解[J]．计算机学报．30(4)：532-538．
张学，陆桑璐，陈贵海，陈道蓄，谢立．2007．无线传感器网络的拓扑控制[J]．软件学报，18(4)，943-954．
Akyildiz LF, Su WL, Sankarasubramaniam Y, Cayirci E.2002. A survey on sensor networks[J]. IEEE Communications Magazine, 40(8): 102-114.
AllawayE H. 2004. Wireless sensor networks: architectures and protocols[M]. CPC Press, 11-12.
A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk, and J. Anderson. 2002.Wireless Sensor Networks for Habitat Monitoring[C]. Proc. First ACM Int'l Workshop on Wireless Sensor Networks and Applications, 88-97.
Bahramgiri M, Hajiaghayi MT, Mirrokni VS. 2002. Fault-Tolerant and 3-dimensional distributed topology control algorithms in wireless multihop networks[C]. In: Proc. of the IEEE Int'l Conf. on Computer Communications and Networks (ICCCN). 392-397.
Bao LC, Garcia-Luna-Aceves JJ. 2003.Topology management in ad hoc networks[C]. In: Proc. of the ACM Int'l Symp. on Mobile Ad-Hoc Networking and Computing (MobiHoc). NY, USA. 129-140.
Cardei, M. Thai, M.T. Yingshu Li, et al. 2005. Energy-efficient target coverage in wireless sensor networks[C]. In: Proc of INFOCOM, Miami USA. 3: 1976-1984.
Chien C, et al. 2001. Low-power direct-sequence spread-spectrum modem architecture for distributed wireless sensor networks[C]. SLPED'01, Huntington Beach, CA.32-40
Clementi A, Penna P, Silvestri R.2004. On the power assignment problem in radio networks[J]. ACM/Kluwer Mobile Networks and Applications (MONET), 9(2):125—140.
C. Hsin and M. Liu.2005. Partial clustering: maintaining connectivity in a low duty-cycled dense wireless sensor network[C]. In Proc. 5th IEEE Workshop on Algorithms for Ad Hoc and Sensor Networks (WMAN'05), Denver, Colorado. 243-251
Chan H, Perrig A.2004.ACE: An emergent algorithm for highly uniform cluster formation[C]. In: Proc, of the 1st European Workshop on Wireless Sensor Networks. Berlin. 154-171.
Chen H, Wu H, Tzeng N. 2004. Grid-based Approach for Working Node Selection in Wireless Sensor Networks[C]. IEEE international conference on communications, Paris, France. 6: 3673-3678
Cortes J, Martinez S, Karatas T, Bullo F.2004. Coverage control for mobile sensing networks[J]. IEEE Trans, on Robotics and Automation. 20(2):243-255.
Deng J, Han YS, Heinzelman WB, Varshney PK. 2005. Scheduling sleeping nodes in high density cluster-based sensor networks[J]. ACM/Kluwer Mobile Networks and Applications (MONET), 10(6):825-835.
E. Ihler. 1991. The complexity of approximating the class steiner tree problem[R]. Technical Report, Institut fur Informatik, Universitat Freiburg.
Gupta P, Kumar PR.2000. The capacity of wireless networks[J]. IEEE Trans, on Information Theory, 46(2):388-404.
Gupta H, Das SR, Gu Q. 2003. Connected sensor cover: Self-Organization of sensor networks for efficient query execution[C]. In Proc, of the ACM Int'l Symp. on Mobile Ad Hoc Networking and Computing (MobiHOC). NY, 189-200.
G. Simon, M. Maro' ti, A. Le'deczi, G. Balogh, B. Kusy, A. Na'das, G. Pap, J. Sallai, and K. Frampton.2004. Sensor Network-Based Countersniper System[C]. Proc. ACM Second Int'l Conf. Embedded Networked Sensor Systems, 1-12.
Hamrita T, et al.2005. Advances in smart sensor technology[C]. Conference of Industry Applications, 2059-2062
Heinzelman WR, Chandrakasan AP, Balakrishnan H.2000. Energy-Efficient communication protocol for wireless microsensor networks[C]. In: Proc, of the Hawaaian Int'l Conf, on System Science (HICSS). Washington. 3005-3014.
H. F. Salama, Douglas S. Reeves, and Yannis Viniotis.1997. A distributed algorithm for delay constrained unicast routing [C]. IEEE INFOCOM. Japan. 1: 84-91.
Intanagonwiwat C, Govindan R, Estrin D, Heidemann J.2003. Directed diffusion for wireless sensor networking[J]. IEEE/ACM Trans, on Networking, 11(1):2-16.
Jian Ma, Min Gao, Qian Zhang, Lionel M. Ni.2007. Energy-Efficient Localized Topology Control Algorithms in IEEE 802.15.4-Based Sensor Networksfj]. IEEE Transactions on Parallel and Distributed Systems. 18(5)711-720.
J. Mark Keil.1993.The complexity of domination problems in circle graphs[M]. Discrete Applied Mathematics.
Kawadia V. 2004. Protocols and architecture for wireless ad hoc networks [D]: [Ph.D]. University of Illinois at Urbana-Champaign.
Kirousis LM, Kranakis E, Krizanc D, Pelc A. 2000. Power consumption in packet radio networksfj]. Theoretical Computer Science, 243(1-2): 289-305.
Kumar S, Lai TH, Balogh J.2004. On k-coverage in a mostly sleeping sensor network[C]. In Proc, of the ACM Int'l Conf, on Mobile Computing and Networking, NY, 144-158.
Kubisch M, Karl H, Wolisz A, Zhong LC, Rabaey J.2003. Distributed algorithms for transmission power control in wireless sensor networks[C]. In Proc, of the IEEE Wireless Communications and Networking Conf. (WCNC). NY. 16-20.
Kulik J, Heinzelman WR, Balakrishnan H.2002. Negotiation based protocols for disseminating information in wireless sensor networksfj].Wireless Networks. 8(2-3): 169-185.
K. Akkaya and M. Younis.2005. Energy-Aware and QoS Routing in Wireless Sensor Networks [J]. Springer Cluster Computing Journal. 8:179-188
L. Feeney and M. Nilson.2001. Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[C]. In Proc. IEEE INFOCOM 2001,1548-1557.
Lin FYS, Chiu PL.2005. A near-optimal sensor placement algorithm to achieve complete coverage/discrimination in sensor networks[J].IEEE Communications Letters, 9(1):43—45.
Li N, Hou JC. 2004. Topology control in heterogeneous wireless networks: Problems and solutions[C]. In: Proc, of the IEEE Conf, on Computer Communications (INFOCOM). NY. 232-243.
Li L, Halpern JY, Bahl P, Wang YM, Wattenhofer R. 2005. A cone-based distributed topology control algorithm for wireless multi-hop networksfj]. IEEE/ACM Trans, on Networking, 13(1):147-159.
Li XY, Song WZ, Wang Y. 2005. Localized topology control for heterogeneous wireless sensor networks[J]. ACM Trans, on Sensor Networks. 2(1):129—153.
ManleyE D, et al.2006. Localization and tracking in sensor systems[C]. IEEE International Conference on Sensor Networks,Ubiquitous, and Trustworthy Computing, 2:237-242.
Manjeshwar A, Grawal DP. 2001. TEEN: A protocol for enhanced efficiency in wireless sensor networks[C]. In: Proc, of the 15th Parallel and Distributed Processing Symp. San Francisco. 2009-2015.
Mathematica. www.wolfram.com/products/mathematica/.
Megerian S, Koushanfar F, Potkonjak M, Srivastava MB. 2005.Worst and best-case coverage in sensor networks[J]. IEEE Trans. on Mobile Computing, 4(1):84—92.
Meguerdichian S, Koushanfar F, Potkonjak M, Srivastava MB. 2001. Coverage problems in wireless ad-hoc sensor network[C]. In: Proc, of the IEEE INFOCOM. Anchorage: IEEE Press, 1380-1387.
Meguerdichian S, Koushanfar F, Qu G, Potkonjak M.2001. Exposure in wireless ad-hoc sensor networks[C]. In Proc, of the ACM Int'1 Conf, on Mobile Computing and Networking. NY, 139-150.
M. Cardei, D. MacCallum, X. Cheng, M. Min, X. Jia, D. Li, and D.-Z. Du. 2002. Wireless sensor networks with energy efficient organization[J]. Interconnection Networks, 3(3-4): 213-229.
M. Bhardwaj, A. Chandrakasan.2002. Bounding the lifetime of sensor networks via optimal role assignment[C]. Proc. 21st Ann. Joint Conf, of the IEEE Computer and Communications Societies, NY. 3: 1587-1596.
Mhatre V, Rosenberg C, Kofman D, Mazumdar R, Shroff N. 2005. A minimum cost heterogeneous sensor network with a lifetime constraint[J]. IEEE Transaction on Mobile Computing, 4(1): 4-15.
Mo Li, Baijian Yang. 2006. A Survey on Topology issues in Wireless Sensor Network[C]. Proceedings of the 2006 international conference on wireless networks, Las Vegas. 503-509.
Moustapha Diaby. 1993. Implicit enumeration for the pure integer 0/1 minimax programming problem[J].Operations Research, 41(6): 1172-1176.
M. Garey and D. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. New York: W.H. Freeman and Co.
Narayanaswamy S, Kawadia V, Sreenivas RS, Kumar PR.2002. Power control in ad-hoc networks: Theory, architecture, algorithm and implementation of the COMPOW protocol[C]. In: Proc, of the European Wireless Conf. Florence, 156-162.
Niculescu D. 2004. Positioning in adhoc sensor networks[J]. IEEE Network, 18 (4):24 -29
Niculescu D, Nath B. 2003. Trajectory based forwarding and its applications[C]. In: Proc, of the 9th Annual Int'1 Conf, on Mobile Computing and Networking. San Diego. 260-272.
NS2. www.isi.edu/nsnam/ns/.
Perrig A, et al. 2002. SPINS: security protocols for sensor networks[J].Wireless Networks, 8(5):521-534
Poduri S, Pattern S, Krishnamachari B, Sukhatme G. 2005. A unifying framework for tunable topology control in sensor nerworks[R]. Technical Report, CRES-05-004, University of Southern California, 1-15.
Paolo Santi and Janos Simon. 2004. Silence is golden with high probability: Maintaining a connected backbone in wireless sensor networks[C]. In Proc. IEEE European Workshop on Wireless Sensor Networks, 106-121.
Samuel Madden et al.2002. Continuously adaptive continuous queries over streams [C]. Proc, of the 2002 ACM SIGMOD international conference on Management of data. Wisconsin USA. 49-60.
S. Lindsey, C. S. Raghavendra.2002.PEGASlS: Power Efficient GAthering in Sensor Information Systems [C]. Proceedings of the IEEE Aerospace Conference. Montana, USA. 3: 3-11.
Sivrikaya F and Yener B.2004. Time synchronization in sensor networks: a survey[J]. IEEE Network, 18 (4):45-50
Sundararaman B, et al. 2005. Clock synchronization for wireless sensor networks: a su rvey[J]. AdHoc Networks(Elsevier), 3(3):281-323.
Shih E, Cho S, Ickes N, et al. July 2001. Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks[C]. Proceedings of ACM MobiCom'01, Rome, Italy, 272-286
Slijepcevic S, Potkonjak M, Tsiatsis V, et al.2002. On communication security in wrieless ad-hoc sensor networks[C]. Proceedings of IEEE International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises, 139-144.
S. Guha and S. Khuller. 1998. Approximation Algorithms for Connected Dominating Sets[J]. Algorithmica, 20(4): 374-387.
S. Ren, Q. Li, H.N.Wang, X. Chen, and X. Zhang.2004. Probabilistic coverage for object tracking in sensor networks[R]. Mobicom04 Poster Session. Philadelphia.
S. Upadhyayula et al.2003. A Low-Latency and Energy-Efficient Algorithm for Convergecast in Wireless Sensor Networks[C]. GLOBECOM. San Francisco, USA. 3525-3530.
Tilak S, Abu-Ghazaleh NB, Heinzelman W. 2002. A taxonomy of wireless micro-sensor network models[J]. Mobile Computing and Communications Review, 1(2): 1-8.
Tian D, Georganas ND.2003.A node scheduling scheme for energy conservation in large wireless sensor networks[J]. Wireless Communications and Mobile Computing,3(2): 271-290.
TobagiF A and Kleinrock L. 1975. Packet switching in radio channels: Part 11-the hidden terminal problem in carrier sense multiple access modes and the busy tone solution[J]. IEEE transactions on Communications, 23 (12):1417-1433
Tseng Y C, et al. 2004. Energy-Efficient topology control for wireless ad hoc sensor networks[J]. Journal of Information Science and Engineering, 20(1):27-37
T. He et al.2003. SPEED: A stateless protocol for real-time communication in sensor networks[C]. Proceedings of ICDCS. Providence, RI. 46-56.
Walters J P, et al.2006. Security in distributed, grid,and pervasive computing(Chapterl7:w ireless sensor networks security: a survey)[M]. Auerbach Publications, CRCPress
Wu K, Gao Y, Li F, Xiao Y. 2005. Lightweight deployment-aware scheduling for wireless sensor networks[J].ACM/Kluwer Mobile Networks and Applications (MONET), 10(6):837-852.
Wu, Q. Rao, N. S. V. Barhen, J. Iyengar, S. S. Vaishnavi, V. K. Qi, H. Chakrabarty, K..2004. On Computing Mobile Agent Routes for Data Fusion in Distributed Sensor Networks[J]. IEEE Transactions on knowledge and data engineering, 16(6), 740-753.
Xie ZJ, Wang L, Lin YP, Chen H, Liu YH.2006. An algorithm of data aggregation based on data compression for sensor networks[J]. Journal of Software, 17(4) :860-867.
Xing GL, Wang XR, Zhang YF, Lu CY, Pless R, Gill C.2005. Integrated coverage and connectivity configuration for energy conservation in sensor networks[J]. ACM Trans, on Sensor Networks, 1(1):36-72.
X. Ning, R. Sumit, C. Krishna Kant, G. Deepak, B. Alan, G. Ramesh, and E. Deborah.2004. A Wireless Sensor Network for Structural Monitoring[C]. Proc. ACM Second Int'l Conf. Embedded Networked Sensor Systems, 13-24.
Younis O, Fahmy S.2004. HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[J]. IEEE Trans, on Mobile Computing, 3(4):660—669.
Y. Xu, J. Heidemann, and D. Estrin. 2001.Geography-informed energy conservation for ad hoc routing[C], In ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), 70-84
Zhang X, Lu SL, Chen DX, Xie L.2006. PREG: A practical power control algorithm based on a novel proximity graph for heterogeneous wireless sensor networks[C]. In Proc, of the 1st Int'l Conf, on Wireless Algorithms, Systems and Applications (WASA). Berlin, 620-631.
孙利民等．2005．无线传感器网络[M]．北京：清华大学出版社．王福豹，史龙，任丰原．2005．无线传感器网络中的自身定位系统和算法[J]．软件学报，16(05)：857-868．
杨文国，郭田德，赵彤．2007．异构监测传感器网络寿命最大化模型及其求解[J]．计算机学报．30(4)：532-538．
张学，陆桑璐，陈贵海，陈道蓄，谢立．2007．无线传感器网络的拓扑控制[J]．软件学报，18(4)，943-954．
Akyildiz LF, Su WL, Sankarasubramaniam Y, Cayirci E.2002. A survey on sensor networks[J]. IEEE Communications Magazine, 40(8): 102-114.
AllawayE H. 2004. Wireless sensor networks: architectures and protocols[M]. CPC Press, 11-12.
A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk, and J. Anderson. 2002.Wireless Sensor Networks for Habitat Monitoring[C]. Proc. First ACM Int'l Workshop on Wireless Sensor Networks and Applications, 88-97.
Bahramgiri M, Hajiaghayi MT, Mirrokni VS. 2002. Fault-Tolerant and 3-dimensional distributed topology control algorithms in wireless multihop networks[C]. In: Proc. of the IEEE Int'l Conf. on Computer Communications and Networks (ICCCN). 392-397.
Bao LC, Garcia-Luna-Aceves JJ. 2003.Topology management in ad hoc networks[C]. In: Proc. of the ACM Int'l Symp. on Mobile Ad-Hoc Networking and Computing (MobiHoc). NY, USA. 129-140.
Cardei, M. Thai, M.T. Yingshu Li, et al. 2005. Energy-efficient target coverage in wireless sensor networks[C]. In: Proc of INFOCOM, Miami USA. 3: 1976-1984.
Chien C, et al. 2001. Low-power direct-sequence spread-spectrum modem architecture for distributed wireless sensor networks[C]. SLPED'01, Huntington Beach, CA.32-40
Clementi A, Penna P, Silvestri R.2004. On the power assignment problem in radio networks[J]. ACM/Kluwer Mobile Networks and Applications (MONET), 9(2):125—140.
C. Hsin and M. Liu.2005. Partial clustering: maintaining connectivity in a low duty-cycled dense wireless sensor network[C]. In Proc. 5th IEEE Workshop on Algorithms for Ad Hoc and Sensor Networks (WMAN'05), Denver, Colorado. 243-251
Chan H, Perrig A.2004.ACE: An emergent algorithm for highly uniform cluster formation[C]. In: Proc, of the 1st European Workshop on Wireless Sensor Networks. Berlin. 154-171.
Chen H, Wu H, Tzeng N. 2004. Grid-based Approach for Working Node Selection in Wireless Sensor Networks[C]. IEEE international conference on communications, Paris, France. 6: 3673-3678
Cortes J, Martinez S, Karatas T, Bullo F.2004. Coverage control for mobile sensing networks[J]. IEEE Trans, on Robotics and Automation. 20(2):243-255.
Deng J, Han YS, Heinzelman WB, Varshney PK. 2005. Scheduling sleeping nodes in high density cluster-based sensor networks[J]. ACM/Kluwer Mobile Networks and Applications (MONET), 10(6):825-835.
E. Ihler. 1991. The complexity of approximating the class steiner tree problem[R]. Technical Report, Institut fur Informatik, Universitat Freiburg.
Gupta P, Kumar PR.2000. The capacity of wireless networks[J]. IEEE Trans, on Information Theory, 46(2):388-404.
Gupta H, Das SR, Gu Q. 2003. Connected sensor cover: Self-Organization of sensor networks for efficient query execution[C]. In Proc, of the ACM Int'l Symp. on Mobile Ad Hoc Networking and Computing (MobiHOC). NY, 189-200.
G. Simon, M. Maro' ti, A. Le'deczi, G. Balogh, B. Kusy, A. Na'das, G. Pap, J. Sallai, and K. Frampton.2004. Sensor Network-Based Countersniper System[C]. Proc. ACM Second Int'l Conf. Embedded Networked Sensor Systems, 1-12.
Hamrita T, et al.2005. Advances in smart sensor technology[C]. Conference of Industry Applications, 2059-2062
Heinzelman WR, Chandrakasan AP, Balakrishnan H.2000. Energy-Efficient communication protocol for wireless microsensor networks[C]. In: Proc, of the Hawaaian Int'l Conf, on System Science (HICSS). Washington. 3005-3014.
H. F. Salama, Douglas S. Reeves, and Yannis Viniotis.1997. A distributed algorithm for delay constrained unicast routing [C]. IEEE INFOCOM. Japan. 1: 84-91.
Intanagonwiwat C, Govindan R, Estrin D, Heidemann J.2003. Directed diffusion for wireless sensor networking[J]. IEEE/ACM Trans, on Networking, 11(1):2-16.
Jian Ma, Min Gao, Qian Zhang, Lionel M. Ni.2007. Energy-Efficient Localized Topology Control Algorithms in IEEE 802.15.4-Based Sensor Networksfj]. IEEE Transactions on Parallel and Distributed Systems. 18(5)711-720.
J. Mark Keil.1993.The complexity of domination problems in circle graphs[M]. Discrete Applied Mathematics.
Kawadia V. 2004. Protocols and architecture for wireless ad hoc networks [D]: [Ph.D]. University of Illinois at Urbana-Champaign.
Kirousis LM, Kranakis E, Krizanc D, Pelc A. 2000. Power consumption in packet radio networksfj]. Theoretical Computer Science, 243(1-2): 289-305.
Kumar S, Lai TH, Balogh J.2004. On k-coverage in a mostly sleeping sensor network[C]. In Proc, of the ACM Int'l Conf, on Mobile Computing and Networking, NY, 144-158.
Kubisch M, Karl H, Wolisz A, Zhong LC, Rabaey J.2003. Distributed algorithms for transmission power control in wireless sensor networks[C]. In Proc, of the IEEE Wireless Communications and Networking Conf. (WCNC). NY. 16-20.
Kulik J, Heinzelman WR, Balakrishnan H.2002. Negotiation based protocols for disseminating information in wireless sensor networksfj].Wireless Networks. 8(2-3): 169-185.
K. Akkaya and M. Younis.2005. Energy-Aware and QoS Routing in Wireless Sensor Networks [J]. Springer Cluster Computing Journal. 8:179-188
L. Feeney and M. Nilson.2001. Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[C]. In Proc. IEEE INFOCOM 2001,1548-1557.
Lin FYS, Chiu PL.2005. A near-optimal sensor placement algorithm to achieve complete coverage/discrimination in sensor networks[J].IEEE Communications Letters, 9(1):43—45.
Li N, Hou JC. 2004. Topology control in heterogeneous wireless networks: Problems and solutions[C]. In: Proc, of the IEEE Conf, on Computer Communications (INFOCOM). NY. 232-243.
Li L, Halpern JY, Bahl P, Wang YM, Wattenhofer R. 2005. A cone-based distributed topology control algorithm for wireless multi-hop networksfj]. IEEE/ACM Trans, on Networking, 13(1):147-159.
Li XY, Song WZ, Wang Y. 2005. Localized topology control for heterogeneous wireless sensor networks[J]. ACM Trans, on Sensor Networks. 2(1):129—153.
ManleyE D, et al.2006. Localization and tracking in sensor systems[C]. IEEE International Conference on Sensor Networks,Ubiquitous, and Trustworthy Computing, 2:237-242.
Manjeshwar A, Grawal DP. 2001. TEEN: A protocol for enhanced efficiency in wireless sensor networks[C]. In: Proc, of the 15th Parallel and Distributed Processing Symp. San Francisco. 2009-2015.
Mathematica. www.wolfram.com/products/mathematica/.
Megerian S, Koushanfar F, Potkonjak M, Srivastava MB. 2005.Worst and best-case coverage in sensor networks[J]. IEEE Trans. on Mobile Computing, 4(1):84—92.
Meguerdichian S, Koushanfar F, Potkonjak M, Srivastava MB. 2001. Coverage problems in wireless ad-hoc sensor network[C]. In: Proc, of the IEEE INFOCOM. Anchorage: IEEE Press, 1380-1387.
Meguerdichian S, Koushanfar F, Qu G, Potkonjak M.2001. Exposure in wireless ad-hoc sensor networks[C]. In Proc, of the ACM Int'1 Conf, on Mobile Computing and Networking. NY, 139-150.
M. Cardei, D. MacCallum, X. Cheng, M. Min, X. Jia, D. Li, and D.-Z. Du. 2002. Wireless sensor networks with energy efficient organization[J]. Interconnection Networks, 3(3-4): 213-229.
M. Bhardwaj, A. Chandrakasan.2002. Bounding the lifetime of sensor networks via optimal role assignment[C]. Proc. 21st Ann. Joint Conf, of the IEEE Computer and Communications Societies, NY. 3: 1587-1596.
Mhatre V, Rosenberg C, Kofman D, Mazumdar R, Shroff N. 2005. A minimum cost heterogeneous sensor network with a lifetime constraint[J]. IEEE Transaction on Mobile Computing, 4(1): 4-15.
Mo Li, Baijian Yang. 2006. A Survey on Topology issues in Wireless Sensor Network[C]. Proceedings of the 2006 international conference on wireless networks, Las Vegas. 503-509.
Moustapha Diaby. 1993. Implicit enumeration for the pure integer 0/1 minimax programming problem[J].Operations Research, 41(6): 1172-1176.
M. Garey and D. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. New York: W.H. Freeman and Co.
Narayanaswamy S, Kawadia V, Sreenivas RS, Kumar PR.2002. Power control in ad-hoc networks: Theory, architecture, algorithm and implementation of the COMPOW protocol[C]. In: Proc, of the European Wireless Conf. Florence, 156-162.
Niculescu D. 2004. Positioning in adhoc sensor networks[J]. IEEE Network, 18 (4):24 -29
Niculescu D, Nath B. 2003. Trajectory based forwarding and its applications[C]. In: Proc, of the 9th Annual Int'1 Conf, on Mobile Computing and Networking. San Diego. 260-272.
NS2. www.isi.edu/nsnam/ns/.
Perrig A, et al. 2002. SPINS: security protocols for sensor networks[J].Wireless Networks, 8(5):521-534
Poduri S, Pattern S, Krishnamachari B, Sukhatme G. 2005. A unifying framework for tunable topology control in sensor nerworks[R]. Technical Report, CRES-05-004, University of Southern California, 1-15.
Paolo Santi and Janos Simon. 2004. Silence is golden with high probability: Maintaining a connected backbone in wireless sensor networks[C]. In Proc. IEEE European Workshop on Wireless Sensor Networks, 106-121.
Samuel Madden et al.2002. Continuously adaptive continuous queries over streams [C]. Proc, of the 2002 ACM SIGMOD international conference on Management of data. Wisconsin USA. 49-60.
S. Lindsey, C. S. Raghavendra.2002.PEGASlS: Power Efficient GAthering in Sensor Information Systems [C]. Proceedings of the IEEE Aerospace Conference. Montana, USA. 3: 3-11.
Sivrikaya F and Yener B.2004. Time synchronization in sensor networks: a survey[J]. IEEE Network, 18 (4):45-50
Sundararaman B, et al. 2005. Clock synchronization for wireless sensor networks: a su rvey[J]. AdHoc Networks(Elsevier), 3(3):281-323.
Shih E, Cho S, Ickes N, et al. July 2001. Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks[C]. Proceedings of ACM MobiCom'01, Rome, Italy, 272-286
Slijepcevic S, Potkonjak M, Tsiatsis V, et al.2002. On communication security in wrieless ad-hoc sensor networks[C]. Proceedings of IEEE International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises, 139-144.
S. Guha and S. Khuller. 1998. Approximation Algorithms for Connected Dominating Sets[J]. Algorithmica, 20(4): 374-387.
S. Ren, Q. Li, H.N.Wang, X. Chen, and X. Zhang.2004. Probabilistic coverage for object tracking in sensor networks[R]. Mobicom04 Poster Session. Philadelphia.
S. Upadhyayula et al.2003. A Low-Latency and Energy-Efficient Algorithm for Convergecast in Wireless Sensor Networks[C]. GLOBECOM. San Francisco, USA. 3525-3530.
Tilak S, Abu-Ghazaleh NB, Heinzelman W. 2002. A taxonomy of wireless micro-sensor network models[J]. Mobile Computing and Communications Review, 1(2): 1-8.
Tian D, Georganas ND.2003.A node scheduling scheme for energy conservation in large wireless sensor networks[J]. Wireless Communications and Mobile Computing,3(2): 271-290.
TobagiF A and Kleinrock L. 1975. Packet switching in radio channels: Part 11-the hidden terminal problem in carrier sense multiple access modes and the busy tone solution[J]. IEEE transactions on Communications, 23 (12):1417-1433
Tseng Y C, et al. 2004. Energy-Efficient topology control for wireless ad hoc sensor networks[J]. Journal of Information Science and Engineering, 20(1):27-37
T. He et al.2003. SPEED: A stateless protocol for real-time communication in sensor networks[C]. Proceedings of ICDCS. Providence, RI. 46-56.
Walters J P, et al.2006. Security in distributed, grid,and pervasive computing(Chapterl7:w ireless sensor networks security: a survey)[M]. Auerbach Publications, CRCPress
Wu K, Gao Y, Li F, Xiao Y. 2005. Lightweight deployment-aware scheduling for wireless sensor networks[J].ACM/Kluwer Mobile Networks and Applications (MONET), 10(6):837-852.
Wu, Q. Rao, N. S. V. Barhen, J. Iyengar, S. S. Vaishnavi, V. K. Qi, H. Chakrabarty, K..2004. On Computing Mobile Agent Routes for Data Fusion in Distributed Sensor Networks[J]. IEEE Transactions on knowledge and data engineering, 16(6), 740-753.
Xie ZJ, Wang L, Lin YP, Chen H, Liu YH.2006. An algorithm of data aggregation based on data compression for sensor networks[J]. Journal of Software, 17(4) :860-867.
Xing GL, Wang XR, Zhang YF, Lu CY, Pless R, Gill C.2005. Integrated coverage and connectivity configuration for energy conservation in sensor networks[J]. ACM Trans, on Sensor Networks, 1(1):36-72.
X. Ning, R. Sumit, C. Krishna Kant, G. Deepak, B. Alan, G. Ramesh, and E. Deborah.2004. A Wireless Sensor Network for Structural Monitoring[C]. Proc. ACM Second Int'l Conf. Embedded Networked Sensor Systems, 13-24.
Younis O, Fahmy S.2004. HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[J]. IEEE Trans, on Mobile Computing, 3(4):660—669.
Y. Xu, J. Heidemann, and D. Estrin. 2001.Geography-informed energy conservation for ad hoc routing[C], In ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), 70-84
Zhang X, Lu SL, Chen DX, Xie L.2006. PREG: A practical power control algorithm based on a novel proximity graph for heterogeneous wireless sensor networks[C]. In Proc, of the 1st Int'l Conf, on Wireless Algorithms, Systems and Applications (WASA). Berlin, 620-631.