史 倢，陈 志，2，3，* ，章 韵，扈罗全，岳文静

(1.南京邮电大学计算机学院，南京 210003； 2.南京大学计算机软件新技术国家重点实验室，南京 210093； 3.江苏省无线传感网高技术研究重点实验室，南京 210003； 4.宽带无线通信与传感网技术教育部重点实验室，南京 210003； 5.苏州出入境检验检疫局，江苏苏州 215104)

无线传感器网络是一种由大量传感器节点组成，通过无线方式协作地检测、感知和处理各种环境或者检测对象信息的网络系统［1－3］，传感器网络节点通常由电池供电，通信、计算、处理能力有限，对该网络进行拓扑控制的目标是寻找一种节点的配置方法，在减少系统能量消耗的前提下，保证整个网络拓扑的连通性和覆盖性。

元胞自动机(Cellular automata)作为状态离散系统，能够以简单的规则揭示复杂的全局特性，因而成为研究自组织时空演化规律的重要工具［4］。文献［5］将元胞自动机作为一种模拟无线传感器网络行为的工具，认为无线传感器网络节点之间具有的高度协作性，形成类似于元胞自动机所模拟的大部分动力学系统。文献［6］在无线传感器网络的元胞自动机模型基础上，提出一种节点可动态调节通信范围的方法。文献［7］通过建立无线传感器网络的二维元胞自动机模型，分析节点状态规则和网络拓扑覆盖性与连通性的关系，并将无线传感器网络的整体拓扑特性初步归纳为震荡、衰减、稳定等基本模式。

上述研究将无线传感器网络平面看成是按照正方形网络排列的二维元胞空间，每个格点对应一个传感器节点，具有工作和休眠两种状态。邻居定义为与元胞相邻的8个元胞，即Moore型邻居［8］。每个元胞根据邻居状态的变化改变自身状态。通常情况下，传感器节点由随机散布方式部署，并非规则分布，并且节点自身能量有限，随着网络的运行，可能因为能量耗尽而失效。因此，本文在此基础上扩展元胞状态为3种，即元胞处无节点对应/节点失效、节点休眠、节点工作，元胞以随机方式部署，寻找元胞最优状态演化规则，以实现在保证网络覆盖率和连通度的前提下减少能耗。

1 基于元胞自动机的拓扑控制模型

1.1 元胞自动机模型

以Conway的生命游戏［9］为例，生命游戏描述的是生物群体的生存繁殖规律:在生命密度过小时，由于孤单使生物体缺乏配种繁殖机会、缺乏互助导致生命危机，生物体由生变为死；在生命密度过大，由于资源缺乏、相互竞争也会出现生存危机，生物体也由生变为死；只有处于个体适中状态的生物才能生存并繁衍后代［4］。

用元胞自动机模型表示为:

(1)元胞分布于规则划分的二维网格上；

(2)元胞具有两种状态:0死，1生；

(3)元胞的状态由上一时刻自身的状态和邻居状态决定，邻居为与元胞相邻的8个元胞；

(4)演化规则用数学表示为S23/B3，即:

1.2 无线传感器网络的元胞自动机模型

无线传感器网络运行状态类似于生命游戏，如果利用网络中的所有节点进行监测会产生冗余，也就是说，在同一时刻会有2个或2个以上的节点监测同一个区域，不仅浪费能源，而且在传输数据包的过程中会产生碰撞和阻塞；如果节点周围邻居过少，那么节点也会因为负载过大、能量耗尽而失效。因此节点的工作/休眠机制成为节省能耗、延长网络寿命的一种有效手段。工作/休眠机制即在合适的时间［10－13］关闭节点发射器，让其进入睡眠状态，以大幅减小能量消耗。

本文考虑无线传感器网络节点经部署初始化后有三种状态:工作、休眠、失效(或空位)。传感器节点具有固定的工作/休眠周期，即当工作(休眠)一定时间T后进入休眠(工作)状态。每个传感器节点具有一定的初始能量E0，当处于工作状态时，打开发射器进行接收、转发、监听等操作，因此需要消耗大量的能量Ew，当其处于休眠状态时，关闭发射器进入低功率状态，消耗较少的能量Es，随着网络的运行，节点工作、休眠状态交替改变，能量耗尽，节点失效，则节点状态变为失效。由于该方法随机性较大，可能随着部分节点的失效导致网络的覆盖率、连通度下降，影响网络的整体性能。因此，需要节点之间具有高度的协作性，节点在固定的时间段检测邻居状态，在保证自己监测的区域内已有足够的节点监测后再进入休眠，同样，处于休眠状态的节点发现该区域内工作节点不足时，及时醒过来进入工作状态。

基于二维元胞自动机的无线传感器网络模型叙述如下:

(1)元胞状态集S={0，1，2}，0 表示无节点/节点失效，1表示节点处于休眠状态；2表示节点处于工作状态。

(2)元胞邻居集合N定义为节点功率半径R范围内所有节点(包括边界)。

(3)每个元胞的状态由上一时刻邻居元胞状态以及自身状态决定。具体演化规则如下:

如果元胞在t时刻为2，且其邻居状态为2的个数为Ni，那么t+Δt时刻元胞状态不变；

如果元胞在t时刻为1，且其邻居状态为2的个数为Nj，那么t+Δt时刻元胞状态改变为2。

上述规则中:Δt表示一个时间间隔；Ni和Nj是选择最优演化规则的两个常量，表示最佳邻居节点个数。

2 基于元胞自动机的拓扑控制方法

2.1 方法流程

根据无线传感器网络的元胞自动机模型，可以建立基于元胞自动机的拓扑控制方法，首先做两点假设:

(1)假设传感器网络为同质网络，即所有节点的大小、形状、结构以及具有的初始能量相同。

(2)假设通信模块的发送半径和接收半径相同。

在上述假设条件下，基于元胞自动机的拓扑控制流程如下:

(1)在规模为L元胞空间内随机部署N个状态非0的元胞，令其中70%的元胞状态为1(休眠)。所有元胞具有固定的工作/休眠周期选择工作或休眠，令该周期为T=kΔt。

(2)在每个时间间隔Δt中，元胞根据上述模型中的演化规则改变自身状态，即由上一时刻邻居元胞状态和元胞自身状态决定。

(3)每个元胞具有一定的初始能量E0，每个时间间隔Δt中，元胞状态为工作时消耗能量Ew，元胞处于休眠状态(也称低功耗状态)时消耗较少的能量Es，当元胞能量全部消耗后，元胞失效。

上述流程中，规模L、节点个数N、时间间隔Δt、工作/休眠周期T、元胞初始能量E0、工作状态消耗能量Ew、休眠状态消耗能量Es等参数可根据实际应用情况进行选择。

2.2 评价参数

为评价基于元胞自动机的无线传感器网络拓扑控制方法性能，定义如下二维元胞模型的拓扑特性:

(1)覆盖率

不考虑边界节点覆盖面积的减少，每个传感器节点的通信半径为R，那么一个节点的覆盖概率为p=πR2/L2。

令一个节点的覆盖概率为p(A)=p，那么两个节点的覆盖概率为

依次，n个节点的覆盖概率为

(2)连通度

无线传感器网络作为信息收集系统，需要实现多跳的信息传输，在元胞自动机模型中表现为活着的元胞拥有活着的邻居［6］。处于工作状态元胞的邻居中无处于工作状态的元胞，则对网络连通率的贡献为0。所以，连通度表示为区域内(所有工作节点个数－邻居节点未处于工作状态的工作节点个数)/所有工作节点个数。

(3)能耗指数

某一时刻工作节点占所有节点的比重表示网络该时刻的能耗指数。能耗指数越高，说明该时刻工作节点个数越多，能量消耗越大。

3 仿真分析

我们利用MATLAB进行仿真研究，定义元胞自动机的规模为L，初始元胞总数为L2，试验中取L=50。根据实际网络特点，采用周期性边界条件。网络初始化为随机部署750个元胞，即令30%的元胞状态为1，并在所有状态为1的元胞中以30%概率取2。元胞半径R=3。取Δt为1个时间步，连续工作/休眠周期为3个时间步，元胞初始能量为0.8 J，每个时刻中，工作状态消耗能量0.016 5 J，休眠状态消耗能量0.000 08 J。仿真研究两个方面内容:①研究在不同的局部更新规则下，系统的覆盖率、连通度和能耗指数的时间演化特征；②研究基于元胞自动机的无线传感器网络拓扑控制方法与节点随机部署后采用随机休眠/工作机制下的拓扑特性。

3.1 最佳局部更新规则

在不同的规则下，系统呈现出复杂的时空演化特性。图1所示为采用S34/B23规则下的网络覆盖率和连通度的变化情况。从图1可见，系统的覆盖率和连通度经过有限次震荡以后逐步趋于稳定，说明在此网络状态下，当每个传感器节点处于工作状态的邻居数为3或4时，网络能够通过一定时间的自适应调节后保持一个相对稳定的拓扑状态。当处于工作状态的邻居数大于4或小于3个时，测试显示覆盖率和连通度始终处于震荡状态，说明网络中工作节点的密度不均衡，造成网络覆盖率和连通度周期震荡，影响网络的整体性能。另外，从图中可以看出，当休眠概率保持在70%左右时(即保持网络中30%的节点处于工作状态)，即可保证网络具有良好的覆盖率和连通度。

图1 规则S34/B23下网络覆盖率和连通度的变化情况

3.2 基于元胞自动机的拓扑控制方法

如图2所示，当系统运行至100步时，采用随机休眠/工作机制的网络中节点能量完全耗尽，而基于元胞自动机方法的网络中运行到110步时才逐渐有节点失效，剩余节点数开始逐渐减少，基于元胞自动机方法的网络寿命比随机休眠/工作机制的网络寿命延长80%左右。

图2 两种方法随时间变化剩余节点数和能耗指数的变化情况

图3 两种方法随时间变化休眠概率、覆盖率、连通度的变化情况

图3给出节点休眠概率、覆盖率和连通度的变化情况。图3(a)中随机工作/休眠机制节点休眠，图3(b)、3(c)所示采用元胞自动机方法的网络覆盖率和连通度有小幅度的震荡，但基本都在90%左右，说明网络能够较好地自适应调整其拓扑状态。相对于定时工作/休眠的情况而言，基于元胞自动机的拓扑控制方法在没有影响网络覆盖率和连通度的前提下，减少了网络系统能耗，延长了网络运行寿命。

4 结束语

拓扑控制是研究实现无线传感器网络能量高效利用的主要技术之一，工作/休眠机制是拓扑控制研究中一个重要的部分。利用元胞自动机对无线传感器网络进行建模，有利于研究与控制节点间相互作用导致的网络拓扑动态变化。本文在随机休眠/工作机制的基础上，提出了一种适用于一般性无线传感器网络的元胞自动机模型，建立了基于该模型的拓扑控制方法，仿真表明该方法在保证网络覆盖率的前提下减少了能量消耗，延长了网络寿命。

在今后的工作中，我们将结合更多问题，考虑与其他拓扑控制算法进行比较，进一步深化元胞自动机在无线传感器网络中的应用。另外，元胞自动机在无线传感器网络中的应用多针对同质网络，今后的研究可以扩展多层次的元胞自动机模型以实现异质网络拓扑控制。

［1］王殊，阎毓杰，胡富平，等.无线传感器网络的理论及应用［M］.北京:北京航空航天大学出版社，2007.7.

［2］陈志，史倢，章韵，等.基于Agent的无线传感器网络AUML交互模型［J］.传感技术学报，2010，23(11):1617－1622.

［3］章韵，王静玉，陈志，等.基于Q学习的无线传感器网络自组织方法研究［J］.传感技术学报，2010，23(11):1623－1626.

［4］贾斌，高自友，李克平，等.基于元胞自动机的交通系统建模与模拟［M］.北京:科学出版社，2007.

［5］Cunha R O，Silva A P，Loreiro A F F，et al.Simulating Large Wireless Sensor Networks Using Cellular Automata［C］//IEEE Proceedings of the 38th Annual Simulation Symposium，April 2005:323－330.

［6］Sepideh Adabi，Ahmad Khadem Zadeh，Arash Dana，et al.Cellular Automata Based Method for Energy Conservation Solution in Wireless Sensor Network［J］.Wireless Communications，Networking and Mobile Computing，2008:1－5.

［7］张文铸，袁坚，俞哲，等.基于元胞自动机的无线传感器网络整体行为研究［J］.物理学报，2008，57(11):6896－6900.

［8］Jarkko Kari.Theory of Cellular Automata:A Survey［J］.Theoretical Computer Science，2005.334(1－3):3－33.

［9］Gardner M.The Fantastic Combination of John Conway’s New Solitaire Game Life［J］.Scientific American，1970，220(4):120－123.

［10］Ye F，Zhong G，Lu S，et al.PEAS:A Robust Energy Conserving Protocol for Long-Lived Sensor Networks［C］//Proceeding of the 23rd International Conference on Distributed Computing Systems，2003:28－37.

［11］Yan T，He T，Stankovic J A.Differentiated Surveillance for Sensor Networks［C］//Proceeding of the First ACM Conference on Embedded Networked Sensor Systems(Sensys03)，2003:51－62.

［12］Wang X，Xing G，Zhang Y，et al.Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks［C］//Proceeding of ACM SIGMOBILE International Conference on Embedded Networked Sensor Systems(SenSys 2003)，Los Angeles，CA，USA，2003:28－39.

［13］石高涛，廖明宏.大规模传感器网络随机睡眠调度节能机制［J］.计算机研究与发展，2006，43(4):579－585.

［14］孙永进，孙雨耕，房朝晖.无线传感器网络的连通与覆盖［J］.天津大学学报，2005，38(1):14－17.