无线传感器网络的建立如图 1所示。首先，传感器节点被部署在感兴趣的区域，如图 1a和图 1b所示。节点的部署方式为：在特定区域，从飞机上投下大量的传感器节点，或者在这片区域，采用人工手动或机器人的方式来放置节点。节点能够通过定位算法发现自己的位置(如图 1c所示)且自组织成为无线网络(如图 1d所示)。

图  1  无线传感器网络

由于传感器的放置位置没有基础结构，节点之间的邻居关系未知。所以传感器节点需要具备自组织能力进行自我配置和管理，通过拓扑控制机制和网络协议自动形成多跳无线网络系统^[4]。

元胞自动机的核心元素包括：元胞空间、节点状态集、节点邻居集和节点状态转换规则，即元胞自动机可以由四元组$A = \{ {L_d}, S, N, f\} $定义，其中：

1) L表示元胞空间。元胞在空间中分布的空间格点的集合就是元胞空间，它是规则的网格，构成这个网格的要素被称为元胞；d表示元胞空间的维数(本文使用二维元胞自动机模型，即d=2)；

2) S表示元胞的有限状态离散集合，可以是二进制形式或在一个有限整数集内取值；

3) N表示包括中心元胞在内的所有邻域内元胞的组合，有冯·诺依曼型、摩尔型、扩展摩尔型等3种；

4) f表示状态转换规则的函数。某个元胞的下一时刻状态仅由邻居的状态及其初始状态决定。设t时刻元胞${C_{i, j}}$的状态为$S_{i, j}^t$，其邻居状态之和定义为：

对于任意元胞${C_{i, j}}$，局部状态转移规则f：

一个二维元胞自动机是一个离散的动力学系统，该系统中，$L \times L$个独立的被称为元胞的对象以一种独特的方式排列在二维元胞空间中。每一个元胞被赋予一个状态(来自一个有限状态集S)，且该状态根据一定的转换规则随时间变化。

元胞自动机模型只是一种建模框架，而不是具体的模拟模型。因此，在构建面向无线传感网络的二维元胞自动机模型时，针对传感器节点的空间分布和局部交互特征，将无线传感网和传统的二维元胞自动机模型进行正确的关系映射是建模的关键所在。本文假设在一个包含$L \times L$个格子单元的规则的二维网格中被随机地放置N个静态独立的传感节点，网格即代表一个二维元胞空间，一个传感节点就对应于该元胞空间中的一个元胞。由于传感器节点的空间分布和局部交互特征，本文通过定义元胞空间中的元胞状态、元胞邻居和状态转换规则集等模型要素，从而建立能较为准确刻画无线传感网络拓扑形成及时空特性的二维元胞自动机模型。

如前所述的无线传感网络通信模型，为降低分析的复杂度，假设网格单元最多包含一个传感节点。该平面无线传感器网络构成元胞空间，传感器节点是元胞空间中的元胞。空间中任何节点的位置可以由二维网格中的水平坐标i和垂直坐标j唯一标识。${C_{i, j}}$表示(i, j)坐标处的节点或元胞。元胞空间记为：

每个节点都有一个最大通信距离${R_c}$，由信号强度的路径衰减控制。${R_c}$定义了二维元胞模型中的邻居关系。定义节点邻域为摩尔型结构，在设定的模型中，节点${C_{i, j}}$的通信邻居集合${N_{i, j}}$定义为：

本文认为传感器节点采用S-MAC协议，即每个节点在每个循环周期中拥有两个工作阶段：活跃/睡眠阶段。节点自身处于什么状态是由唤醒规则来决定的：当处于活跃状态时，检测周围环境并执行必要的处理；当处于睡眠状态时，节点进入睡眠状态达到节能的目的。定义包含N个元胞的状态向量$S = \{ {S_{i, j}} \in \{ 0, 1\} |{C_{i, j}} \in L\} $，其中${S_{i, j}}$表示节点${C_{i, j}}$的状态，0和1分别表示该节点处于休眠或活跃状态。

状态转换为无线传感器网络的元胞自动机自组织算法的核心，转换规则决定了节点下一时刻是活跃还是休眠，对降低能量消耗、网络覆盖度、连通度有直接的影响。具体规则将在下面介绍。

为了评价本文的无线传感网的元胞自动机自组织算法，定义6个面向无线传感器网络的二维元胞自动机模型的性能指标：

网络总能量：在特定时间点，所有节点所含剩余能量的总和；连通度：活跃的节点有活跃的邻居；覆盖度：在特定时间点，所有活跃节点监测区域所占的百分比；存活的传感器总数：在特定时间点，还有剩余能量的传感器总数；网络生存时间：从仿真开始到所有节点能量耗尽所经过的时间；系统耗能指数：在特定时间点，所有处于活跃状态的节点数与整个无线传感器网络的节点数的比值，反映系统消耗能量的多少。

无线传感器节点代表元胞自动机中的一个元胞。节点具有以下属性：剩余能量、状态、位置(x, y)和定时器，分别用来确定传感器电池中的剩余能量、节点是处于活跃还是待机状态、节点部署方式中的自组织部署方式。

本文用二维元胞自动机与无线传感器网络对应，元胞空间为二维网格，假定每个节点的邻居数不超过8个，即摩尔型。网格中的一个元胞如果不包含任何节点，则相当于该元胞有一个死亡节点(节点的电池没有剩余能量)。

本文提出的无线传感器网络的元胞自动机自组织算法的伪代码如下：

while网络存活do

for所有节点do

  if节点存活(节点还有剩余能量) then

    if处于活跃状态then

      减少节点的能量(活跃时损耗的能量)

        if节点能量耗尽then

          存活节点数减1

        else if计时器为0 then

        按照转换规则进行状态转换

          重新开始计时

        else

          计时器递减

        end if

      else (处于休眠状态)

      减少节点的能量(休眠时损耗的能量)

        if节点能量耗尽then

          存活节点数减1

        else if计时器为0 then

        按照转换规则进行状态转换

          重新开始计时

      else

        计时器递减

      end if

    end if

  end if

end for

end while

在该算法中，网格中的所有活跃节点都必须进行验证(如果不用定时器，元胞自动机的验证规则会在每个时间单元进行。但在实际网络中，节点的关闭/开启操作是各能源消耗方面比较大的一部分，在仿真中不考虑这一部分消耗)。每个存活的节点都会有随机的一段时间处在待机模式，并且在这段时间后，它会被“唤醒”，然后进行下一次验证。如果在某时刻，节点经过转换规则推出下一时刻为活跃/休眠状态，那么该节点状态将置为活跃/休眠。一段随机时间间隔过后，它将再次执行邻居验证，这个循环会持续到节点能量耗尽为止。

最简单的节点转换规则为所有传感器节点一直处于活跃状态，直至能量耗尽。文献[3]使用生命游戏作为转换规则。文献[5]提出的转换规则是如果传感器节点在某时刻有一个以上的邻居处于活跃状态，则它将自己的下一状态置为待机模式。本文提出的转换规则考虑了传感器节点的剩余能量。WSN节点的能量一般是有限的，但必须要有足够的处于活跃状态的节点来组成网络的主干，现有文献提出的转换规则都是根据邻居节点工作/休眠状态的节点数决定自身下一时刻的状态，没有考虑节点本身以及邻居节点的剩余能量等级状况，这可能会导致节点间剩余能量的不均衡。因此在制定状态转换规则时将剩余能量也考虑其中，使网络尽可能均匀耗能，以求达到更好的网络性能。本文的改进规则为：若节点有一个以上的邻居处于活跃状态，则将自己的状态置为待机模式，否则将根据自己的剩余能量来决定下一状态。

本文假设每个节点有两个可能的状态(活跃或休眠)，8个邻居，因此需要定义256条节点行为规则。在相关文献中，转换规则都只考虑了邻居节点和自身状态，没有考虑节点和本身以及邻居节点的剩余能量等级状况^{[3, 5]}，这可能导致节点间剩余能量的不均衡。

严格意义上的CA只能有一个状态参量，但在实际应用中，可以具有多个状态参量。本文将节点的剩余能量考虑为节点的状态参量。在状态转换规则中，设average_energy代表本节点及邻居节点的平均剩余能量，则有：

式中，E为本节点的剩余能量；$\sum\limits_{n \in N} {{E_n}} $为本节点邻居的总能量；N为邻居节点的个数。

本文考虑的是每个节点的邻居为相邻8个网格中的节点，所以式(5)可以转化为：

本文定义各变量含义如表 1所示。

改进的算法中，用某节点的剩余能量与average_energy的比值作为状态转换的活跃因子，即A=energy_left/average_energy。取值范围(由极限分析)为(0, 9]。rand(1)是服从0~1的均匀分布。所以${\rm{rand}}(1) \times A$服从0~A的均匀分布。A越大，rand(1)A > 0.5的概率也越大，但比值较小时，表示这个节点的剩余能量不多，不会像现有转换规则那样直接转为活跃状态，而是更大概率地处于休眠状态。活跃因子对状态转换的影响如下：

1) 当A < 0.5时：${\rm{rand}}(1) \times A > 0.5$的概率为0，${\rm{rand}}(1) \times A < 0.5$的概率为1；

2) 当A > 0.5时：${\rm{rand}}(1) \times A > 0.5$的概率为${{(A - 0.5)} \mathord{\left/ {\vphantom {{(A - 0.5)} A}} \right. } A} = 1 - {{0.5} \mathord{\left/ {\vphantom {{0.5} A}} \right. } A}$，${\rm{rand}}(1) \times A < 0.5$的概率为${{0.5} \mathord{\left/ {\vphantom {{0.5} A}} \right. } A}$。

综合上面两种情况，定义运算：

在sum_state=0的情况下，节点在下一周期是活跃状态的概率为$p = {(1 - {{0.5} \mathord{\left/ {\vphantom {{0.5} A}} \right. } A})^ + }$，在下一周期是休眠状态的概率为$1 - p = 1 - {(1 - {{0.5} \mathord{\left/ {\vphantom {{0.5} A}} \right. } A})^ + }$。状态转移流程如图 2所示。

图  2  改进算法流程图

节点部署的网格通过二维矩阵实现，网络包含$L \times L$个网格。传感器节点数目为NodeAmount，性能指标完全相同，随机分布在网格中，并假设一个网格单元至多包含一个传感节点。该网格即代表一个二维元胞空间，一个传感节点就对应于该元胞空间中的一个元胞。仿真参数的设置如表 2所示。

每个节点的能量递减函数通过类似于文献[6]中描述的线性函数计算，仿真参数设置^[7]如表 2所示。

网格中的节点状态初始化为0, 1中的一个随机值，之后的运行过程根据提出的基于元胞自动机的无线传感器网络自组织算法进行。

在网络还有存活节点时，每个周期后节点的剩余能量都会根据自身状态减小相应的值。每个节点有一个属性为Node.timer。每个周期内，计时器为0的节点执行一次状态转换规则来决定下一时刻的状态，并重置计时器为随机值，这个循环会持续到节点能量耗尽为止。若节点有一个以上的邻居处于活跃状态，它将自己的状态置为待机模式，否则根据自己的剩余能量多少来决定下一状态。

考虑网络规模为L=100，传感节点数为NodeAmount=5 000，4种转换规则的网络总能量、连通度、覆盖度、存活的传感器总数、系统耗能指数分别如图 3~图 7所示。图 1中用于与改进算法做对比的转换规则1指所有传感器节点一直处于活跃状态，直至能量耗尽；转换规则2指某时刻若传感器节点有一个以上的邻居处于活跃状态，则它将自己的状态置为待机模式^[5]；转换规则3指生命游戏规则^[3]；转换规则4指本文提出的改进转换规则。图 3~图 7为转换规则1~4的5个网络性能指标曲线图。

图  3  网络剩余总能量

图  4  节点间的连通度

图  5  传感器网络的覆盖度

图  6  网络中存活的传感器节点总数

图  7  网络的系统耗能指数

对上面的各特性曲线图有如下分析：

1) 网络总能量随时间递减，这可以通过线性递减函数的使用来解释。只是运用不同的转换规则，能量能够保持的时间也不同。换句话说，网络中节点存活的时间不同。

2) 连通度、覆盖度：转换规则1中，所有节点都一直处于工作状态，所以连通度和覆盖度都很高，只是节点的能量很快耗尽，网络死亡。其他3条转换规则中，采用转换规则2对应的网络连通度小于转换规则4的连通度，转换规则4的连通度小于转换规则3的连通度。转换规则2的覆盖度与转换规则4的覆盖度几乎一样，两者均大于采用转换规则2时的覆盖度。

3) 存活的传感器总数：在转换规则1中，所有节点在同一时刻死亡，因为它们的初始电池能量一样，网络运行时又都处于活跃状态。而其他3条转换规则中，转换规则2中，节点前一段时间死亡得快，后一段时间死亡得慢；规则3中，节点前一段时间死亡得慢，后一段时间死亡得快，使用本文提出的算法，即规则4，节点以比较均匀的速度死亡。

4) 系统耗能指数：在转换规则1中，网络存活时，所有节点一直工作，所以系统耗能指数最大；由图 7可以看出，转换规则4对应的耗能指数比转换规则2对应的能耗指数稍小，更加节约能量；采用转换规则3时系统耗能指数最小。

本文改进了转换规则，在尽量减少系统能量消耗的前提下，保证网络拓扑的连通性和覆盖性，通过仿真说明了改进算法使网络有更好的性能。但是改进算法对网络的生存时间并没有延长，且网络的覆盖度和连通度在转换规则2和转换规则3上取了折中值。其实节点根据不同局部更新规则交互作用，其效果肯定会是不同全局特性之间的折中关系。关键是在实际应用中，更需要保证网络的哪些性能？并且根据网络规模、传感器节点数的不同，特性曲线也有较大差别，根据所选的特定数据并不能反映出适用于所有网络的转换规则。但是介于本文的转换规则是在S1/B1(转换规则2)的基础上做的改进，而根据仿真结果的数据显示，改进后的算法使得网络确实在连通度、系统耗能指数有更好的性能，所以将节点剩余能量引入转换规则确实是可行的。研究结果为无线传感网络的建模和性能分析及后续的相关技术研究奠定理论基础。