无线传感网络拓扑控制关键问题
|
摘要
随着无线传感网络应用研究不断深入，涌现出间歇连通、容迟、容错等新概念，为相关系统分析和设计带来新的挑战。在拓扑控制领域，网络动态覆盖问题和能量效率问题不断凸显，引起学术界和工业界的普遍关注。本文分别针对这两方面问题展开研究，主要工作和创新点包括以下四方面。
首先，提出移动传感网络区域覆盖的统计特征，包括首达时间、累积覆盖面积、位置覆盖度和动态覆盖面积等。利用Jackson排队网络对区域动态覆盖问题进行建模，证明了区域覆盖问题在统计意义上等价于排队问题。结合北京市出租车真实运营数据和多种典型移动场景进行仿真，验证了上述理论结果可以辅助分析大规模移动传感网络的基本覆盖能力。
其次，提出基于二维元胞自动机的能量调度策略，利用传感网络容迟特征构造间歇连通图。通过“生命游戏”模拟无线传感网络的能量调度过程，从元胞空间上的动力学层次研究节点状态更新问题，提出将元胞空间拓扑演化分为“振荡”、“衰减”、“稳定”三种模式，指出在稳定模式下网络拓扑连通性、覆盖性和生存时间存在折中关系。
再次，提出基于局部感知的拓扑控制算法(LIc0)。相比其他方法，LIc0算法充分利用了网络容迟特性，在每个特定时刻网络可能不连通，但在较长时间尺度上可实现端到端可达性。仿真表明，采用s2803规则的LIc0算法下网络生存时间可达LEAcH算法的7倍，代价是牺牲15％左右的动态覆盖面积，网络平均端到端距离增加，并出现间歇连通的情况。
最后，提出基于指数退避机制的异步LIc0算法(A—LIc0)，针对大规模传感网络中难以实现全网时间同步的情形，对节点状态更新时机进行了改进。仿真表明，随着平均退避时间的增加，网络寿命增长，代价是动态覆盖能力和网络连通性变差。A—LIc0无需时间同步，更适合一般无线传感网络直用。
本论文的理论分忻和原理模型可供进一步研究参考，理论结果和算法设计可以指导实际的无线传感网络工程。
Emerging new applications of Wireless Sensor Networks(WSNs) have introducednew features, such as intermittently connectivity, delay tolerance and error-tolerance,which incur new challenges in analysis and development of WSNs. Regarding thetopology control problem, dynamic coverage and energy e?ciency are two criticalfactors that attract both academic and industrial interests. The contributions of thisthesis in this area are listed below.
First, theorems are proposed and proved to formulate statistic characters of areacoverage in mobile WSNs, including ?rst hit time, coverage degree distribution, dy-namic and accumulated coverage ratio, et al. Area coverage problem of mobile WSNsis modeled as a Jackson queueing network, and it is proved that the area coverageproblem is equivalent to a queueing problem in terms of statistical problem. By jointsimulations with a variety of mobile models and the real Beijing taxi traces, we showedthat the theoretical results could be used in analyzing large scale mobile WSNs.
Second, a Cellular Automata(CA) based energy scheduling mechanism is pro-posed, utilizing delay tolerant features to build intermittently connected graph. Theenergy scheduling is modeled as”game of life”, facilitating the study of sensor statetransition from collective dynamic system viewpoint. It is found that the spacial evolu-tion of CA topology can be classi?ed into several patterns, including oscillation, atten-uation and stabilization. Moreover, the tradeo? relations among connectivity, coverageand system lifetime under the stable mode is revealed.
Third, a new topology control algorithm for WSNs, namely LICO(LocalInformation-based Cognition and Operation) is proposed. LICO dose not require con-nectivity of network graph, and sensors can made state transition merely according toone hop interactions. Simulations showed that LICO enjoys much longer network life-time, which is about 7 times of that of LEACH under rule S2B03, in sacri?cing thedynamic coverage ratio by 15%, and the network’s intermittent loss of connectivity.
Finally, the asynchronized version of LICO, namely A-LICO is proposed, whichis based on exponential back-o?. Large scale WSNs’lack of synchronization restraintsthe applications and performance of LICO. A-LICO conquer the problem and enjoyslonger lifetime. Simulation shows A-LICO is ?ne turnable in that the coverage andconnectivity quality decreases as the the average back-o? time rises. Therefore A-LICO is more suitable to general large scale WSNs.
The proposed theoretical results, prototype and algorithms can be applied to prac-tical WSN applications.
首先，提出移动传感网络区域覆盖的统计特征，包括首达时间、累积覆盖面积、位置覆盖度和动态覆盖面积等。利用Jackson排队网络对区域动态覆盖问题进行建模，证明了区域覆盖问题在统计意义上等价于排队问题。结合北京市出租车真实运营数据和多种典型移动场景进行仿真，验证了上述理论结果可以辅助分析大规模移动传感网络的基本覆盖能力。
其次，提出基于二维元胞自动机的能量调度策略，利用传感网络容迟特征构造间歇连通图。通过“生命游戏”模拟无线传感网络的能量调度过程，从元胞空间上的动力学层次研究节点状态更新问题，提出将元胞空间拓扑演化分为“振荡”、“衰减”、“稳定”三种模式，指出在稳定模式下网络拓扑连通性、覆盖性和生存时间存在折中关系。
再次，提出基于局部感知的拓扑控制算法(LIc0)。相比其他方法，LIc0算法充分利用了网络容迟特性，在每个特定时刻网络可能不连通，但在较长时间尺度上可实现端到端可达性。仿真表明，采用s2803规则的LIc0算法下网络生存时间可达LEAcH算法的7倍，代价是牺牲15％左右的动态覆盖面积，网络平均端到端距离增加，并出现间歇连通的情况。
最后，提出基于指数退避机制的异步LIc0算法(A—LIc0)，针对大规模传感网络中难以实现全网时间同步的情形，对节点状态更新时机进行了改进。仿真表明，随着平均退避时间的增加，网络寿命增长，代价是动态覆盖能力和网络连通性变差。A—LIc0无需时间同步，更适合一般无线传感网络直用。
本论文的理论分忻和原理模型可供进一步研究参考，理论结果和算法设计可以指导实际的无线传感网络工程。
Emerging new applications of Wireless Sensor Networks(WSNs) have introducednew features, such as intermittently connectivity, delay tolerance and error-tolerance,which incur new challenges in analysis and development of WSNs. Regarding thetopology control problem, dynamic coverage and energy e?ciency are two criticalfactors that attract both academic and industrial interests. The contributions of thisthesis in this area are listed below.
First, theorems are proposed and proved to formulate statistic characters of areacoverage in mobile WSNs, including ?rst hit time, coverage degree distribution, dy-namic and accumulated coverage ratio, et al. Area coverage problem of mobile WSNsis modeled as a Jackson queueing network, and it is proved that the area coverageproblem is equivalent to a queueing problem in terms of statistical problem. By jointsimulations with a variety of mobile models and the real Beijing taxi traces, we showedthat the theoretical results could be used in analyzing large scale mobile WSNs.
Second, a Cellular Automata(CA) based energy scheduling mechanism is pro-posed, utilizing delay tolerant features to build intermittently connected graph. Theenergy scheduling is modeled as”game of life”, facilitating the study of sensor statetransition from collective dynamic system viewpoint. It is found that the spacial evolu-tion of CA topology can be classi?ed into several patterns, including oscillation, atten-uation and stabilization. Moreover, the tradeo? relations among connectivity, coverageand system lifetime under the stable mode is revealed.
Third, a new topology control algorithm for WSNs, namely LICO(LocalInformation-based Cognition and Operation) is proposed. LICO dose not require con-nectivity of network graph, and sensors can made state transition merely according toone hop interactions. Simulations showed that LICO enjoys much longer network life-time, which is about 7 times of that of LEACH under rule S2B03, in sacri?cing thedynamic coverage ratio by 15%, and the network’s intermittent loss of connectivity.
Finally, the asynchronized version of LICO, namely A-LICO is proposed, whichis based on exponential back-o?. Large scale WSNs’lack of synchronization restraintsthe applications and performance of LICO. A-LICO conquer the problem and enjoyslonger lifetime. Simulation shows A-LICO is ?ne turnable in that the coverage andconnectivity quality decreases as the the average back-o? time rises. Therefore A-LICO is more suitable to general large scale WSNs.
The proposed theoretical results, prototype and algorithms can be applied to prac-tical WSN applications.
引文
[1] Saltzer J, Reed D, Clark D. End-to-End arguments in system design. ACM Transactions onComputer Systems, 1984, 2(4):195– 206.
[2] Zimmermann H. OSI Reference Model: The ISO Model of Architecture for Open SystemsInterconnection. IEEE Transactions on Communications, 1980, 28(4):425–432.
[3] Huston G, Michaelson G. RFC 5396: Textual Representation of Autonomous System (AS)Numbers. The Internet Society, 2008.
[4]吴建平，吴茜，徐恪．下一代互联网体系结构基础研究及探索．计算机学报，2008，31(9)：1536-1548．
[5] Wawrzoniak M, Peterson L, Roscoe T. Sophia: an Information Plane for networked systems.ACM SIGCOMM Computer Communication Review, 2004, 34(1):15–20.
[6] Poslad S. Ubiquitous Computing Smart Devices, Smart Environments and Smart Interaction.Wiley, 2009.
[7]袁坚，王钺．网络发展及其更广泛的安全需求．中国电子科学研究院学报，2008，3(6)：551-557．
[8] Kephart J O, Chess DM. The Vision of Autonomic Computing. Computer, 2003, 36:41–50.
[9] Thomas R, Friend D, DaSilva L, et al. Cognitive Networks. Cognitive Radio, SoftwareDefined Radio, and Adaptive Wireless Systems, 2007. 17–41.
[10] DiMario M. System of systems interoperability types and characteristics in joint commandand control. System of Systems Engineering, 2006, 1:6–10.
[11] ITU. ITU Internet Reports 2005: The Internet of Things. Technical report, November, 1995.http://www.itu.int/internetofthings/.
[12] IBM. 22 opportunities for a smarter planet. Technical report, 2009.
[13]石军．“感知中国”促进中国物联网加速发展．通信管理与技术，2009，9(5)：1-3．
[14] Future Army Applications National Research Council C. Network Science. The NationalAcademies Press, 2006.
[15] Akyildiz I, Su W, Sankarasubramaniam Y, et al. A survey on sensor networks. CommunicationsMagazine, IEEE, 2002, 40(8):102– 114.
[16]于海斌，曾鹏等．智能无线传感器网络系统．科学出版社，2006：1-3．
[17] Callaway E. Wireless Sensor Network: Architecture and Protocols. CRC Press LLC, 2004.
[18]任丰原，黄海宁，林闯．无线传感器网络．软件学报，2003，14(7)：1282-1291．
[19] Estrin D, Govindan R, Heidemann J. Next century challenges: Scalable coordinate in sensornetwork. Proceedings of the 5th ACM/IEEE International Conference on Mobile Computingand Networking., Seattle: IEEE Computer Society, 1999.
[20] Cerf V, Burleigh S, Hooke A. DTN Research Group Internet Draft: Delay-Tolerant NetworkArchitecture. Technical report, 2003.
[21] Burleigh S, Hooke A, Torgerson L, et al. Delay-tolerant networking: an approach to interplanetaryInternet. IEEE Communications Magazine, 2003, 41(6):128– 136.
[22] Juang P, Oki H, Wang Y, et al. Energy-efficient computing for wildlife tracking: designtradeoffs and early experiences with ZebraNet. SIGOPS Operating Systems Review, 2002,36(5):96–107.
[23] Shah R, Roy S, Jain S, et al. Data MULEs: modeling a three-tier architecture for sparsesensor networks. Proceedings of the First IEEE International Workshop on Sensor NetworkProtocols and Applications, 2003. 30– 41.
[24] Pentland A, Fletcher R, Hasson A A. A Road to Universal Broadband Connectivity. Proceedingsof the 2nd International Conference of Open Collaborative Design for SustainableInnovation, 2002. 1–9.
[25]张学，陆桑璐，陈贵海，等．无线传感器网络的拓扑控制．软件学报，2007，18(4)：943 954．
[26]孙立民，李建中等．无线传感器网络．清华大学出版社，2005．
[27] Meguerdichian S, Koushanfar F, Potkonjak M, et al. Coverage problems in wireless ad-hocsensor networks. Proceedings of Twentieth Annual Joint Conference of the IEEE Computerand Communications Societies, 2001. 1380–1387.
[28] Cardei M, Wu J. Handbook of Sensor Networks:Compact Wireless and Wired SensingSystems. CRC Press, 2005.
[29] Li X Y,Wan P J, Frieder O. Coverage in wireless ad hoc sensor networks. IEEE Transactionson Computers, 2003, 52(6):753– 763.
[30] Megerian S, Koushanfar F, Potkonjak M, et al. Worst and best-case coverage in sensornetworks. IEEE Transactions on Mobile Computing, 2005, 4(1):84– 92.
[31] Liu B, Towsley D. A study of the coverage of large-scale sensor networks. Proceedings ofIEEE International Conference on Mobile Ad-hoc and Sensor Systems, 2004. 475– 483.
[32] Kumar S, Lai T, Balogh J. On k-coverage in a mostly sleeping sensor network. WirelessNetworks, 2008, 14(3):277–294.
[33] Wan P J, Yi C W. Coverage by randomly deployed wireless sensor networks. IEEE Transactionson Information Theory, 2006, 52(6):2658–2669.
[34] Tian D, Georganas N D. A coverage-preserving node scheduling scheme for large wirelesssensor networks. Proceedings of the 1st ACM international workshop on Wireless sensornetworks and applications, New York, NY, USA: ACM, 2002. 32–41.
[35] Ye F, Zhong G, Cheng J, et al. PEAS: A Robust Energy Conserving Protocol for LonglivedSensor Networks. Proceedings of International Conference on Distributed ComputingSystems, Los Alamitos, CA, USA: IEEE Computer Society, 2003. 28–37.
[36] Shakkottai S, Srikant R, Shroff N. Unreliable sensor grids: coverage, connectivity and diameter.Proceedings of Twenty-Second Annual Joint Conference of the IEEE Computer andCommunications, 2003. 1073– 1083.
[37] Meguerdichian S, Koushanfar F, Qu G, et al. Exposure in wireless Ad-Hoc sensor networks.Proceedings of the 7th annual international conference on Mobile computing and networking,New York, NY, USA: ACM, 2001. 139–150.
[38] Clouqueur T, Phipatanasuphorn V, Ramanathan P, et al. Sensor deployment strategy fortarget detection. Proceedings of the 1st ACM international workshop on Wireless sensornetworks and applications, New York, NY, USA: ACM, 2002. 42–48.
[39] Hata M. Empirical formula for propagation loss in land mobile radio services. IEEE Transactionson Vehicular Technology, 1980, 29(3):317– 325.
[40] Hall P. Introduction to the Theory of Coverage Processes. John Wiley & Sons Inc, 1988.
[41] Lazos L, Poovendran R. Stochastic coverage in heterogeneous sensor networks. ACMTransactions on Sensor Networks, 2006, 2(3):325–358.
[42] Ram S, Majunath D, Iyer S, et al. On the Path Coverage Properties of Random SensorNetworks. IEEE Transactions on Mobile Computing, 2007, 6(5):494–506.
[43] Manohar P, Ram S S, Manjunath D. Path coverage by a sensor field: The nonhomogeneouscase. ACM Transactions on Sensor Networks, 2009, 5(2):1–26.
[44] Ghrist R, Muhammad A. Coverage and hole-detection in sensor networks via homology.Proceedings of the 4th international symposium on Information processing in sensor networks,Piscataway, NJ, USA: IEEE Press, 2005. No.34.
[45] Silva V, Ghrist R, Muhammad A. Blind swarms for coverage in 2-d. Proceedings ofRobotics: Science and Systems, 2005. 1–8.
[46] Kar K, Banerjee S. Node Placement for Connected Coverage in Sensor Networks. Proceedingsof Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2003.
[47] Slijepcevic S, Potkonjak M. Power efficient organization of wireless sensor networks. Proceedingsof IEEE International Conference on Communications, 2001. 472–476.
[48] Ye F, Zhong G, Zhang L. Energy Efficient Robust Sensing Coverage in Large Sensor Networks.Technical report, Technical Report UCLA, 2002.
[49] Zhang H, Hou J. Maintaining Sensing Coverage and Connectivity in Large Sensor Networks.Technical Report UIUCDCS-R-2003-2351, Technical Report UIUC, 2003.
[50] Wang X, Xing G, Zhang Y, et al. Integrated coverage and connectivity configuration inwireless sensor networks. Proceedings of the 1st international conference on Embeddednetworked sensor systems, New York, NY, USA: ACM, 2003. 28–39.
[51] Cardei M, Du D Z. Improving wireless sensor network lifetime through power aware organization.Wireless Networks, 2005, 11(3):333–340.
[52] Wu K, Gao Y, Li F, et al. Lightweight Deployment-Aware Scheduling for Wireless SensorNetworks. Mobile Networks and Applications, 2005, 10(6):837–852.
[53]田乃硕，徐秀丽，马占友．离散时间排队论．科学出版社，2008．
[54]陆大.随机过程及其应用．清华大学出版社，2007．
[55] Serfozo R. Introduction to Stochastic Networks. Springer, July, 1999.
[56] Chen H, Yao D D. Fundamentals of queueing networks : performance, asymptotics, andoptimization. Springer, 2001.
[57] Hughes B D. Random walks and random environments. Oxford University Press, 1996.
[58] Broch J, Maltz D, Johnson D, et al. A performance comparison of multi-hop wireless adhoc network routing protocols. Proceedings of the Fourth Annual ACM/IEEE InternationalConference on Mobile Computing and Networking, Dallas, Texas, USA: ACM, 1998. 85–97.
[59] Bai F, Helmy A. A Survey of Mobility Models in Wireless Adhoc Networks (Chapter 1 inWireless Ad-Hoc Networks). Kluwer Academic, 2006.
[60] Hanashi A M, Awan I, Woodward M. Performance evaluation with different mobility modelsfor dynamic probabilistic flooding in MANETs. Mobile Information Systems, 2009,5(1):65–80.
[61]chopard B，Droz M，祝玉学等(译)．物理系统的元胞自动机模拟．清华大学出版社，2003．
[62] Mange D, Madon D, Stauffer A, et al. Von Neumann revisited: A Turing machine withself-repair and self-reproduction properties. Robotics and Autonomous Systems, 1997,22(1):35–58.
[63] Eliasmith C. The myth of the Turing machine: the failings of functionalism and relatedtheses. Journal of Experimental and Theoretical Artificial Intelligence, 2002, 14(1):1–8.
[64] Smillie K. Turing and the universal machine: The making of the modern computer. IEEEAnnals of the History of Computing, 2002, 24(2):95–95.
[65] Brackenbury I, Ravin Y. Machine intelligence and the Turing Test. IBM Systems Journal,2002, 41(3):524–529.
[66]贾斌，高自友等．基于元胞自动机的交通系统建模与模拟．科学出版社，2007．
[67] Vollmar R. John von Neumann and self-reproducing cellular automata. Journal of CellularAutomata, 2006, 1(4):353–376.
[68] Kazakov D, Sweet M. Evolving the game of life. Lecture Notes in Computer Science, 2005,3394:132–146.
[69] Langton C. Self-reproduction in cellular automata. Physica D, 1984, 10(1-2):135–144.
[70] Byl J. Selft-reproduction in small cellular automata. Physica D, 1989, 34(1-2):295–299.
[71] Taylor C, Langton C, Kitano H. Editor’s introduction: Special issue on highlights of theAlife VI Conference. Artif Life, 1998, 4(1):III–III.
[72] Wolfram S. 20 Problems in the theory of cellular automata. Phys Scripta, 1985, T9:170–183.
[73] Wolfram S. Cryptography with cellular automata. Lecture Notes in Computer Science,1986, 218:429–432.
[74] Wolfram S. Cellular automata as models of complextiy. Nature, 1984, 311(5985):419–424.
[75] Wolfram S. Universality and complexity in cellular automata. Physica D, 1984, 10(1):1–35.
[76] Wolfram S. Cellular automaton fluids: Basic theory. Journal of Statistical Physics, 1986,45(3-4):471–526.
[77] Wolfram S. Random sequence generation by cellular automata. Advances in Applied Mathematics,1986, 7(2):123–169.
[78] Wolfram S. Computation theory of cellular automata. Communications in MathematicalPhysics, 1984, 96(1):15–57.
[79] Chen S, Chen H, Martinez D, et al. Lattice boltzmann model for simulation of magnetohydrodynamics.Physical Review Letters, 1991, 67(27):3776–3779.
[80] Mattila K, Hyvaeluoma J, Timonen J, et al. Comparison of implementations of the lattice-Boltzmann method. Computers and Mathematics with Applications, 2008, 55(7):1514–1524.
[81] Benzi R, Succi S, Vergassola M. The lattice boltzmann-equation - theory and applications.Physics Reports, 1992, 222(3):145–197.
[82] Packard N, Wolfram S. Two-dimensional cellular automata. Journal of Statistical Physics,1985, 38(5-6):901–946.
[83] Dubacq J, Durand B, Formenti E. Kolmogorov complexity and cellular automata classification.Theoretical Computer Science, 2001, 259(2):271–285.
[84] Hurd L, Kari J, Culik K. The topological-entropy of cellular automata is umcomputable.Ergodic Theory and Dynamical Systems, 1992, 12:255–265.
[85] Voorhees B. Entropy of additive cellular automata. International Journal of TheoreticalPhysics, 1989, 28(11):1387–1396.
[86] Meyerovitch T. Finite entropy for multidimensional cellular automata. Ergodic Theory andDynamical Systems, 2008, 28:1243–1260.
[87] Akin H. The topological entropy of invertible cellular automata. Journal of Computationaland Applied Mathematics, 2008, 213(2):501–508.
[88] Gin A, Tougaw P, Williams S. An alternative geometry for quantum-dot cellular automata.Journal of Applied Physics, 1999, 85(12):8281–8286.
[89] Makowiec D. New challenges in cellular automata due to network geometry - Ferromagnetictransition study. Journal of Cellular Automata, 2006, 1(4):299–315.
[90] Jin X, Kim T. Classification of cellular automata and complexity. International Journal ofModern Physics B, 2003, 17(22-24):4232–4237.
[91] Sutner K. The computational complexity of cellular automata. Lecture Notes in ComputerScience, 1989, 380:451–459.
[92] Gordon D. On the computational power of totalistic cellular automata. Mathematical SystemsTheory, 1987, 20(1):43–52.
[93] Hansen P. Parallel cellular-automata: a model program for computational science. Concurrency:Practice and Experience, 1993, 5(5):425–448.
[94] Marr C, Hutt M. Topology regulates pattern formation capacity of binary cellular automataon graphs. Physica A, 2005, 354:641–662.
[95] Manzini G, Margara L. A complete and efficiently computable topological classificationof D-dimensional linear cellular automata over Z(m). Theoretical Computer Science, 1999,221(1-2):157–177.
[96] Burkhead E G. A topological classification of D-dimensional cellular automata. Dynamicalsystem, 2009, 24(1):45–61.
[97] Serra R, Villani M. Perturbing the regular topology of cellular automata: Implications forthe dynamics. Lecture Notes in Computer Science, 2002, 2493:168–177.
[98] Culik K, Hurd L, Yu S. Computation theoretic aspects of cellular automata. Physica D,1990, 45(1-3):357–378.
[99]谢惠民．复杂性与动力系统．上海科技教育出版社，1994．
[100] Cerpa A, Estrin D. ASCENT: Adaptive Self-Configuring sEnsor Networks Topologies.Proceedings of Twenty-First Annual Joint Conference of the IEEE Computer and CommunicationsSocieties, New York, USA, 2002. 1278– 1287.
[101]周成虎，孙战利等．地理元胞自动机研究．科学出版社，2000．
[102] Sesic A, Dautovic S, Malbasa V. Dynamic Power Management of a System With aTwo-Priority Request Queue Using Probabilistic-Model Checking. IEEE Transactions onComputer-Aided Design of Integrated Circuits and Systems, 2008, 27(2):403– 407.
[103] Park C W, Noh K W, Kim S Y. A new scheduling technique based on Dynamic VoltageScaling for MPSoC. Proceedings of International SoC Design Conference, Busan, Korea,2008. 73–76.
[104] Kirousis L M, Kranakis E, Krizanc D, et al. Power consumption in packet radio networks.Theoretical Computer Science, 2000, 243(1-2):289– 305.
[105] Kubisch M, Karl H,Wolisz A, et al. Distributed algorithms for transmission power control inwireless sensor networks. Proceedings of IEEEWireless Communications and Networking,New orleans, LA, USA, 2003. 558– 563.
[106] Li N, Hou J. Topology control in heterogeneous wireless networks: problems and solutions.Proceedings of Twenty-third Annual Joint Conference of the IEEE Computer andCommunications Societies, volume 1, Hong Kong, China, 2004.
[107] Li N, Hou J, Sha L. Design and analysis of an MST-based topology control algorithm. IEEETransactions on Wireless Communications, 2005, 4(3):1195– 1206.
[108] Li L, Halpern J Y, Bahl P, et al. A cone-based distributed topology-control algorithm forwireless multi-hop networks. IEEE/ACM Transactions on Networking, 2005, 13(1):147–159.
[109] Poduri S, Pattem S, Krishnamachari B, et al. Sensor Network Configuration and the Curseof Dimensionality. Proceedings of in The Third IEEE Workshop on Embedded NetworkedSensors, 2006.
[110] Heinzelman W, Chandrakasan A, Balakrishnan H. An application-specific protocol architecturefor wireless microsensor networks. Wireless Communications, IEEE Transactionson, 2002, 1(4):660– 670.
[111] Younis O, Fahmy S. Distributed clustering in ad-hoc sensor networks: a hybrid, energyefficientapproach. Proceedings of Twenty-third Annual Joint Conference of the IEEE Computerand Communications Societies, Hong Kong, China, 2004. 1– 12.
[112] Xu Y, Heidemann J, Estrin D. Geography-informed energy conservation for Ad Hoc routing.Proceedings of the 7th annual international conference on Mobile computing and networking,2001.
[113] Deb B, Bhatnagar S, Nath B. Multi-resolution state retrieval in sensor networks. Proceedingsof the First IEEE International Workshop on Sensor Network Protocols and Applications,2003. 19– 29.
[114] Schurgers C, Tsiatsis V, Srivastava M. STEM: Topology management for energy efficientsensor networks. Proceedings of IEEE Aerospace Conference, Big Sky Kauai, USA, 2002.1099–1108.
[115] Cormen T H, Leiserson C E, Rivest R L. Introduction to Algorithms. MIT Press andMcGraw-Hill, 1990: 558–565.
[116] Schonfisch B, Roos A. Synchronous and asynchronous updating in cellular automata.Biosystems, 1999, 51(3):123– 143.
[2] Zimmermann H. OSI Reference Model: The ISO Model of Architecture for Open SystemsInterconnection. IEEE Transactions on Communications, 1980, 28(4):425–432.
[3] Huston G, Michaelson G. RFC 5396: Textual Representation of Autonomous System (AS)Numbers. The Internet Society, 2008.
[4]吴建平，吴茜，徐恪．下一代互联网体系结构基础研究及探索．计算机学报，2008，31(9)：1536-1548．
[5] Wawrzoniak M, Peterson L, Roscoe T. Sophia: an Information Plane for networked systems.ACM SIGCOMM Computer Communication Review, 2004, 34(1):15–20.
[6] Poslad S. Ubiquitous Computing Smart Devices, Smart Environments and Smart Interaction.Wiley, 2009.
[7]袁坚，王钺．网络发展及其更广泛的安全需求．中国电子科学研究院学报，2008，3(6)：551-557．
[8] Kephart J O, Chess DM. The Vision of Autonomic Computing. Computer, 2003, 36:41–50.
[9] Thomas R, Friend D, DaSilva L, et al. Cognitive Networks. Cognitive Radio, SoftwareDefined Radio, and Adaptive Wireless Systems, 2007. 17–41.
[10] DiMario M. System of systems interoperability types and characteristics in joint commandand control. System of Systems Engineering, 2006, 1:6–10.
[11] ITU. ITU Internet Reports 2005: The Internet of Things. Technical report, November, 1995.http://www.itu.int/internetofthings/.
[12] IBM. 22 opportunities for a smarter planet. Technical report, 2009.
[13]石军．“感知中国”促进中国物联网加速发展．通信管理与技术，2009，9(5)：1-3．
[14] Future Army Applications National Research Council C. Network Science. The NationalAcademies Press, 2006.
[15] Akyildiz I, Su W, Sankarasubramaniam Y, et al. A survey on sensor networks. CommunicationsMagazine, IEEE, 2002, 40(8):102– 114.
[16]于海斌，曾鹏等．智能无线传感器网络系统．科学出版社，2006：1-3．
[17] Callaway E. Wireless Sensor Network: Architecture and Protocols. CRC Press LLC, 2004.
[18]任丰原，黄海宁，林闯．无线传感器网络．软件学报，2003，14(7)：1282-1291．
[19] Estrin D, Govindan R, Heidemann J. Next century challenges: Scalable coordinate in sensornetwork. Proceedings of the 5th ACM/IEEE International Conference on Mobile Computingand Networking., Seattle: IEEE Computer Society, 1999.
[20] Cerf V, Burleigh S, Hooke A. DTN Research Group Internet Draft: Delay-Tolerant NetworkArchitecture. Technical report, 2003.
[21] Burleigh S, Hooke A, Torgerson L, et al. Delay-tolerant networking: an approach to interplanetaryInternet. IEEE Communications Magazine, 2003, 41(6):128– 136.
[22] Juang P, Oki H, Wang Y, et al. Energy-efficient computing for wildlife tracking: designtradeoffs and early experiences with ZebraNet. SIGOPS Operating Systems Review, 2002,36(5):96–107.
[23] Shah R, Roy S, Jain S, et al. Data MULEs: modeling a three-tier architecture for sparsesensor networks. Proceedings of the First IEEE International Workshop on Sensor NetworkProtocols and Applications, 2003. 30– 41.
[24] Pentland A, Fletcher R, Hasson A A. A Road to Universal Broadband Connectivity. Proceedingsof the 2nd International Conference of Open Collaborative Design for SustainableInnovation, 2002. 1–9.
[25]张学，陆桑璐，陈贵海，等．无线传感器网络的拓扑控制．软件学报，2007，18(4)：943 954．
[26]孙立民，李建中等．无线传感器网络．清华大学出版社，2005．
[27] Meguerdichian S, Koushanfar F, Potkonjak M, et al. Coverage problems in wireless ad-hocsensor networks. Proceedings of Twentieth Annual Joint Conference of the IEEE Computerand Communications Societies, 2001. 1380–1387.
[28] Cardei M, Wu J. Handbook of Sensor Networks:Compact Wireless and Wired SensingSystems. CRC Press, 2005.
[29] Li X Y,Wan P J, Frieder O. Coverage in wireless ad hoc sensor networks. IEEE Transactionson Computers, 2003, 52(6):753– 763.
[30] Megerian S, Koushanfar F, Potkonjak M, et al. Worst and best-case coverage in sensornetworks. IEEE Transactions on Mobile Computing, 2005, 4(1):84– 92.
[31] Liu B, Towsley D. A study of the coverage of large-scale sensor networks. Proceedings ofIEEE International Conference on Mobile Ad-hoc and Sensor Systems, 2004. 475– 483.
[32] Kumar S, Lai T, Balogh J. On k-coverage in a mostly sleeping sensor network. WirelessNetworks, 2008, 14(3):277–294.
[33] Wan P J, Yi C W. Coverage by randomly deployed wireless sensor networks. IEEE Transactionson Information Theory, 2006, 52(6):2658–2669.
[34] Tian D, Georganas N D. A coverage-preserving node scheduling scheme for large wirelesssensor networks. Proceedings of the 1st ACM international workshop on Wireless sensornetworks and applications, New York, NY, USA: ACM, 2002. 32–41.
[35] Ye F, Zhong G, Cheng J, et al. PEAS: A Robust Energy Conserving Protocol for LonglivedSensor Networks. Proceedings of International Conference on Distributed ComputingSystems, Los Alamitos, CA, USA: IEEE Computer Society, 2003. 28–37.
[36] Shakkottai S, Srikant R, Shroff N. Unreliable sensor grids: coverage, connectivity and diameter.Proceedings of Twenty-Second Annual Joint Conference of the IEEE Computer andCommunications, 2003. 1073– 1083.
[37] Meguerdichian S, Koushanfar F, Qu G, et al. Exposure in wireless Ad-Hoc sensor networks.Proceedings of the 7th annual international conference on Mobile computing and networking,New York, NY, USA: ACM, 2001. 139–150.
[38] Clouqueur T, Phipatanasuphorn V, Ramanathan P, et al. Sensor deployment strategy fortarget detection. Proceedings of the 1st ACM international workshop on Wireless sensornetworks and applications, New York, NY, USA: ACM, 2002. 42–48.
[39] Hata M. Empirical formula for propagation loss in land mobile radio services. IEEE Transactionson Vehicular Technology, 1980, 29(3):317– 325.
[40] Hall P. Introduction to the Theory of Coverage Processes. John Wiley & Sons Inc, 1988.
[41] Lazos L, Poovendran R. Stochastic coverage in heterogeneous sensor networks. ACMTransactions on Sensor Networks, 2006, 2(3):325–358.
[42] Ram S, Majunath D, Iyer S, et al. On the Path Coverage Properties of Random SensorNetworks. IEEE Transactions on Mobile Computing, 2007, 6(5):494–506.
[43] Manohar P, Ram S S, Manjunath D. Path coverage by a sensor field: The nonhomogeneouscase. ACM Transactions on Sensor Networks, 2009, 5(2):1–26.
[44] Ghrist R, Muhammad A. Coverage and hole-detection in sensor networks via homology.Proceedings of the 4th international symposium on Information processing in sensor networks,Piscataway, NJ, USA: IEEE Press, 2005. No.34.
[45] Silva V, Ghrist R, Muhammad A. Blind swarms for coverage in 2-d. Proceedings ofRobotics: Science and Systems, 2005. 1–8.
[46] Kar K, Banerjee S. Node Placement for Connected Coverage in Sensor Networks. Proceedingsof Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2003.
[47] Slijepcevic S, Potkonjak M. Power efficient organization of wireless sensor networks. Proceedingsof IEEE International Conference on Communications, 2001. 472–476.
[48] Ye F, Zhong G, Zhang L. Energy Efficient Robust Sensing Coverage in Large Sensor Networks.Technical report, Technical Report UCLA, 2002.
[49] Zhang H, Hou J. Maintaining Sensing Coverage and Connectivity in Large Sensor Networks.Technical Report UIUCDCS-R-2003-2351, Technical Report UIUC, 2003.
[50] Wang X, Xing G, Zhang Y, et al. Integrated coverage and connectivity configuration inwireless sensor networks. Proceedings of the 1st international conference on Embeddednetworked sensor systems, New York, NY, USA: ACM, 2003. 28–39.
[51] Cardei M, Du D Z. Improving wireless sensor network lifetime through power aware organization.Wireless Networks, 2005, 11(3):333–340.
[52] Wu K, Gao Y, Li F, et al. Lightweight Deployment-Aware Scheduling for Wireless SensorNetworks. Mobile Networks and Applications, 2005, 10(6):837–852.
[53]田乃硕，徐秀丽，马占友．离散时间排队论．科学出版社，2008．
[54]陆大.随机过程及其应用．清华大学出版社，2007．
[55] Serfozo R. Introduction to Stochastic Networks. Springer, July, 1999.
[56] Chen H, Yao D D. Fundamentals of queueing networks : performance, asymptotics, andoptimization. Springer, 2001.
[57] Hughes B D. Random walks and random environments. Oxford University Press, 1996.
[58] Broch J, Maltz D, Johnson D, et al. A performance comparison of multi-hop wireless adhoc network routing protocols. Proceedings of the Fourth Annual ACM/IEEE InternationalConference on Mobile Computing and Networking, Dallas, Texas, USA: ACM, 1998. 85–97.
[59] Bai F, Helmy A. A Survey of Mobility Models in Wireless Adhoc Networks (Chapter 1 inWireless Ad-Hoc Networks). Kluwer Academic, 2006.
[60] Hanashi A M, Awan I, Woodward M. Performance evaluation with different mobility modelsfor dynamic probabilistic flooding in MANETs. Mobile Information Systems, 2009,5(1):65–80.
[61]chopard B，Droz M，祝玉学等(译)．物理系统的元胞自动机模拟．清华大学出版社，2003．
[62] Mange D, Madon D, Stauffer A, et al. Von Neumann revisited: A Turing machine withself-repair and self-reproduction properties. Robotics and Autonomous Systems, 1997,22(1):35–58.
[63] Eliasmith C. The myth of the Turing machine: the failings of functionalism and relatedtheses. Journal of Experimental and Theoretical Artificial Intelligence, 2002, 14(1):1–8.
[64] Smillie K. Turing and the universal machine: The making of the modern computer. IEEEAnnals of the History of Computing, 2002, 24(2):95–95.
[65] Brackenbury I, Ravin Y. Machine intelligence and the Turing Test. IBM Systems Journal,2002, 41(3):524–529.
[66]贾斌，高自友等．基于元胞自动机的交通系统建模与模拟．科学出版社，2007．
[67] Vollmar R. John von Neumann and self-reproducing cellular automata. Journal of CellularAutomata, 2006, 1(4):353–376.
[68] Kazakov D, Sweet M. Evolving the game of life. Lecture Notes in Computer Science, 2005,3394:132–146.
[69] Langton C. Self-reproduction in cellular automata. Physica D, 1984, 10(1-2):135–144.
[70] Byl J. Selft-reproduction in small cellular automata. Physica D, 1989, 34(1-2):295–299.
[71] Taylor C, Langton C, Kitano H. Editor’s introduction: Special issue on highlights of theAlife VI Conference. Artif Life, 1998, 4(1):III–III.
[72] Wolfram S. 20 Problems in the theory of cellular automata. Phys Scripta, 1985, T9:170–183.
[73] Wolfram S. Cryptography with cellular automata. Lecture Notes in Computer Science,1986, 218:429–432.
[74] Wolfram S. Cellular automata as models of complextiy. Nature, 1984, 311(5985):419–424.
[75] Wolfram S. Universality and complexity in cellular automata. Physica D, 1984, 10(1):1–35.
[76] Wolfram S. Cellular automaton fluids: Basic theory. Journal of Statistical Physics, 1986,45(3-4):471–526.
[77] Wolfram S. Random sequence generation by cellular automata. Advances in Applied Mathematics,1986, 7(2):123–169.
[78] Wolfram S. Computation theory of cellular automata. Communications in MathematicalPhysics, 1984, 96(1):15–57.
[79] Chen S, Chen H, Martinez D, et al. Lattice boltzmann model for simulation of magnetohydrodynamics.Physical Review Letters, 1991, 67(27):3776–3779.
[80] Mattila K, Hyvaeluoma J, Timonen J, et al. Comparison of implementations of the lattice-Boltzmann method. Computers and Mathematics with Applications, 2008, 55(7):1514–1524.
[81] Benzi R, Succi S, Vergassola M. The lattice boltzmann-equation - theory and applications.Physics Reports, 1992, 222(3):145–197.
[82] Packard N, Wolfram S. Two-dimensional cellular automata. Journal of Statistical Physics,1985, 38(5-6):901–946.
[83] Dubacq J, Durand B, Formenti E. Kolmogorov complexity and cellular automata classification.Theoretical Computer Science, 2001, 259(2):271–285.
[84] Hurd L, Kari J, Culik K. The topological-entropy of cellular automata is umcomputable.Ergodic Theory and Dynamical Systems, 1992, 12:255–265.
[85] Voorhees B. Entropy of additive cellular automata. International Journal of TheoreticalPhysics, 1989, 28(11):1387–1396.
[86] Meyerovitch T. Finite entropy for multidimensional cellular automata. Ergodic Theory andDynamical Systems, 2008, 28:1243–1260.
[87] Akin H. The topological entropy of invertible cellular automata. Journal of Computationaland Applied Mathematics, 2008, 213(2):501–508.
[88] Gin A, Tougaw P, Williams S. An alternative geometry for quantum-dot cellular automata.Journal of Applied Physics, 1999, 85(12):8281–8286.
[89] Makowiec D. New challenges in cellular automata due to network geometry - Ferromagnetictransition study. Journal of Cellular Automata, 2006, 1(4):299–315.
[90] Jin X, Kim T. Classification of cellular automata and complexity. International Journal ofModern Physics B, 2003, 17(22-24):4232–4237.
[91] Sutner K. The computational complexity of cellular automata. Lecture Notes in ComputerScience, 1989, 380:451–459.
[92] Gordon D. On the computational power of totalistic cellular automata. Mathematical SystemsTheory, 1987, 20(1):43–52.
[93] Hansen P. Parallel cellular-automata: a model program for computational science. Concurrency:Practice and Experience, 1993, 5(5):425–448.
[94] Marr C, Hutt M. Topology regulates pattern formation capacity of binary cellular automataon graphs. Physica A, 2005, 354:641–662.
[95] Manzini G, Margara L. A complete and efficiently computable topological classificationof D-dimensional linear cellular automata over Z(m). Theoretical Computer Science, 1999,221(1-2):157–177.
[96] Burkhead E G. A topological classification of D-dimensional cellular automata. Dynamicalsystem, 2009, 24(1):45–61.
[97] Serra R, Villani M. Perturbing the regular topology of cellular automata: Implications forthe dynamics. Lecture Notes in Computer Science, 2002, 2493:168–177.
[98] Culik K, Hurd L, Yu S. Computation theoretic aspects of cellular automata. Physica D,1990, 45(1-3):357–378.
[99]谢惠民．复杂性与动力系统．上海科技教育出版社，1994．
[100] Cerpa A, Estrin D. ASCENT: Adaptive Self-Configuring sEnsor Networks Topologies.Proceedings of Twenty-First Annual Joint Conference of the IEEE Computer and CommunicationsSocieties, New York, USA, 2002. 1278– 1287.
[101]周成虎，孙战利等．地理元胞自动机研究．科学出版社，2000．
[102] Sesic A, Dautovic S, Malbasa V. Dynamic Power Management of a System With aTwo-Priority Request Queue Using Probabilistic-Model Checking. IEEE Transactions onComputer-Aided Design of Integrated Circuits and Systems, 2008, 27(2):403– 407.
[103] Park C W, Noh K W, Kim S Y. A new scheduling technique based on Dynamic VoltageScaling for MPSoC. Proceedings of International SoC Design Conference, Busan, Korea,2008. 73–76.
[104] Kirousis L M, Kranakis E, Krizanc D, et al. Power consumption in packet radio networks.Theoretical Computer Science, 2000, 243(1-2):289– 305.
[105] Kubisch M, Karl H,Wolisz A, et al. Distributed algorithms for transmission power control inwireless sensor networks. Proceedings of IEEEWireless Communications and Networking,New orleans, LA, USA, 2003. 558– 563.
[106] Li N, Hou J. Topology control in heterogeneous wireless networks: problems and solutions.Proceedings of Twenty-third Annual Joint Conference of the IEEE Computer andCommunications Societies, volume 1, Hong Kong, China, 2004.
[107] Li N, Hou J, Sha L. Design and analysis of an MST-based topology control algorithm. IEEETransactions on Wireless Communications, 2005, 4(3):1195– 1206.
[108] Li L, Halpern J Y, Bahl P, et al. A cone-based distributed topology-control algorithm forwireless multi-hop networks. IEEE/ACM Transactions on Networking, 2005, 13(1):147–159.
[109] Poduri S, Pattem S, Krishnamachari B, et al. Sensor Network Configuration and the Curseof Dimensionality. Proceedings of in The Third IEEE Workshop on Embedded NetworkedSensors, 2006.
[110] Heinzelman W, Chandrakasan A, Balakrishnan H. An application-specific protocol architecturefor wireless microsensor networks. Wireless Communications, IEEE Transactionson, 2002, 1(4):660– 670.
[111] Younis O, Fahmy S. Distributed clustering in ad-hoc sensor networks: a hybrid, energyefficientapproach. Proceedings of Twenty-third Annual Joint Conference of the IEEE Computerand Communications Societies, Hong Kong, China, 2004. 1– 12.
[112] Xu Y, Heidemann J, Estrin D. Geography-informed energy conservation for Ad Hoc routing.Proceedings of the 7th annual international conference on Mobile computing and networking,2001.
[113] Deb B, Bhatnagar S, Nath B. Multi-resolution state retrieval in sensor networks. Proceedingsof the First IEEE International Workshop on Sensor Network Protocols and Applications,2003. 19– 29.
[114] Schurgers C, Tsiatsis V, Srivastava M. STEM: Topology management for energy efficientsensor networks. Proceedings of IEEE Aerospace Conference, Big Sky Kauai, USA, 2002.1099–1108.
[115] Cormen T H, Leiserson C E, Rivest R L. Introduction to Algorithms. MIT Press andMcGraw-Hill, 1990: 558–565.
[116] Schonfisch B, Roos A. Synchronous and asynchronous updating in cellular automata.Biosystems, 1999, 51(3):123– 143.