1  引  言

      无线传感器网络是由一组传感器节点以自组织的方式构成的无线网络，其目的是协作的感知、采集和处理网络覆盖区域中感知对象的信息，并将信息发送给观察者。路由协议是无线传感器网络设计的重要环节，目前，针对其研究的主要内容是如何降低系统能耗。LEACH是一种典型的分簇协议，通过改变网络结构可以达到节约能耗的目的。但是，它预先选定簇头节点，并且簇头直到网络生命周期结束都是固定不变的；簇头同时还承担数据融合、数据发送的“双重”任务，因此，能量消耗很快。网络中，一旦簇头失效，簇内数据将全部丢失，整个网络面临瘫痪。综合考虑以上这些因素，本文设计了一种新的协议LACHS。它根据网络中节点的剩余能量，动态地选择集中式或分布式分簇算法，可以有效延长网络生命周期；同时考虑网络拓扑结构的变化，从而保证网络的稳定性。

      2  协议LACHS的设计

      协议LACHS将数据传输过程按照时间分为不同的“回合”，每个“回合”包括簇建立阶段和数据传输阶段。考虑到分簇算法执行的复杂性，LACHS将平面网络划分为2层结构。其中，底层为簇成员，第二层为它们对应的簇点。新“回合”开始后，先执行分簇算法，之后等待数据传输。

      2.1  簇建立阶段

      根据网络内节点的剩余能量，协议LACHS设计了两种算法。初始阶段，网络内节点能量充足，采用集中式分簇算法；后期，节点能量逐渐消耗，采用分布式分簇算法。

      2.1.1  集中式分簇算法

      考虑到sink较其他节点能量充足，在sink上运行模拟退火算法来选取下一“回合”的m个簇头节点。簇头必须保证在此“回合”中整个网络的能耗最低，即簇成员向簇头传输数据所需要能量的总和最小；选取簇头的条件是它与簇成员的距离最小。

      设当前状态的簇头节点集合为C，在每次迭代过程中，随机变化C中节点c的x，y(只考虑二维空间)坐标得到其新坐标x′，y′，位置最靠近x′，y′的节点就成为新集合C′中的c′。设包含节点c的集合C的代价为f(c)，包含节点c′的集合C′的代价为f(C′)，如果f(C′)

      当网络中的节点个数为100时，经过200～500次迭代就会收敛。

      当簇头选取结束后，簇类亦随之建立，集中式分簇算法流程见图1，具体过程如下：

      ①网络中节点散播完毕后，所有节点进入idle状态。

      ②等待随机时间Tm，sink节点在网络中随机选择m个节点组成初始簇头节点集C，剩余节点(n-m个)仍旧处于idle状态。

      ③等待随机时间Ti，剩余节点进入候选簇头节点状态(ch_cand)，成为此“回合”的候选簇头节点CHC(cluster head candidate)。

      ④CHC向sink节点广播msg_my-state，申请成为簇头节点，内容包括ID、位置、剩余能量、在以前“回合”中担任簇头的次数。

      ⑤sink节点接收到消息msg_my-state后，运行模拟退火算法，选出m个簇头节点CH(clusterhead)。

      ⑥CH向其邻居节点广播msg_search-mem-ber，邀请邻居节点加入。

      ⑦邻居节点接受信号最强的CH发出的邀请消息msg_search-member，并向它发送msg_add，成为候选簇成员CMC(cluster member candidate)。

      ⑧CH收到CMC的msg_add后，向其发送认证信息msg_allow，同意其加入。

      ⑨CMC收到msg_allow，表示加入成功，状态转为c_member，成为簇成员节点CM(cluster mem-bet)。

      ⑩随后进入数据传输阶段。

      2.1.2  分布式分簇算法

      当网络内存活节点的个数占原节点总数的30％时，采用分布式分簇算法，即sink不参与簇类划分，而是网络中的节点通过比较权值来选择簇头，权值计算

      Weight=energy_remain／(header_times+1)    (3)

      式中：header_times表示在以前”回合”中担任簇头的次数；energy_remain表示剩余能量。

      分布式分簇算法流程见图2。

      ①初始状态下，所有节点处于idle状态。

      ②等待一段随机时间Tn后，新的“回合”开始。所有节点转入cn_cand状态，成为候选簇头节点CHC。

      ③CHC向邻居节点广播msg_cand，申请成为簇头节点，内容包括ID、位置、剩余能量、在以前“回合”中担任簇头的次数。

      ④处于CHC附近的邻居节点接收信息msg_cand，由式(3)计算CHC的Weight值，然后将自己的Weight值与CHC的Weight值进行比较。若自己的Weight值大，则向邻居广播msg_I′m-header，告知自己成为此“回合”的簇头节点CH；若Weight值相同，则比较ID，选择ID小的节点作为簇头节点CH。

      ⑤邻居节点接收msg_I′m-header报文，选择信号最强的CH作为自己的簇头并向它发送申请加入信息msg_add，成为候选簇成员CMC。同时，把报文msg_I′m head信号次强的簇头节点CH作为本回合的备用簇头节点BCH(backup cluster header)保存。

      ⑥CH收到CMC的msg_add后，向其发送认证信息msg_allow，同意其加入。

      ⑦CMC收到msg_allow，表示加入成功，状态转为c_member，成为簇成员节点CM。

      ⑧随后进入数据传输阶段。

      分簇过程结束后，所有节点处于c_head或c_member状态，并且CH保存本簇所有CM的ID信息，CM保存自己的CH及BCH的ID信息。

      2.2  数据传输阶段

      首先，簇成员将采集的数据发送给它们对应的簇头(在第二层中)；然后，簇头将接收的数据经融合处理后经过一跳路由传输至sink。

      2.3  异常情况的处理

      当网络中出现旧节点死亡(包括：簇某个成员死亡和簇头死亡)和新节点加入时，我们称网络发生异常情况，此时需要采取策略对网络进行簇类重组。

      ①簇内某个成员节点死亡

      若簇头在一定时间Ta内没有收到簇成员的数据包，则认为该节点死亡。在整个WSN中，某个簇成员的死亡不会对整个网络造成太大影响，因而对于这种情况不处理。

      ②簇头死亡

      此情况多发生在网络生命周期后期，此时簇头节点能量消耗较大。簇成员节点向簇头节点发送msg_charact-data，若经过时间Tb未得到簇头响应，则认为簇头死亡，此时簇成员节点立即向其保存的备用簇头节点BCH发送msg_add申请加入备用簇；备用簇头节点接收到msg_add后，向它们发送msg_allow，批准加入。

      ③新节点加入

      为简化网络路由算法，此时采取简单设计，网络不再重新分簇仍采用之前选举的簇头节点，只是考虑将新来的节点加入哪个簇。新节点向此“回合”的簇头节点发送msg_new-join，簇头节点向其发送msg_allow；它们选择msg_allow报文信号最强的簇头申请加入该簇，同时将信号次强的簇头节点作为备选簇头节点保存。

      3  模拟实验验证

      为了评估分簇算法在能量消耗方面的特性，参考了文献[4]中单个节点的能量模型。当发送方与接收方距离为d时，传输a bit数据包所消耗的能量为

      为了比较LACHS与LEACH的路由性能，在实验时我们假设相同的网络环境，传感器节点随机部署在网络中，使用Matlab软件进行模拟实验，实验用到的参数如表1，其中N代表网络内部属节点的个数；M代表区域半径；k代表簇头节点个数。

      试验1：比较节点的存活情况

      在相同实验条件下，(即网络结构为N=200，M=50)协议LEACH运行了约750“回合”，协议LACHS大约可运行1100“回合”，运行周期明显增长，如图3所示。

      试验2：采用不同拓扑结构，比较了两协议的能耗，如图4所示。

      设Eave代表每个节点执行一“回合”的平均能耗，且Eave=Einitial／Etotal。

      从图4可以看出：

      ①协议LACHS更节能。

      当M=50时，协议LEACH，LACHS节点的平均能耗分别为0.00031，0.00026 J／node；当M=100时，协议LEACH，LACHS节点的平均能耗分别为0.00057，0.00054 J／node。

      ②当网络部署密集时，节约能耗更明显。

      M=50时，LACHS节约能耗比为(0.00031～0.00026)／0.00031=16.1％；M=100时，LACHS节约能耗比为(0.00057～0.00054)／0.00057=5.3％；比较可知M=100时节点分布密集，节约能耗比高。

      4  结  论

      针对经典协议LEACH的不足，设计了一种基于分簇的无线传感器网络路由协议LACHS。结合节点的剩余能量，LACHS动态选取集中式或分布式分簇算法，能有效延长生命周期；同时，还保证了拓扑结构的稳定性。模拟实验结果表明了算法的有效性。