具有最优簇规模的传感网不等簇数据收集协议

引用本文

宋晓莹, 温涛, 郭权, 张冬青, 盛刚. 具有最优簇规模的传感网不等簇数据收集协议. 2015, 45(6): 1961-1973
SONG Xiao-ying, WEN Tao, GUO Quan, ZHANG Dong-qing, SHENG Gang. Unequal cluster data gathering protocol with optimal cluster size in sensor networks. Journal of Jilin University Engineering and Technology Edition, 2015, 45(6): 1961-1973 复制到剪切板

Permissions

具有最优簇规模的传感网不等簇数据收集协议

宋晓莹¹, 温涛^1,², 郭权², 张冬青¹, 盛刚¹

1.东北大学软件中心,沈阳 110003

2.大连东软信息学院辽宁省网络安全与计算技术重点实验室,辽宁大连 116023

作者简介:宋晓莹(1984-),女,博士研究生.研究方向:无线传感器网络.E-mail:songxiaoying@neusoft.edu.cn

基金:国家自然科学基金面上项目(61170169,61170168); 山东省自然科学基金项目(ZR2012AL07, ZR2013AM013)

摘要

针对无线传感器网络的能量空洞问题,提出了一种具有最优簇规模的无线传感器网络不等簇的数据收集协议(UCPOCS)。首先,UCPOCS协议运用定时广播代替传统的消息协商机制竞选簇首。其次,利用候选簇首的位置信息从理论上获得最优簇半径对网络进行不等簇的划分。然后,簇首间多跳路由机制根据其相邻簇首的剩余能量等3种信息选择其中继节点,使UCPOCS能够适用于均匀和非均匀节点分布情况。最后,仿真结果表明UCPOCS协议能够有效地均衡网络能量消耗,延长网络寿命。

关键词: 计算机应用; 无线传感器网络; 数据收集; 不等簇; 能量空洞; 能量均衡

中图分类号:TP393 文献标志码:A 文章编号:1671-5497(2015)06-1961-13

Unequal cluster data gathering protocol with optimal cluster size in sensor networks

SONG Xiao-ying¹, WEN Tao^1,², GUO Quan², ZHANG Dong-qing¹, SHENG Gang¹

1.Software Center,Northeastern University,Shenyang 110003,China

2. Liaoning Key Lab of Network Security and Computing Technology,Neusoft Information Institute,Dalian 116023,China

Abstract

In this paper, an unequal cluster data gathering protocol with optimal cluster size (UCPOCS) is proposed in order to resolve energy hole problem in wireless sensor networks. First, UCPOCS adopts time broadcast to substitute traditional discussion mechanism to select cluster head. Then, the optimal cluster radius is theoretically obtained according to the location message of the candidate cluster head, which clusters the whole network. Finally, the multi-hops routing mechanism selects the relay-nodes according to three messages of neighbor cluster heads, e.g. residual energy etc, which is suitable for uniform and non-uniform node distribution. Simulation is conducted and results demonstrate that the proposed UCPOCS can balance energy consumption effectively and the network lifetime can be prolonged.

Keyword: computer application; wireless sensor networks; data gathering; unequal cluster size; energy hole; energy balanced

Show Figures

0 引言

目前, 无线传感器网络(Wireless sensor networks, WSNs)因其广阔的应用前景成为国内外的研究热点^[1]。传感器节点能够检测环境并从环境中获得所需信息, 通过邻居节点最终传送到用户。在多个传感器节点和一个Sink节点的多对一类型的无线传感器网络中, 由于距离Sink较近的节点承担大量的数据中转, 能量消耗高于网络中的其他区域, 进而形成了能量空洞现象^{[2, 3, 4]}。文献[5]中的实验结果表明, 当一个网络寿命结束时, 总的节点能量剩余超过90%。

分簇的数据收集协议是解决能量空洞问题的有效方法之一^[6]。目前, 根据分簇过程中竞争簇半径的不同, 主要分为等簇的^{[7, 8]}和不等簇的^{[2, 6, 9]}数据收集协议。LEACH协议^[7]是首次被提出的具有等簇的数据收集协议, 其思想是通过预先设定的相同概率以扰动的方式随机选取簇首节点, 簇首收集完簇内成员的数据后, 以直接传送的方式发送到汇聚点Sink。虽然该协议比平面的数据收集协议在网络寿命等性能方面具有显著提高, 但是其随机扰动方式会造成额外的能量消耗, 而且数据从簇首到Sink的直传方式会造成远方簇首的能耗大幅度下降。因为传感器节点的能量消耗与节点间的距离呈指数关系。HEED协议^[8]弥补了LEACH协议中的不足之处, 其采用剩余能量高的节点充当簇首节点, 有效降低随机选举簇首节点的能耗。另外, 簇首节点到Sink节点采用多跳中转的方式代替直传方式, 该方式有效降低了远方簇首节点因过快的能量消耗而提前死亡。因为在文献[10]中, 首次从理论上证明了多跳的传输方式比直接传送的单跳方式更具有能量高效性。然而, 在多对一的数据收集网络中, 等簇的数据收集方式存在着严重的问题。无论簇首节点位于网络中的何处, 其簇的规模总是相同的, 随着距离Sink较远区域面积的增大, 因其相同的簇规模导致簇的个数随之增加。这将加重距离Sink较近的节点中转负担, 从而降低网络寿命。事实上, 文献[11]已经证明了不等簇的数据收集协议比等簇的数据收集协议具有更长的网络寿命。这是因为, 不等簇的数据收集协议会使距离Sink较远的簇具有较大的规模, 而距离Sink较近的簇具有较小的规模。这样距离Sink较近的节点可消耗较少的能量处理簇内数据, 而拥有充足的能量来承担来自其他簇首节点的数据中转。

目前, 已有大量的文献研究了不等簇的数据收集协议, 然而, 对于竞争簇规模都是采用启发式的确定, 并没有给出理论上的最优值。UCS协议^[9]首次提出采用不等簇的方式进行数据收集, 其主要思想是采用分层的网络模型, 首先从理论上获得各层的簇成员个数的期望, 进而利用簇成员的个数来取得各层不等的簇半径。但该协议主要适用于异构的无线传感器网络模型, 而且采用仅有两层的同心环网络模型, 无法适用于大规模网络的数据收集。UCR^[6]是经典的不等簇数据收集协议, 其主要思想是在距离Sink较近的簇具有较小的簇规模, 而在距离Sink较远的簇形成较大的簇规模。这样, 能够使距离Sink较近的簇首具有足够的能量承担来自其他簇首的数据中转, 从而达到均衡整个网络能量消耗的目的。然而, 该协议适用于节点均匀分布的情况, 且各个簇的簇半径只是根据距离Sink的远近启发式地获得, 并没有给出理论上的最优值。文献[1]提出了一种新颖的不等簇数据收集协议, 该文献从理论上探讨了分簇时的最优簇半径, 但是该协议主要是通过不同时刻、不同簇半径的轮换方式实现不等簇的数据收集。也就是说, 在同一时刻, 网络中的所有簇规模依然是相同的。文献[12]提出了一种具有模糊逻辑能量意识的不等簇数据收集协议来解决能量空洞问题, 该数据收集协议的优势在于它能被应用在任意类型的无线传感器中。然而, 该协议的不等簇规模形成是依赖两个模糊的输入变量, 即节点与Sink之间的距离和节点的剩余能量。显然, 它没有考虑获得理论上最优的簇半径。

本文提出了一种具有最优簇规模的无线传感器网络不等分簇的数据收集协议。该协议主要解决了现存不等分簇数据收集协议的3个关键问题。①降低消息代价问题。文献[6, 9, 12]中, 在竞选簇首节点阶段, 采用消息协商机制最终确立簇首节点。即同一竞争簇半径内, 出现多个候选簇首的情况下, 一个候选簇首的剩余能量大于所有其邻居候选簇首的剩余能量时, 该簇首竞选成功并广播消息通知其邻居候选簇首, 邻居候选簇首收到该消息后放弃竞争并广播消息。这种消息协商机制, 会使候选簇首节点竞争簇首时需要广播和接收大量消息。尤其是在节点分布不均匀的网络中, 将造成节点能量消耗不均衡。因此, 降低消息代价适应、节点非均匀分布的网络是一个亟待解决的问题。②理论上的最优簇半径问题。在前述的分析中, 现存的不等分簇数据收集协议都没有给出理论上最优的簇半径, 仅仅是根据节点的相关信息启发式地确定簇规模。这种启发式确定簇规模的方式不但无法使网络效率^[13]达到最大化, 还严重影响簇首数据路由传输阶段的能量消耗。所以, 根据簇首节点的地理位置信息取得该簇理论上的最优簇半径是本文需要解决的最重要问题。③适应非均匀节点分布的路由选择问题。在簇首数据的传输阶段, 以往的文献主要考虑节点均匀分布情况下的能量高效和能量均衡的路由选择。而在本文节点非均匀分布的情况下, 仅考虑这两项路由选择因素是不够的。

1 系统模型

1.1 网络模型

网络中随机部署N个节点, 且节点的密度为ρ 。网络中所有节点具有相同的初始能量及处理能力, 其中, 分为簇首节点和普通节点。普通节点可通过单跳或多跳将数据传送到该簇簇首; 簇首节点根据一定的规则确定, 其数据通过其他普通节点或簇首多跳中转到Sink。

除此之外, 本文还假设无线传感器网络模型具有如下性质:

(1)节点及Sink被部署后, 位置固定, 不具有移动功能;

(2)网络中仅有一个Sink, 且部署于网络的中心和网络的外部两种场景;

(3)节点具有位置感知能力, 配备了GPS设备;

(4)网络中的所有节点具有相同的传输范围r₀;

(5)假设为一个完美的数据链路层, 不考虑消息碰撞等问题;

(6)采用数据融合技术减少传输数据量;

(7)周期采集型业务, 节点定期从传感器上收集数据到基站。

在上述假设中, 第1项说明节点包括基站不具有移动性; 第2项说明网络模式是多个节点对应一个基站的多对一数据收集模式; 第3项属性表明, 本协议要求节点具有位置感知能力, 也是确定最优不等簇半径的关键因素; 第4项属性表明节点的发射功率不可调, 主要是因为通过理论推导最优不等簇半径时的计算简便性, 详见2.1.2节; 第5项属性表明本协议暂不考虑MAC层的情况; 第6项属性表明, 本协议采用一定的数据融合技术来减少传输的数据量, 能够显著节约节点的能量; 第7项属性表明, 本协议适用于周期型的数据收集网络。

1.2 能耗模型

本文采用经典的能量消耗模型^[1], 其中发送时的能量消耗为式(1)所示, 接收时的能量消耗如式(2)所示。

$\begin{matrix} \begin{matrix} \{\begin{matrix} E_{t} = l E_{elec} + l ε_{fs} d^{2} & ifd < d_{0} \\ E_{t} = l E_{elec} + l ε_{amp} d^{4} & ifd \geq d_{0} \end{matrix} (1) \\ E_{r} (l) = l E_{elec} (2) \end{matrix} \end{matrix}$

其中, E_elec表示发射电路损耗的能量。若传输距离小于阈值d₀, 功率放大损耗采用自由空间模型; 当传输距离大于等于阈值d₀时, 采用多路径衰减模型。ε _fs, ε _amp分别为这两种模型中功率放大所需的能量。节点接收l比特的数据消耗时的能量如式(2)所示。以上参数的具体设置取自文献[1], 见表1。

表1 网络参数 Table 1 Network parameter

1.3 相关定义

为了保证数据传输的高效性及有效防止路由回路问题, 本文定义了簇首节点的前方邻居节点集合, 该定义主要受到文献[14]的启示。同时, 为了数据多跳传输时均衡地消耗能量和适应节点非均匀分布的情况, 定义了能量密度的概念。本文的6个重要定义如下:

定义1(簇首的前方区域) 簇首CH_i的前方区域是Sink与圆R(CH_i)的两条切线与经过两个切点的两条半径所组成的区域。其中, R(CH_i)为簇首CH_i的通信范围。

定义2(簇首的前方邻居节点) 簇首CH_i的前方邻居节点是位于其前方区域的邻居节点, 用N_f(CH_i)表示。

为了给出簇首CH_i的前方邻居节点集合的定义, 首先得明确邻居节点的转向角及转向边界角的定义。如图1所示, A、B为簇首CH_i通信范围与Sink的切点。区域AiBS为簇首CH_i的前方区域, 节点H为簇首CH_i的一个前方邻居节点, 且它们之间的距离为D_i_,_H, 簇首CH_i与Sink之间的距离为D。

	Figure Option View Download New Window
	图1 CH_i的前方邻居节点集合Fig.1 Front neighbor nodes set of cluster head CH_i

定义3(邻居节点的转向角) 邻居节点的转向角是以簇首CH_i为顶点, 前方邻居节点和簇首CH_i的边与簇首CH_i和Sink为边的夹角。如图1所示, α 为邻居节点H的转向角。邻居节点的转向角可通过式(3)计算求得。

$\begin{matrix} α_{iH} = \arccos \frac{D_{i, S}^{2} + D_{i, H}^{2} - D_{H, S}^{2}}{2 \times D_{i, H}^{} \times D_{i, S}} (3) \end{matrix}$

式中:α _iH为簇首CH_i与邻节点H的转向角; D_i_,_S为簇首CH_i与Sink之间的距离; D_H_,_S为邻居节点H与Sink之间的距离。

定义4(邻居节点的转向边界角) 转向边界角是转向角的最大值。如图1所示, β 是邻居节点H关于簇首节点CH_i与Sink的转向边界角。利用式(4)可以求得。

$\begin{matrix} β_{i} = \arcsin \frac{\sqrt{{D_{i, S}}^{2} - {r_{0}}^{2}}}{D_{i, S}} (4) \end{matrix}$

定义5(簇首的前方邻居节点集合) 簇首的前方邻居节点集合是可以利用邻居节点的转向角和转向边界角表示为式(5)所示。

$\begin{matrix} \begin{matrix} N_{f} (C H_{i}) = \\ \{\forall n_{H} \in N (C H_{i}), D_{i, H} \leq r_{0}, α_{iH} \leq β_{i}} (5) \end{matrix} \end{matrix}$

式中:β _i为簇首CH_i与其邻居节点的转向边界角。

定义6(能量密度) 能量密度是在节点通信范围内, 所有邻居节点的剩余能量之和与该节点的通信覆盖面积的比率。形式化表示为式(6)所示。

$\begin{matrix} ED (i, t) = \frac{\sum_{j}^{=} R E_{j}}{S_{i}} j \in N (i) (6) \end{matrix}$

式中:ED(i, t)为在t时刻, 节点i的能量密度; S_i为节点i的覆盖面积; $\begin{matrix} \sum_{j}^{=} \end{matrix}$ RE_j为节点i的所有邻居节点的剩余能量之和。

2 UCPOCS协议

UCPOCS协议主要分为两个部分:能量高效的分簇算法和能量高效且均衡的多跳路由算法。在网络部署阶段, 由于节点配备GPS设备, 传感器节点可以方便地获取自身、其邻居节点以及Sink的地理位置信息, 从而获得与它们之间的距离。这不仅有利于获得节点的前方邻居节点集合从而保障路由选择的高效性, 更有助于实现网络非均匀分簇时重要因素的取得。重要的是根据地理位置的局域信息从理论上求得了簇半径的最优值, 可实现靠近汇聚点的簇成员较少、远离汇聚点的簇成员较多的簇规模的异构现象。图2为具有最优簇规模的非均匀数据收集协议的示意图。其中, 网络中的节点组成了Voronoi图结构的不等簇, 节点之间的连线代表节点间的多跳传输。

	Figure Option View Download New Window
	图2 UCPOCS数据收集协议Fig.2 UCPOCS data gathering protocol

2.1 簇的形成

本文是采用异构分簇的方式将无线传感器中的节点组织成一个个带有一个簇首与多个普通成员的簇单元。与LEACH协议相似, 为了使簇首节点能量消耗均衡, 簇的划分重构是以轮的方式循环操作。在这期间, 向汇聚点Sink传输多少轮数据后重新构簇获得最大的网络寿命仍是一个开放性的问题^{[15, 16]}。本文研究重点不在于此, 故采用与LEACH协议相同的机制重新划分网络。UCPOCS协议采用的是分布式簇首竞争算法, 主要以节点的剩余能量和与汇聚点Sink的距离为选取的依据, 从而使候选簇首节点成为最终簇首节点。当网络中的节点以概率T成为候选簇首节点后, 根据每个候选簇首的地理位置信息从而确定其最优的簇半径。然后, 通过定时广播机制确定最终簇首。网络中的普通节点选取最近的簇首节点, 从而形成了距离汇聚节点近的簇规模较小, 使其拥有足够的能量中转其他节点的数据; 距离汇聚节点较远的簇规模较大, 因其不必中转过多次的数据。通过这种异构的分簇方式, 以期使网络均衡地消耗能量, 从而解决能量空洞问题。

2.1.1 簇首的确定

簇首的确定过程大致分为4个阶段, 即确定候选簇首阶段, 确定候选簇首信息阶段, 计算广播时间阶段以及最终簇首确立阶段。图3展示了UCPOCS的簇首选择算法的伪代码。在第1个阶段, 为每个节点分配一个0到1的随机数τ , 同时设置一个门限值T来控制网络中的节点成为候选簇首的比例。如果τ 小于门限值T, 该节点将成为网络中的候选簇首节点, 如图3中1~4行所示。

	Figure Option View Download New Window
	图3 UCPOCS的簇首选择算法Fig.3 Clustering head selection algorithm of UCPOCS

在第2阶段中, 所有的候选簇首节点需要通过GPS设备确定各候选簇首节点的邻居簇首节点以及它们到汇聚点Sink的距离。确定候选簇首与汇集点Sink的距离是为了从理论上获得使能量消耗最小时的最优簇半径, 将在2.1.2节详细阐述。确定候选簇首的邻居候选簇首是因为当同一个候选簇中出现多个候选簇首时, 将采用簇首竞争算法确立最终簇首。由于UCPOCS协议中的簇首选举依据的是局部竞争, 因此需要为每个候选簇首节点保存一张邻居候选簇头信息表, 其结构为:邻居候选簇首的ID, 邻居候选簇首的簇半径和邻居候选簇首的剩余能量。当候选簇首确定完毕后, 向网络中广播竞选消息CandiHeadMsg(ID, r_i, RE_i)。如图3中5~10行所示。

在第3阶段中, 当同一个候选簇内出现多个候选簇首时, 也就是说候选簇首的邻居候选簇首表不为空, 需要采用定时广播机制来实现候选簇首的竞争。候选簇首广播其成为最终簇首的时间主要依赖两个因素:其自身的剩余能量和它邻居候选簇首的平均剩余能量以及它本身与Sink的距离和邻居簇首到Sink的平均距离。本文规定了如果候选簇C_i成为了最终簇首, 那么在其簇半径范围内的所有邻居候选簇首均自动退出簇首竞争。该规则主要的目的是确保同一个候选簇中仅有一个最终簇首。在前面提到的文献[6, 9, 12]中, 簇首节点的竞争采用的是协商机制。其过程是:当剩余能量最多的候选簇首发送其胜利的消息后, 同一个簇的候选簇首接收到该消息后发送退出消息并变成普通节点, 这个剩余能量最多的簇首接收到退出消息后, 将该候选簇首从其邻居簇首表中删除。最后, 邻居候选簇首表为空的候选簇首发送最终簇首消息。由此可见, 用这种协商机制, 本身就需要广播和接收大量的消息。在节点随机分布的网络模型中, 有些区域节点部署得密集, 有些区域节点被部署得松散, 若此时运用该机制会造成能量消耗的严重不均衡。本文运用计算广播机制的思想是根据式(7)计算何时广播成为最终簇首的时间, 然后直接发送成为最终簇首的消息, 从而省去消息协商的过程, 达到降低消息代价的目的。

$\begin{matrix} t_{i} = T_{PD} \times \frac{{\bar{E}}_{N (i)}}{R E_{i}} \times \frac{d_{i}}{{\bar{d}}_{N (i)}} (7) \end{matrix}$

从式(7)可知, 如果C_i的剩余能量小于其邻居候选簇首的平均剩余能量, 同时, 它到Sink的距离大于其邻居候选簇首的平均距离, 则C_i直接退出竞选成为普通节点。否则, 可以求得候选簇首C_i广播其本身成为最终簇首的时间t_i。如果候选簇首C_i的剩余能量较大且距离Sink较近, 则它广播成为最终簇首的时间较短, 成为最终簇首的概率就会较大。如图3中11~14行所示。

在第4阶段中, 主要是确立最终簇首。在第3阶段中, 通过式(7)可以求得候选簇首C_i向网络广播自身成为最终簇首的时间。在T_PD有效的范围内且当前时间没有超过t_i的时间范围, 若候选簇首C_i收到了来自其他邻居簇首成为最终簇首消息VictoryHeadMsg(ID_j)时, 候选簇首C_i自动退出簇首竞选。否则, 广播VictoryHeadMsg(ID_i)消息使其自身C_i成为最终簇首。如图3中15~23行所示。

从分簇算法可知, 第3阶段中, 运用定时广播机制可大大降低消息代价。而在确定完最终簇首节点以后, 普通节点通过地理感知可以确定离它最近的簇首并向该簇首发送JoinClusterMsg(ID_i, RE, Position)消息从而完成整个网络的分簇工作。值得注意的是, 文献[6, 9, 12]中是通过两次消息广播完成普通节点加入到相应的簇中。而本文仅通过一次即可完成, 这进一步降低了消息代价。

2.1.2 基于位置的最优不等簇半径

通过上一小节, 完成了网络簇结构的划分。在普通节点成为候选簇首节点的过程中, 需要计算在该候选簇首位置的竞争最优簇半径。在这一小节中, 详细介绍根据簇首节点的地理位置信息使能量消耗最小时的最优簇半径。其主要思想是:根据簇首与汇集节点Sink的距离, 使距离汇集节点近的簇规模较小, 使其有足够的能量中转来自其他节点的数据; 距离汇集节点远的簇, 规模较大, 达到网络能量消耗均衡, 从而解决能量空洞问题。为了从理论上推导最优的簇半径, 得到了关于获得最优簇半径的定理1。

定理1 簇首节点处于网络中的任意位置时, 使网络中能量消耗最小时最优簇半径为r= · 。

证明本文主要从两个角度证明定理1。第1种情况为从网络中任意取出一个距离汇集节点Sink为D的簇, 获得其在能量消耗最小时的最优簇半径。第2种情况为在网络模型中任意位置的簇在能量消耗最小时的最优簇半径。

(1)当网络中仅有一个簇时, 网络模型如图4所示。由于本文的网络节点为随机分布且节点的密度为ρ , 所以分布在该簇中的簇成员节点个数为ρ π r²。在该簇中, 所有节点到簇首CH_i的平均距离为:

$\begin{matrix} \int_{0}^{2} \int_{0}^{r} r^{2} drdθ \cdot (\frac{1}{π r^{2}}) = \frac{2}{3} r (8) \end{matrix}$

	Figure Option View Download New Window
	图4 单个簇的网络模型Fig.4 Network model with single cluster

一个簇首的能量消耗分为汇聚簇内数据所消耗的能量和簇首到Sink的能量消耗。为了使单个簇首的能量消耗最小, 首先需要计算簇中的所有节点传送1个单位数据到簇首CH所消耗的平均能量和簇首CH传送1个单位数据到汇集节点Sink所需要的能量。

为了计算简便, 本文假设节点能量消耗采用自由空间模型, 且不考虑E_elec等因素仅与地理位置信息相关的能量消耗。E_{one_intra}为所有节点传送1个单位数据到簇首CH所消耗的平均能量:

$\begin{matrix} E_{one_intra} = ρπ r^{2} \cdot \frac{4 r^{2}}{9 {r_{0}}^{2}} (9) \end{matrix}$

式中:r为簇半径。

E_{one_inter}为簇首CH传送数据到汇集节点Sink所消耗的能量:

$\begin{matrix} E_{one_inter} = \frac{D^{2}}{{r_{0}}^{2}} (10) \end{matrix}$

式中:D为簇首节点与汇集节点Sink的距离。

E_{one_sum}是簇中的所有簇成员节点传输1个单位数据到汇集节点Sink所消耗的总能量。由于所有节点的数据首先传送到簇首节点, 再由簇首节点聚合后传输到汇集节点Sink, 其总能耗为E_{one_intra}加上E_{one_inter}, 而该簇的簇成员节点的总个数为ρ π r²。因此, 得到式(11):

$\begin{matrix} \begin{matrix} E_{one_sum} = \frac{E_{one_intra} + E_{one_inter}}{ρπ r^{2}} = \\ \frac{4 r^{2} ρπ r^{2} + 9 D^{2}}{9 ρπ r^{2} {r_{0}}^{2}} (11) \end{matrix} \end{matrix}$

为了使网络中的每个节点能量消耗最小, 对式(11)中以r为自变量求导数获得极值点。因此, 根据式(11)求得了一个簇能量消耗最小时, 最优簇半径的表达式如式(12)所示:

(2)当簇位于圆形网络中时, 网络模型如图5所示。θ 为簇首与X轴正半轴之间的夹角, 圆形网络的半径为R。通过第一种情况, 获得了单个簇节点在网络中能量消耗最小时的最优簇半径值。根据单个簇的最优簇半径表达式(12), 假设在圆形网络拓扑中, 最优簇半径的表达式为r=α D^β, 若求得α 和β 的值构成的簇半径表达式与式(12)相同, 那么定理1便得到了证明。其中, α 和β 必须为实数。因此, 接下来的重点是求出α 和β 的值。

	Figure Option View Download New Window
	图5 圆形拓扑的网络模型Fig.5 Network model of circle topology

为了求得圆形网络模型中节点能量消耗最小时的最优簇半径, 在该网络模型中用极坐标来表示簇首节点相对于汇集节点Sink的位置, 即通过极坐标(D, θ )可以确定网络中的一个簇首节点。那么, 以簇首节点CH_i为中心的簇面积为π r², 则该簇的密度函数如式(13)所示:

$\begin{matrix} f_{CH} (D, θ) = \frac{1}{π r^{2}} (13) \end{matrix}$

与网络中仅有单个簇的能量消耗分析相似, 为了获得网络中能量消耗最小时的最优簇半径, 同样需要确定圆形网络模型中簇内部的节点传送到簇首所消耗的能量, 数据从簇首传送到汇集节点Sink所需要消耗的能量以及它们消耗的总能量。

由式(9)可得到簇首距离Sink为D时, 簇成员节点传送其簇首节点所消耗的能量表达式为:

$\begin{matrix} \begin{matrix} E_{circle_intra} = \\ \int_{0}^{2} \int_{0}^{R} \frac{4 r^{2}}{9 {r_{0}}^{2}} \cdot ρπ r^{2} \cdot f_{CH} (D, θ) \cdot DdDdθ = \\ \frac{4 ρ}{9 {r_{0}}^{2}} \overset{2 π}{\int_{0}} \overset{R}{\int_{0}} D r^{2} dDdθ (14) \end{matrix} \end{matrix}$

式中:E_{circle_intra}为圆形网络模型中簇首距离Sink为D时的簇内部节点传送到各自簇首所消耗的能量; 积分单元为距离汇集节点Sink的簇首个数f_CH(D, θ )DdDdθ 。

同理, E_{circle_inter}为距离Sink为D的簇首传送数据到Sink时的能量消耗。根据式(10)和积分单元f_CH(D, θ )DdDdθ 求得如式(15)所示:

$\begin{matrix} \begin{matrix} E_{circle_inter} = \int_{0}^{2} \int_{0}^{R} f_{CH} (D, θ) \cdot D \cdot \frac{D^{2}}{{r_{0}}^{2}} dDdθ = \\ \frac{1}{π {r_{0}}^{2}} \int_{0}^{2} \int_{0}^{R} \frac{D^{3}}{r^{2}} dDdθ (15) \end{matrix} \end{matrix}$

因此, E_{circle_sum}为网络中距离Sink为D时的簇, 其簇成员传送到汇集节点Sink所消耗的能量总和为:

$\begin{matrix} \begin{matrix} E_{circle_sum} = E_{circle_intra} + E_{circle_inter} = \\ \int_{0}^{2} \overset{R}{\int_{0}} (\frac{4 πρD r^{4} + 9 D^{3}}{9 π {r_{0}}^{2} r^{2}}) dDdθ (16) \end{matrix} \end{matrix}$

为了获得α 和β 的值, 将前面假设的等式r=α D^β代入到式(16)中, 便得到了关于α 和β 的总能耗公式:

$\begin{matrix} \begin{matrix} E_{circle_sum} (α, β) = \\ \int_{0}^{2} \int_{0}^{R} \frac{4 πρD (α D^{β})^{4} + 9 D^{3}}{9 π {r_{0}}^{2} (α D^{β})^{2}}] dDdθ = \\ \frac{2 π}{{r_{0}}^{2}} (\frac{4 ρα}{9} \cdot \frac{R^{2 + 2 β}}{2 + 2 β} + \frac{1}{π α^{2}} \cdot \frac{R^{4 - 2 β}}{4 - 2 β}) (17) \end{matrix} \end{matrix}$

将α 和β 视为自变量, 分别对其求偏导数得到了式(18)和式(19):

$\begin{matrix} \begin{matrix} \frac{\partial E_{circle_total}}{\partial α} = \frac{1}{{r_{0}}^{2}} [\frac{8 ρπ}{9} \cdot \frac{R^{2 β + 2}}{2 β + 2} - \frac{4}{α^{3}} \cdot \frac{R^{4 - 2 β}}{4 - 2 β}] (18) \\ \frac{\partial E_{circle_total}}{\partial β} = \\ \frac{1}{{r_{0}}^{2}} [\frac{8 ρπα}{9} \cdot \frac{R^{2 + 2 β} [(2 + 2 β) \cdot lnR - 1]}{{(2 + 2 β)}^{2}} + \\ \frac{2 R^{4 - 2 β}}{α} \cdot \frac{(4 - 2 β) \cdot lnR - 1}{{(4 - 2 β)}^{2}}] (19) \end{matrix} \end{matrix}$

令式(18)和式(19)等于0, 将式(18)(19)组成一个关于α 和β 的二元一次方程组, 便可求得α 和β 在总能量消耗最小时的值。利用Matlab工具求得, α 共有四个解, 分别为:

$\begin{matrix} \begin{matrix} {(\frac{9}{4 ρπ})}^{\frac{1}{4}}, - {(\frac{9}{4 ρπ})}^{\frac{1}{4}}, - \frac{1}{4} [9^{\frac{7}{8}} {(\frac{1}{4 ρπ})}^{\frac{1}{4}} i + {(\frac{9}{4 ρπ})}^{\frac{1}{4}}], \\ - \frac{1}{4} [- 9^{\frac{7}{8}} {(\frac{1}{4 ρπ})}^{\frac{1}{4}} i + {(\frac{9}{4 ρπ})}^{\frac{1}{4}}] (20) \end{matrix} \end{matrix}$

β 仅有一个实数解为1/2。由于α 和β 必须为实数, 所以最终得到了式(21):

$\begin{matrix} α = {(\frac{9}{4 ρπ})}^{\frac{1}{4}}, β = \frac{1}{2} (21) \end{matrix}$

将式(21)代入到之前假设的等式r=α D^β中, 网络中能量消耗最小时的最优簇半径仍然与网络中仅有一个簇时的最优簇半径相同。因此, 定理1得到了证明。

2.2 节点间的多跳路由

当簇首节点将数据传送到汇集节点Sink时, 每个簇首节点首先将簇成员的数据进行聚合, 然后将数据包以多跳的方式将数据传送给其前方邻居节点中路由代价最小的节点。被选中的前方邻居节点再选择其前方邻居节点中的节点, 以此类推传送至汇集节点Sink, 其目的是寻找一条从簇首节点到汇集节点Sink的最小代价路径, 如图2所示。由于无线传感器网络多对一的传输模式使其路由数据的方式与Ad Hoc网络的路由协议完全不同。另外, 无线传感器网络中基于事件驱动和查询驱动的路由协议也并不适合分簇的无线传感器网络。因此, 需设计适合分簇网络和节点非均匀分布的多跳路由算法。本文假设UCPOCS协议中的中继节点可融合来自其他簇首或其他节点的数据。

在1.3节定义了前方邻居节点集合, 主要是限定了下一跳节点的选择范围, 将使路由发现趋向于汇集节点Sink的区域。这不仅保证了能量的高效性, 还防止了路由回路的产生。在选择下一跳节点前, 簇首或节点N_i根据与汇集节点Sink的位置信息计算出前方邻居节点集合, 并建立一张前方邻居节点信息表, 包括节点ID、节点位置、Sink的位置、当前剩余能量和能量密度。簇首或节点N_i计算其每个前方邻居节点的路由代价, 并选择路由代价最小的前方邻居节点作为该簇首或节点的下一跳节点。当选择N_j为下一跳节点后, 再根据它与Sink的位置信息确定其前方邻居节点集合, 从中选择下一跳中继节点, 直到数据送达Sink, 该代价函数如式(22)所示:

$\begin{matrix} cost (i, j) = α \frac{d_{jSink}}{d_{iSink}} + β \frac{{\bar{E}}_{fNei} (i)}{E_{res} (N_{j})} + γ \frac{{\bar{ED}}_{fNei} (i)}{ED (N_{j})} (22) \end{matrix}$

式中:d_i_Sink为节点与汇集节点Sink之间的距离; d_j_Sink为前方邻居节点与汇集节点Sink之间的距离; $\begin{matrix} {\bar{E}}_{fNei} \end{matrix}$ (i)为节点i的前方邻居节点的平均剩余能量; E_res(N_j)为节点j的当前剩余能量; $\begin{matrix} {\bar{ED}}_{fNei} \end{matrix}$ (i)为节点i的前方邻居节点的平均能量密度; ED(N_j)为节点j的当前能量密度; α 、β 和γ 为加权系数, 且三项加权系数的和为1。簇首或节点i选择其前方邻居节点中代价函数最小的节点, 即k=argmincost(i, j)。

在设计该代价函数时, 第1项考虑的是选择离汇集节点Sink较近的中继节点。主要是因为本文节点的传输范围是固定的, 选择距Sink较近的中继节点可减少中继次数, 降低节点的能量消耗。

第2项考虑的是选择剩余能量较高的节点作为下一跳中继节点。因为无线传感器网络节点能量有限, 无论是传送数据、接收数据还是簇首选择都要消耗大量的能量。因此, 节点的剩余能量是选择下一跳中继节点的主要因素。

第3项考虑的是选择剩余能量密度较高的节点。根据定义6, 能量密度实质上是单位面积上的剩余能量。选择该因素主要是因为本文的节点是随机部署的, 即有些节点被部署得密集, 有些节点则被部署得稀疏, 而节点密集时被选择的下一跳中继节点较为分散, 能量消耗得较为均衡; 而节点稀疏时, 被选择的下一跳中继节点较为集中, 容易造成过早出现能量消耗最大的节点, 使网络寿命缩减。因此, 该因素主要确保了节点能量消耗的均衡性。

值得注意的是, 如果在前方邻居节点表中存在多个相同的最小路由代价, 则随机选取一个节点作为下一跳中继节点。如果节点N_i的前方邻居节点集合为空, 则采用与文献[14]相同的回退机制, 将该节点在邻居信息表中删除, 重新选择节点N_i的前方邻居节点集合中代价函数次最小的节点作为下一跳中继节点。

3 UCPOCS协议分析

性质1 在网络分簇阶段, UCPOCS协议的消息复杂度为O(N)。其中, N为网络中节点的个数。

证明在簇首选择阶段开始, 假设网络中有N个节点, 以概率T成为候选簇首节点, 则有N× T个CandiHeadMsg消息广播为候选簇首节点。根据各个候选簇首的剩余能量高低, 使剩余能量高的候选簇首节点较快地广播其成为最终的簇首节点, 假设网络中有M个候选簇首节点成为最终的簇首节点, 则有M个候选簇首节点会广播VictoryHeadMsg消息成为最终簇首节点。由于UCPOCS协议是具有位置意识的协议, 能够通过GPS设备确定普通节点与其最近的簇首节点, 然后直接发送JoinCluserMsg消息加入到距离它最近的簇首节点, 该消息的个数为N-M个。因此, 该阶段网络中总的消息开销为N× T+N。所以, 消息复杂度为O(N)。

从性质1可以看出UCPOCS协议的消息开销是非常小的。数据收集算法HEED协议在构簇的过程中是由内向外迭代构簇, 因此其消息的上界为N× 消息迭代次数; UCR分簇算法的消息开销为N× (2T+1)。本文的UCPOCS协议无需迭代, 因此一定比迭代确定分簇的HEED协议消息代价小。另外, UCPOCS协议的消息开销比UCR的小N× T。这主要是因为, 本文利用定时广播机制与传感器节点定位技术, 节点可以很方便地获得自身、邻居节点以及Sink的地理位置信息, 从而有效避免竞争簇首节点时的盲目泛洪。因此, UCPOCS协议消息代价大幅度地降低。

性质2 簇首节将数据传向汇集节点Sink的过程中, 不会产生路由回路。

证明采用反正法来证明性质2。假设存在一个路由回路为{n₁, n₂, …, n_L, n₁}。D_i_{, Sink}表示为节点i与汇集节点Sink之间的距离。根据定义5, 节点的前方邻居节点D_{1, Sink}要比D_{2, Sink}长, 即D_{1, Sink}> D_{2, Sink}> …> D_L_{, Sink}> D_{1, Sink}。然而, 实际上节点L与汇集节点Sink之间的距离D_L_{, Sink}比节点1到汇集节点Sink的距离D_{1, Sink}要短。这与实际情况矛盾。因此, 簇首节点将数据传向汇集节点Sink的过程中, 保证不会产生路由回路。

4 仿真实验

4.1 场景设置及测试指标

仿真实验的运行环境为Intel Pentium双核(2.2 GHz)处理器, 2 G内存, 运用C语言在Visual C++6.0软件平台上实现了UCPOCS协议和其他3个数据收集协议:LEACH协议、HEED协议和UCR协议。在这4个协议中, LEACH协议和HEED协议是等簇的, 而UCR协议和本文的UCPOCS协议均为不等簇协议。为了评价UCPOCS协议, 实验设置了两种不同的场景。一种是汇集节点Sink位于无线传感器网络的中心, 另一种是Sink位于无线传感器网络的外部。其他实验参数如表1所示。

在测试时, 本文主要考查了如下6个指标:

(1)总能量消耗:网络节点在正常工作时, 节点每一轮所消耗的能量总和。

(2)网络寿命:由于本文节点为非均匀分布情况, 除了考查第一个节点死亡时网络中节点工作的轮数(FDT), 还需要考查网络中死亡节点达到一半时节点工作的轮数(HDT)。

(3)能耗均衡性:本文通过节点剩余能量的均值和方差来考查能量消耗的均衡程度。值得注意的是:在某一时刻, 剩余能量的均值越大, 方差越小, 则协议的能量消耗均衡性越好。

$\begin{matrix} \begin{matrix} {\bar{E}}_{r} = \frac{\sum_{i}^{=} E_{r}}{N} (23) \\ \hat{E} = \frac{\sqrt{\sum_{i}^{=} (E_{r} {- \bar{E_{r}})}^{2}}}{N} (24) \end{matrix} \end{matrix}$

式中:E_r为节点当前的剩余能量; $\begin{matrix} {\bar{E}}_{r} \end{matrix}$ 为网络中节点的平均剩余能量; $\begin{matrix} \hat{E} \end{matrix}$ 为所有节点剩余能量的标准差。

(4)簇首个数:网络中, 簇首在不同仿真时间中的总个数。该指标主要是为了考查各个数据收集协议中, 分簇算法的稳定性。

(5)存活节点数量:指节点从工作开始到节点全部死亡过程中, 存活节点的数量随着工作时间的变化情况。该指标是为了比较四种数据收集协议的稳定性。

(6)死亡节点分布:指4种协议的死亡节点数量达到30%时, 它们在网络中的分布情况。该指标是为了比较4种数据收集协议解决能量空洞问题的有效性。

4.2 实验结果

(1)总能量消耗

4种协议的总能量消耗在场景I和场景II的情况如图6所示。其中, 图6(a)为Sink部署在无线传感器网络的中心, 图6(b)为Sink部署在无线传感器网络的外部。从图中可以发现, 随着网络监测时间的增加, 4种协议的总能耗也随之增加。由于UCPOCS协议采用基于地理信息的方式确定邻居节点和簇首节点, 防止了盲目泛洪消耗的能量。

	Figure Option View Download New Window
	图6 总能量消耗Fig.6 Total energy consumption

另外, 其簇半径为网络中能量消耗最小时的最优值, 故能量消耗较少, 工作时间相对较长。而LEACH协议由于簇首节点收集完簇内数据后, 通过直接传送方式送达Sink, 导致其能量消耗最快。HEED协议在选取簇首节点时考虑了剩余能量因素, 并且在簇间传输过程中采用了多跳传输, 故其能耗在同一时刻明显低于LEACH协议。UCR协议由于是非均匀分簇协议, 在Sink附近的簇规模较小, 有足够的能量负责来自其他簇首节点的数据中转。因其消息协商机制和启发式确定簇规模导致它的能量消耗大于本文的UCPOCS协议。

(2)网络寿命

图7表示4种协议在两种网络场景中的网络寿命(单位:轮)。FDT为网络中出现第一个死亡节点时的时间, HDT为网络中出现死亡节点的数目达到了一半时的网络时间。由于FDT在比较稀疏的网络环境中是重要的性能指标在节点非均匀分布的环境中, 有些区域节点部署得密集。因此, 仅仅考察FDT是不够的, 本文还考察了网络的HDT。从图中可以看出, 在这两种场景中, 无论是FDT还是HDT不等簇分簇方式都比等簇的要长。并且场景I中同一个协议的网络寿命明显比场景II中的要长。这主要是因为场景I的Sink位于网络的中心, 各个节点到Sink的距离比场景II中的大部分节点要短, 故传输过程中能量消耗较小, 网络寿命较长。其中, 在场景I中同为等簇的HEED协议要比LEACH协议的FDT长81.9%, 比HDT长72.15%; 同样为不等簇的UCPOCS协议比UCR协议的FDT长5.38%, 比HDT长8%。

	Figure Option View Download New Window
	图7 网络寿命Fig.7 Network lifetime

(3)能耗均衡性

4种协议在两种网络场景中的平均剩余能量和节点的剩余能量方差如图8所示。根据指标1中的网络节点总能量消耗和式(23)(24)可以求得各轮中节点的平均剩余能量和剩余能量的方差。从图中可以观察出, 等簇的LEACH协议和HEED协议的节点平均剩余能量较大, 并且其方差很大, 波动得也比较大。这说明等簇的数据收集协议并没有采用有效的能量消耗均衡机制。因为等簇的协议有可能产生仅有一个簇首节点无簇成员的簇, 这导致节点负载不均衡, 能量消耗的差异比较大。UCPOCS协议的方差最小且比较稳定, 因此UCPOCS协议最好地均衡了无线传感器网络中节点的能量消耗。

	Figure Option View Download New Window
	图8 能量消耗的均衡性Fig.8 Balance of energy consumption

(4)簇首个数

4种协议在两种网络场景中的簇首个数如图9所示。从图中可以观查到, UCPOCS协议的簇首个数在FDT出现之前, 网络中形成的簇个数比较稳定。而在FDT之后, UCPOCS协议的簇首个数也没有类似于其他3种协议有剧烈的下降趋势。这是因为网络中的簇首个数主要取决于簇首节点的地理位置信息和其传输范围, 这两个因素值相对固定。

	Figure Option View Download New Window
	图9 簇首节点个数Fig.9 Number of cluster head

因此, UCPOCS协议网络中的簇个数没有特别明显的变化, 故其分簇算法具有良好的稳定性。而节点的剩余能量作为UCR协议和HEED协议确定簇半径的主要因素之一。在FDT出现后, 网络死亡速度加快, 节点的剩余能量大幅度降低。因此, 这两种协议在FDT出现后, 簇首节点个数也随之大幅度地减少。

(5)存活节点数量

4种协议在两种网络场景中的节点存活数量如图10所示。从图中可以看出, UCPOCS协议在两种场景中的稳定性都比较好。其所有节点的存活时间明显长于其他3种数据收集协议。即使UCPOCS协议出现了FDT之后, 其存活节点数量也是呈线性下降到节点全部死亡, 而不是网络分裂直接导致数据收集功能完全瘫痪。这主要是因其采用定时广播机制代替的消息代价较高的簇首节点竞选协商机制, 故在分簇阶段中的能耗就小于其他3种数据收集协议。另外, UCPOCS协议的簇半径是使网络能量消耗最小的最优值, 这能够进一步节省网络中的能量消耗。重要的是, 在数据多跳的路由选择中, UCPOCS协议考虑了能量密度因素更适合节点非均匀分布的无线传感器网络。综上, UCPOCS协议较其他3种数据收集协议具有更好的稳定性。

	Figure Option View Download New Window
	图10 存活节点数量Fig.10 Nnumber of alive nodes

(6)死亡节点分布

4种协议在两种网络场景中的死亡节点分布如图11所示。从图中可以看出, 4种数据收集协议因其不同的功能机制, 死亡节点呈现了不同的分布状况。LEACH协议的死亡节点主要分布在远离Sink的区域, 这主要是因为簇首节点向Sink传送数据时采用的是直接传送的方式。而节点间的距离与能量消耗呈指数关系。因此, 远离Sink的区域能量消耗得最快。HEED协议和UCR协议的死亡节点主要分布于接近Sink的区域。因其多跳传输方式, 造成Sink附近的区域承担了较重的数据中转。虽然UCR协议为不等簇的数据收集协议, 离Sink较近的区域具有较小的簇规模, 使其具有足够的能量承担数据中转。然而, 簇规模的确定是启发式的。因此, UCR协议只能有效缓解能量空洞的出现, 但还是不能最终避免。UCPOCS协议的死亡节点随机分布于整个网络中, 故其相比其他3种数据收集协议能够较好地避免能量空洞问题。

	Figure Option View Download New Window
	图11 死亡节点分布Fig.11 Distribution of dead nodes

5 结束语

提出了一种具有最优簇规模的无线传感器网络不等分簇的数据收集协议(UCPOCS)。在簇首节点竞选阶段, 采用定时广播机制代替了传统协议的信息协商机制。其次, 本文采用了基于簇首节点的地理信息, 从理论上确定最优簇半径, 使整个网络的能量消耗最小。然后, 提出了一种适用于节点非均匀分布的多跳路由选择机制。最后, 实验表明UCPOCS比LEACH、HEED和UCR三个著名协议能更有效地均衡网络能量消耗, 延长网络寿命, 从而避免能量空洞问题。

The authors have declared that no competing interests exist.

参考文献

View Option

[1]	付帅, 马建峰, 李洪涛, 等. 改进的基于分簇无线传感器网络的数据融合算法[J]. 吉林大学学报: 工学版, 2014, 44(4): 1118-1125. Fu Shuai, Ma Jian-feng, Li Hong-tao, et al. Improved data aggregation algorithm based on clustered wireless sensor networks[J]. Journal of Jilin University (Engineering and Technology Edition), 2014, 44(4): 1118-1125. [本文引用:2]
[2]	Liu A F, Wu X Y, Chen Z G, et al. Research on the energy hole problem based on unequal cluster-radius for wireless sensor networks[J]. Computer Communications, 2010, 33(3): 302-321. [本文引用:2]
[3]	Jia Jie, Chen Jian, Wang Xing-wei, et al. Energy-balanced density control to avoid energy hole for wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2012: 812013. [本文引用:1]
[4]	Liu An-feng, Jin Xin, Cui Guo-hua, et al. Deployment guidelines for achieving maximum lifetime and avoiding energy holes in sensor networks[J]. Information Sciences, 2013, 230: 197-226. [本文引用:1]
[5]	Lian J, Naik K, Agnew G B. Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[J]. International Journal of Distributed Sensor Networks, 2006, 2(2): 121-145. [本文引用:1]
[6]	Chen G H, Li C F, Ye M, et al. An unequal cluster-based routing protocol in wireless sensor networks[J]. Wireless Networks, 2009, 15(2): 193-207. [本文引用:3]
[7]	Band yopadhyay S, Coyle E. An energy efficient hierarchical clustering algorithm for wireless sensor networks[C]∥Proceedings of IEEE INFOCOM, San Francisco, CA, 2003: 1713-1723. [本文引用:2]
[8]	Younis O, Fahmy S. HEED: a hybrid, energy-efficient distributed clustering approach for ad hoc sensor networks[J]. IEEE Transactions on Mobile Computing, 2004, 3(4): 366-379. [本文引用:2]
[9]	Soro S, Heinzelman W B. Prolonging the lifetime of wireless sensor networks via unequal clustering[C]∥Proceedings of 19th IEEE International Conference on Parallel and Distributed Processing Symposium, Washington DC, USA, 2005: 1-8. [本文引用:2]
[10]	Mhatre V, Rosenberg C. Design guidelines for wireless sensor networks: communication, clustering and aggregation[J]. Ad Hoc Networks, 2004, 2(1): 45-63. [本文引用:1]
[11]	Liu A F, Zhang P H, Chen Z G. Theoretical analysis of the lifetime and energy hole in cluster based wireless sensor networks[J]. Journal of Parallel Distributed Computing, 2011, 71(10): 1327-1355. [本文引用:1]
[12]	Bagci H, Yazici A. An energy aware fuzzy approach to unequal clustering in wireless sensor networks[J]. Applied Soft Computing, 2013, 13(4): 1741-1749. [本文引用:1]
[13]	Chen Y X, Chuah C N, Zhao Q. Network configuration for optimal utilization efficiency of wireless sensor networks[J]. Ad Hoc Network, 2008, 6(1): 92-107. [本文引用:1]
[14]	王小明, 安小明. 具有能量和位置意识基于ACO的WSN路由算法[J]. 电子学报, 2010, 38(8): 1763-1769. Wang Xiao-ming, An Xiao-ming. An energy and location aware ACO based routing algorithm for wireless sensor networks[J]. Acta Electronica Sinica, 2010, 38(8): 1763-1769. [本文引用:1]
[15]	Younis O, Krunz M, Ramasubramanian S. Node clustering in wireless sensor networks: recent developments and deployment challenges[J]. Network, 2006, 20(3): 20-25. [本文引用:1]
[16]	Li H, Liu Y L, Chen W F, et al. COCA: constructing optimal clustering architecture to maximize sensor network lifetime[J]. Computer Communications, 2013, 36(3): 256-268. [本文引用:1]

2014

0.0

. 2014, 44(4):1118-1125 DOI:10.13229/j.cnki.jdxbgxb201404033

Improved data aggregation algorithm based on clustered wireless sensor networks

改进的基于分簇无线传感器网络的数据融合算法

Fu Shuai , Ma Jian-feng , Li Hong-tao

付帅, 马建峰, 李洪涛

1.School of Computer Science and Technology, Xidian University, Xi'an 710071, China; 2.College of Information Technical, Hebei Normal University, Shijiazhuang 050024, China

In order to effectively prolong the lifetime of cluster-based Wireless Sensor Networks (WSNs), an improved Energy-Efficient Separation Algorithm (EESA) is proposed to solve the uneven energy dissipation problem. On the basis of inter-cluster energy balance, the basic clustering algorithm is improved. EESA uses network topology and energy consumption to calculate q cluster radius. The selection strategy of cluster heads is modified from the perspective of task separation, in which the task of a single cluster head is assigned to two nodes to obtain the intra-cluster energy balance. Simulation results show that EESA can avoid the energy hole problem effectively and reduce energy consumption of the whole WSN, thus prolonging the network lifetime.

为了有效地延长分簇无线传感器网络的寿命, 提出了一种改进的解决不均衡能量消耗问题的新算法EESA(Energy-efficient separating algorithm)。在考虑簇间能耗平衡的基础上, 根据网络拓扑和能量消耗来计算簇半径, 对基本的簇划分方式进行了改进, 并通过将单个簇头的任务分配给两个节点完成以实现簇内的能耗平衡的方法从任务分离角度对簇头选举策略进行了改进。仿真结果表明:EESA可以有效避免能量洞问题, 并减少整个传感器网络的能量消耗, 从而延长了网络寿命。

... 0 引言目前,无线传感器网络(Wireless sensor networks,WSNs)因其广阔的应用前景成为国内外的研究热点^[1] ...

... 2 能耗模型本文采用经典的能量消耗模型^[1],其中发送时的能量消耗为式(1)所示,接收时的能量消耗如式(2)所示 ...

2010

0.0

... 在多个传感器节点和一个Sink节点的多对一类型的无线传感器网络中,由于距离Sink较近的节点承担大量的数据中转,能量消耗高于网络中的其他区域,进而形成了能量空洞现象^[2,3,4] ...

... 目前,根据分簇过程中竞争簇半径的不同,主要分为等簇的^[7,8]和不等簇的^[2,6,9]数据收集协议 ...

2012

0.0

2013

0.0

2006

0.0

2009

0.0

... 分簇的数据收集协议是解决能量空洞问题的有效方法之一^[6] ...

... 目前,根据分簇过程中竞争簇半径的不同,主要分为等簇的^[7,8]和不等簇的^[2,6,9]数据收集协议 ...

... UCR^[6]是经典的不等簇数据收集协议,其主要思想是在距离Sink较近的簇具有较小的簇规模,而在距离Sink较远的簇形成较大的簇规模 ...

2003

0.0

... 目前,根据分簇过程中竞争簇半径的不同,主要分为等簇的^[7,8]和不等簇的^[2,6,9]数据收集协议 ...

... LEACH协议^[7]是首次被提出的具有等簇的数据收集协议,其思想是通过预先设定的相同概率以扰动的方式随机选取簇首节点,簇首收集完簇内成员的数据后,以直接传送的方式发送到汇聚点Sink ...

2004

0.0

... 目前,根据分簇过程中竞争簇半径的不同,主要分为等簇的^[7,8]和不等簇的^[2,6,9]数据收集协议 ...

... HEED协议^[8]弥补了LEACH协议中的不足之处,其采用剩余能量高的节点充当簇首节点,有效降低随机选举簇首节点的能耗 ...

2005

0.0

... 目前,根据分簇过程中竞争簇半径的不同,主要分为等簇的^[7,8]和不等簇的^[2,6,9]数据收集协议 ...

... UCS协议^[9]首次提出采用不等簇的方式进行数据收集,其主要思想是采用分层的网络模型,首先从理论上获得各层的簇成员个数的期望,进而利用簇成员的个数来取得各层不等的簇半径 ...

2004

0.0

2011

0.0

2013

0.0

2008

0.0

... 这种启发式确定簇规模的方式不但无法使网络效率^[13]达到最大化,还严重影响簇首数据路由传输阶段的能量消耗 ...

2010

0.0

. 2010, 38(8):1763-1769

An energy and location aware ACO based routing algorithm for wireless sensor networks

具有能量和位置意识基于ACO的WSN路由算法

Wang Xiao-ming , An Xiao-ming.

王小明, 安小明

An energy and location aware ACO based routing algorithm (ELACO) for WSNs is also designed by fusing the energy and location information of nodes.To bypass dead ends,a backward routing mechanism is established,as a result,the routing success rate increases.Simulation results show that the ELACO has a higher search success rate,efficiently balance node energy consumption to prolong the network lifetime.

通过融合传感器节点的剩余能量和地理位置信息,设计一种具有传感器节点能量和地理位置意识的基于蚁群优化方法的无线传感器网络路由算法(ELACO);针对路由空洞现象,提出一种路由回退机制,提高了路由搜索成功率.仿真结果表明,ELACO算法具有很高的路由查寻成功率,能够更好地均衡传感器节点能量消耗,从而延长网络使用寿命.

2006

0.0

... 在这期间,向汇聚点Sink传输多少轮数据后重新构簇获得最大的网络寿命仍是一个开放性的问题^[15,16] ...

2013

0.0

... 在这期间,向汇聚点Sink传输多少轮数据后重新构簇获得最大的网络寿命仍是一个开放性的问题^[15,16] ...