大规模无线传感网基于CFSFDP和泊松混合模型的分簇路由算法*

陶志勇,王和章,刘 影

(辽宁工程技术大学电子与信息工程学院,辽宁 葫芦岛 125105)

大规模无线传感网基于CFSFDP和泊松混合模型的分簇路由算法*

陶志勇*,王和章,刘 影

(辽宁工程技术大学电子与信息工程学院,辽宁 葫芦岛 125105)

针对无线传感网随规模的扩大其节点能量利用率较低的问题,提出了一种适用于大规模无线传感网的基于CFSFDP和泊松混合模型的分簇路由算法(CRCPMM)。其核心思想是:在基站利用改进的CFSFDP算法自动估计簇的数目K值并选取聚类中心,然后运用泊松混合模型将节点合理聚类,以保证聚类效果最优;簇间采用多跳传输方式,综合考虑簇首等效剩余能量、簇首之间的距离以及多跳路径与理想最优路径之间的角度。仿真结果表明:与低功耗自适应集簇(LEACH)协议、分布式能量有效非均匀成簇(DEBUC)协议相比,CRCPMM协议在大规模网络中具有明显的优势,能够有效均衡节点能耗,延长网络生命周期。

无线传感器网络;能耗均衡;CFSFDP;泊松混合模型;角度

随着MEMS(Micro Electro Mechanical System)和无线通信技术的发展,无线传感器网络WSN(Wireless Sensor Networks)的应用越来越广泛,如军事侦察、医疗监护等[1]。WSN是由大量廉价的具有一定计算、存储和通信能力的传感器节点相互协作而形成的,传感器节点一般采用能量受限的电池供电,且部署后无法更换,这严重限制了WSN的发展[2]。由于传感器节点的能耗与网络的路由息息相关,因此如何设计能量高效的路由协议成为了WSN研究的重要目标[3]。

为了延长网络生命周期[4],许多基于成簇的路由协议被提出[5]。分簇减少了数据的冗余度,降低了传输能耗。早期的成簇路由协议大多采用单跳通信的方式,其网络扩展性较差。随着研究的深入,越来越多的成簇网络采用多跳通信的方式,这虽然能够节省能量,但易导致能量空洞[6]。

LEACH[7]是最早提出的一种均匀分簇路由协议,相比较于平面路由协议,其能量利用率较高,生命周期较长;但随机的簇首选举和簇间单跳通信易导致某些节点由于能耗过快而过早死亡。因此,李成法等人[8]提出了一种不均匀的成簇路由协议-EEUC(Energy-Efficient Uneven Clustering),它通过控制簇首的竞争半径来调整簇的规模,使靠近基站的簇规模较小,这样距离基站较近的簇首会由于簇内能耗的降低而预留足够的能量来转发其他簇首的数据;然而簇首的选择只由概率和门限值决定,无法保证所选簇首最优。Hui等人[9]提出了混合整数线性规划模型,以此来确定簇首的最佳位置。陈海南等人[10]提出利用遗传算法和概率准则的有效结合来均衡网络能耗。张雅琼[11]提出利用K-means算法均匀分簇,避免了极大簇和极小簇的情况;但K-means算法对初始聚类中心敏感,聚类效果不理想。Rodriguez等人[12]提出了一种综合考虑局部密度和距离的聚类算法-CFSFDP(Clustering by Fast Search and Find of Density Peaks),该算法能够从网络中选取最优聚类中心;但聚类中心的选择需要借助人工辅助,很难应用于实践。因此,在此基础上,马春来等人[13]提出了一种聚类中心自动选取策略,通过引入拐点实现CFSFDP算法的自动化。

蒋畅江等人[14]提出了DEBUC(Distributed Energy-Balanced Unequal Clustering)协议,它利用节点的竞争半径选择候选簇首,根据候选簇首以及其邻居节点的剩余能量通过基于时间的竞争算法选举最终簇首,同时在簇间运用贪婪算法选择中继节点,均衡了能耗;但由于随着网络规模的增大,竞争半径逐渐增加,簇内通信距离达到自由空间模型的极限值,导致数据传输时能耗增加较快。孙彦清等人[15]提出了UCDP(Uneven Clustering routing protocol based on Dynamic Partition)协议,它利用能量均衡的非均匀分区算法将网络合理动态分区,选举簇首与区头协作通信,通过簇内单跳、区内以及区间多跳相结合的方式建立一个能耗最优的路由协议;但在路径建立时,簇内以及簇间需要多次通信。

本文综合以上问题,在改进算法的基础上提出了一种适用于大规模无线传感网的分簇路由算法。该算法在基站利用改进的CFSFDP算法自动估计类数K值和选取聚类中心;通过泊松混合模型将节点依概率合理分簇;在簇间采用多跳路由方式,将等效能量、距离和角度因素相结合,对多跳路径进行优化。实验数据表明:该协议能够有效延长网络寿命,均衡节点能耗,并且在大规模网络中具有良好的性能。

1 网络模型与能耗模型

1.1 网络模型

本文假设N个传感器节点随机分布在M×M的监测区域内,且传感器网络具有如下性质[14]:①基站在监测区域外,传感器节点在监测区域内,部署后位置均不变。②所有节点同构,即具有相似的能力(处理/通信),且都有唯一的节点标识号。③链路对称,即已知发射端的发射功率,接收端可以根据接收到的信号强度估算两者的距离。④节点的发射功率以及通信半径可以根据需要自动调整。⑤节点具有位置感知能力。⑥相对于节点感知范围而言,监测区域远大于单个节点的感知区域。

1.2 能耗模型

本文采用文献[7]的能耗模型,即一阶无线电模型。发射端向距离为d的接收端发送l比特数据的能耗为:

(1)

接收端接收l比特的数据所消耗的能量为:

ERx(l)=lEelec

(2)

簇首将普通节点的数据进行融合同样需要消耗能量,本文采用文献[15]的融合模型,即无论簇首接收到多少普通节点的数据均将其融合成l比特。

2 大规模分簇路由算法-CRCPMM

针对LEACH协议以及大多基于其改进的路由协议如DEBUC等随着网络规模的扩大其能量利用率较低的问题,本文提出了一种基于CFSFDP和泊松混合模型的大规模无线传感网分簇路由算法。该算法通过在基站运行改进的CFSFDP算法来估计K值和选取聚类中心,然后在此基础上利用泊松混合模型实现K值的优化和节点分簇;同时在簇间综合考虑等效能量因素、距离因素以及角度因素,建立最优多跳传输路径。

2.1 改进的CFSFDP算法

经典聚类算法如K-means、K-medoids等在聚类时首先需要确定最终聚类数K以及初始种子节点,而两者的选择大多采用随机或人为指定的方式,这使得算法带有一定的主观性和随意性。因此本文提出在利用泊松混合聚类前先采用改进的CFSFDP聚类算法选取初始种子节点以及估计网络K值。为了降低能耗,本文采用集中式的方法,由基站控制运行改进的CFSFDP算法。

局部密度ρi主要用来刻画聚类中心的邻居节点个数。邻居节点个数越多,ρi越大;反之,ρi越小。根据局部密度的含义,其表达式为:

(3)

式中:dc为截断距离。由式(3)可知,与节点xi的距离小于dc的节点数越多,ρi越大。

d1≤d2≤…≤dNN

(4)

取dc=df(NNt),f(NNt)表示对NNt进行四舍五入运算,t取经验值0.02[12]。

ρq1≥ρq2≥…ρqN

(5)

根据距离的含义,其表达式为:

(6)

尽管CFSFDP无需复杂的参数设置和迭代运算[13],但是在选取聚类中心时仍需要人工辅助。基于此,本文在局部密度ρi和距离δi的基础上提出一种适用于CFSFDP的聚类中心自动选取策略,其核心思想在于对决策图中拐点的刻画。

聚类中心自动选取策略首先将ρi和δi的归一化乘积γi作为节点的决策值,其表达式为式(7)。然后将γi按照降序排列并取前n(n=N/3)[13]个节点作为聚类中心候选节点。本文以网络中共有100个节点为例,其决策图如图1。

(7)

图1 决策图

由图1可知,按照γi减小的方向聚类中心候选节点的密度逐渐增大,且在某一特殊点密度变化最大,此特殊点即为拐点。候选节点xi的密度为与xi的γi值小于ε的其他候选节点数目,其表达式为:

(8)

式中:χij为特殊函数,其计算公式为:

(9)

为了更好地刻画拐点,本文引入密度变化率,其表达式为式(10)。根据上述拐点的含义,密度变化率最大的候选节点即为拐点,图1的拐点判断图如图2所示。设拐点的决策值为γt,则K值为决策值不小于γt的聚类中心候选节点数目,其所对应的节点即为初始种子节点。本文以上述K值和初始种子节点对泊松混合聚类进行初始化。

DCRi=βi+1-βi

(10)

图2 拐点判断图

2.2 加速泊松混合聚类

在二维地理空间位置部署的大量传感器节点通常是独立随机分布的,这种分布方式适用于分析没有先验知识的地理环境。传感器节点通常采用高空洒落的方式部署在难以监测的环境中,节点的位置可以看作服从二维泊松分布[16]。设传感器节点在单位监测区域A内呈密度为λ的随机分布,则区域内的节点数N(A)服从泊松分布,其概率为:

(11)

式中:‖A‖表示单位监测区域的面积。

2.2.1 建立泊松混合模型

传统聚类算法如DBSCAN、Birch、AGNES等判断节点的所属类时一般只考虑距离因素,并没有关注节点的分布;而在实际环境中,节点是否属于某一类与节点的分布有较大的关系。针对上述思想,本文提出了一种基于泊松混合模型的加速聚类算法。

假设服从泊松混合分布的随机节点为xi,则其概率可表示为:

(12)

式中:πk为每个泊松模型分量的混合系数,代表其所包含的节点数占总节点数的比例;K为泊松模型分量的个数;MDik为节点xi与聚类中心ck的曼哈顿距离,MDmin为MDik的最小值,即MDmin=min{MDik,k=1,2,…,K};P(xi|λk,nk)表示第k个泊松模型的分布律,λk为其均值,nk为该模型分量所包含的节点数,其表达式为:

(13)

设Z={zik}为隐变量集,zik表示节点xi属于第k类的概率,泊松模型的参数为θk=(λk,nk),则节点集的最大对数似然函数为:

(14)

2.2.2 改进的EM算法

本文采用EM算法迭代求解式(14)的最大似然参数。EM算法(Expectation Maximization Algorithm)是一种迭代优化求解概率模型参数的最大似然估计方法,其具体步骤分为两步:E-Step和M-Step。

对式(14),由Jensen不等式可得:

(15)

(16)

(17)

由EM算法求出最大似然参数估计值。其中,混合系数:

(18)

泊松模型分量的均值:

(19)

隐变量:

(20)

(21)

(22)

(23)

为了在泊松混合聚类的迭代初期使参数θk快速逼近最优解,本文采用Steffensen加速方法。当θk接近最优解时,由于EM算法步长变化缓慢,本文使用Broyden对称秩1校正公式进行校正,使算法快速收敛。因此在整个迭代周期算法的迭代次数明显减少,达到了加速收敛的目的。

(24)

式中:α为调节系数,满足0≤α≤1,其取值为:

(25)

为了使算法快速逼近最优解,迭代开始时令α=1,同时初始化混合系数πk=1/K。随着迭代的进行,相比较于式(14),式(24)的似然函数L(zik,πk|x)增加速度较快,且前后两次迭代的混合系数差异越来越小,直到α=0,迭代停止。

(26)

(27)

(28)

2.2.3 求解最优K值

2.2.4 加速泊松混合聚类的基本步骤

Step 10 利用隐含参数信息熵原理,求出三维数组Ω中不同K值的信息熵H,则H的最小值所对应的K值即为泊松模型成份数的最优解。

Step 11 根据最优成份数K值所对应的zik以及能耗均衡性确定节点的簇标记,即对于节点xi,从zik中选择两个较大值,并计算其能负比,从中选择值最大的作为节点的簇。能负比为聚类中心的剩余能量与该类中节点数的比值,其表达式为式(29),Ej表示剩余能量,nj表示节点个数。

ECRj=Ej/nj

(29)

由以上步骤可以看出,加速泊松混合聚类在每次迭代过程中有一次分量的消除过程(Step 5)以及两次加速收敛的步骤(Step 2和Step 8),这将大大地减少算法的迭代次数。同时算法拥有最佳K值以及节点簇标记的判定过程(Step 10和Step 11),这将使最终得到的模型成份数最优,节点聚类更合理。聚类完成后,算法进入簇内选择簇首阶段。

2.3 簇首选择

本文算法在簇内采用文献[17]的三级簇首选择机制选举簇首,同时考虑剩余能量、簇内总能耗以及簇内节点的能耗均衡3个因素。

由文献[15]可知,节点可以获取自身的当前剩余能量Er;由1.1可知,节点具有位置感知能力,即任意两个节点之间的距离是已知的,则簇内某一节点当选为簇首时的簇内总能耗TECi为:

(30)

式中:l,Eelec,εfs,dk-i的意义与式(1)相同。

由式(1)可知,簇内节点向簇首发送数据时所消耗的能量与距离的平方成正比,簇内节点到簇首的距离的差异越小,簇内节点的能耗越均衡。因此,当簇内某一节点当选为簇首时,簇内节点的能耗均衡性EBi为:

(31)

首轮时,簇内所有节点参与竞选,选举的簇首不但具有较高的剩余能量,而且能够保证簇内总能耗较低和簇内节点能耗均衡。后续轮次时,本文算法采用由上一轮簇首指定下一轮簇首的方式。若上一轮簇首的剩余能量最高,则簇首不变;否则,上一轮簇首根据节点剩余能量以及与自身的距离选择下一轮簇首。下一轮簇首与上一轮簇首的距离越近,簇内总能耗越低,簇内节点能耗越均衡。簇首确定后,算法进入稳定的数据传输阶段。

2.4 数据传输

数据传输阶段分为簇内通信和簇间通信。在簇内,若节点到基站的距离小于到簇首的距离,则节点直接将数据传输至基站,否则,节点将数据传输至簇首。在簇间,采用数据包在相邻簇首间中继转发的方式,相邻簇首包括已当选为簇首的节点和直接与基站通信的节点。

簇间中继时,下一跳簇首的选择除了与等效剩余能量和距离有关外,实际上还与方向有关[18]。因此,本文提出了一种综合考虑等效能量、距离和角度的多跳路由策略。

根据贪婪边界无状态路由GPSR[18]的思想,下一跳簇首应具有较大的前进距离。设N为当前簇首,M为下一跳簇首,T为基站。为了更好地衡量前进距离,本文提出相对距离的概念。相对距离即下一跳簇首到基站的距离与当前最优路径的比值,当前最优路径为当前簇首与基站的连线,其表达式为:

(32)

根据CR[18]的思想,路由策略应选择与当前最优路径夹角φ较小的簇首作为下一跳,这样选择的下一跳路径能最快收敛于当前最优路径,且整个转发路径最先收敛于理想最优路径,理想最优路径为源簇首到基站的连线。在WSN中,该夹角φ可以通过定位技术计算得出[19]。考虑余弦函数的特性,当夹角越小时,其值越大,否则,其值越小。因此,本文以cosφ来衡量下一跳路径与当前最优路径的夹角。

为了均衡簇首的能耗,路由策略应选择等效剩余能量较大的簇首作为下一跳。等效剩余能量为簇首剩余能量与簇内节点个数的关系,本文以sin(πEi)来衡量簇首的剩余能量,以式(33)来衡量簇内节点个数,mi为第i个簇内的节点数,mmax为最大的簇所包含的节点数。等效剩余能量的计算公式为式(34),由公式可知,簇首剩余能量越大,所包含的节点数越少,其等效剩余能量越大。

(33)

(34)

综上,新的簇间路由策略应选择等效剩余能量较大、相对距离较近且角度较小的簇首作为下一跳。本文以值Wi作为其度量标准,其计算式为:

(35)

2.5 算法时间复杂度分析

CRCPMM算法的时间复杂度由四部分组成,即CFSFDP的时间复杂度、加速泊松混合聚类的时间复杂度以及簇首选择和数据传输的时间复杂度。

假设网络中共有N个节点,候选聚类中心个数为n,簇首数目为K,则CRCPMM算法的时间复杂度为O(N2)。

证明CRCPMM算法利用改进的CFSFDP自动估计聚类中心个数。首先,基站计算参数dij,ρi,δi,时间复杂度均为O(N2);其次,计算ρi和δi的归一化乘积γi,并将γi按照降序排列,时间复杂度分别为O(N)和O(nlogn);然后,计算βi和密度变化率DCRi,时间复杂度分别为O(n2)和O(n)。因此,CFSFDP的时间复杂度为:

O(N2+N2+N2+N+nlogn+n2+n)=O(N2)

(36)

在加速泊松混合聚类中,首先建立泊松混合模型,时间复杂度为O(N);其次,利用EM算法迭代求解概率模型参数,设迭代次数为t,则其时间复杂度为O(NKt);然后将节点聚类,时间复杂度为O(N)。因此,加速泊松混合聚类的时间复杂度为O(N+N+NKt)。

在簇首选择过程中,节点需要计算其作为簇首时的TECi和EBi,时间复杂度均为O(N)。在数据传输过程中,簇首需要计算下一跳簇首的EREi,cosφ,Rd,时间复杂度均为O(K2)。因此,簇首选择和数据传输过程的时间复杂度为O(N+N+K2+K2+K2),即O(N+K2)。

根据以上分析,由于N≥K且N≥t,因此整个算法的时间复杂度为O(N2)。

3 实验分析

为了验证CRCPMM算法的性能,本文分别在不同的网络规模下仿真LEACH[7]、DEBUC[14]和CRCPMM 3种协议的网络寿命、网络总能耗以及节点平均剩余能量,横坐标为仿真时间,以轮数表示。其中,4种网络规模分别为100 m×100 m、200 m×200 m、400 m×400 m以及800 m×800 m,网络中的节点总数分别为100、400、1600和6400。具体仿真参数如表1所示。

表1 仿真参数表

3.1 网络寿命

本文定义网络寿命为从WSN的第一轮开始到10%节点失效的轮数。图3～图6分别为4种不同网络规模下3种协议的网络寿命对比图,纵坐标为网络中存活的节点个数。

图3 规模为100 m×100 m的网络寿命对比

图4 规模为200 m×200 m的网络寿命对比

图5 规模为400 m×400 m的网络寿命对比

图6 规模为800 m×800 m的网络寿命对比

由以上4个图可知,随着网络规模的增大,3种协议的网络寿命在不断减小。在小规模网络中(如图3和图4),3种协议的网络寿命分别为435轮、516轮、559轮和389轮、488轮、546轮,相对于LEACH和DEBUC协议,CRCPMM协议在网络寿命上分别延长28.5%、8.33%和40.35%、11.88%;在中规模网络中(如图5),3种协议的网络寿命分别为135轮、416轮和526轮,CRCPMM协议在网络寿命上分别延长289.6%和26.44%;而在大规模网络中(如图6),3种协议的网络寿命分别为48轮、241轮和383轮,CRCPMM协议在网络寿命上分别延长697.9%和58.92%。

以上数据表明:相比较于小规模和中规模网络,CRCPMM协议在大规模网络中能够明显延长网络寿命。这是因为随着网络规模的增大,LEACH协议的单跳通信以及DEBUC协议竞争半径的增加导致了能量的快速消耗,而本文利用改进的CFSFDP算法和泊松混合模型优化了K值,实现了节点的最优聚类,降低了能量的消耗速度,因此CRCPMM协议更加适用于大规模网络。

3.2 网络总能耗

图7～图10为4种不同网络规模下3种协议的网络总能耗对比图,纵坐标为网络的总能量消耗。

图9 规模为400 m×400 m的网络总能耗

图7 规模为100 m×100 m的网络总能耗

图8 规模为200 m×200 m的网络总能耗

图10 规模为800 m×800 m的网络总能耗

由图7～图10可知,在小规模(如图7和图8)和中规模网络中(如图9),3种协议的总能耗差异相对较小;而在大规模网络中(如图10),CRCPMM协议的总能耗明显低于其余两种协议,说明在大规模网络中CRCPMM协议能够有效降低能耗。

随着网络规模的增大,LEACH协议由于簇间采用单跳通信,其节点能耗增加较快;DEBUC协议由于竞争半径增大,簇内采用多径衰落模型,其能耗增加也较快;而本文算法通过将改进的CFSFDP和泊松混合聚类相结合,优化了簇的数目K值,选举了最优聚类中心,实现了节点的合理分簇,减缓了能耗的增加速率。因此,CRCPMM协议更加适应于大规模网络。

图12 规模为200 m×200 m的节点平均剩余能量

3.3 节点平均剩余能量

图11～图14为4种不同网络规模下3种协议的节点平均剩余能量对比图,纵坐标为节点的平均剩余能量。

图11 规模为100 m×100 m的节点平均剩余能量

图13 规模为400 m×400 m的节点平均剩余能量

图14 规模为800 m×800 m的节点平均剩余能量

节点的平均剩余能量越高,节点的能耗越均衡。从图中可以得出,在小规模(如图11和图12)和中规模网络中(如图13),3种不同协议的节点平均剩余能量虽然不同,但差异相对较小;而在大规模网络中(如图14),本文算法的节点平均剩余能量在相同的轮数(如200轮)都明显高于其余两种协议,这说明在大规模网络中CRCPMM协议能够更好地均衡节点能耗。

随着监测区域规模的增加,LEACH协议中与基站较远的簇首和与基站较近的簇首的能耗差距逐渐增大;DEBUC协议在簇间通信时由于重点考虑距离因素会使得簇首在选择下一跳节点时过多偏离理想最优路径,从而增加多跳跳数和能量消耗;而本文算法不仅在节点聚类时考虑了能负比,且在多跳通信时综合考虑了等效剩余能量因素、距离因素和角度因素,在保证多跳路径偏离最优路径较小的情况下,选择能耗均衡的下一跳簇首。因此,与其余两种协议相比,CRCPMM协议更加适应于大规模网络。

4 结束语

针对诸多路由协议如LEACH、DEBUC等在大规模无线传感网中的局限性,本文提出了一种适用于大规模网络的基于CFSFDP和泊松混合模型的分簇路由算法。该算法利用改进的CFSFDP和泊松混合模型实现节点的合理分簇;在簇间兼顾等效能量、距离和角度建立能耗均衡的多跳路径。实验仿真表明:与LEACH、DEBUC协议相比,本文算法在大规模网络中具有较明显的优势,能够有效延长网络生命周期,均衡节点的能耗。

虽然本文算法在大规模网络中表现了良好的性能,但实际环境中移动节点以及异构网络的应用越来越广泛,为了更好地适应传感器网络的发展,下一步的主要工作是在异构网络中对算法做出改进,使其更加适用于实际场合。

[1] Zhang D,Li G,Zheng K,et al. An Energy-Balanced Routing Method Based on Forward-Aware Factor for Wireless Sensor Network[J]. IEEE Transactions on Industrial Informatics,2013,10(1):766-773.

[2] Gherbi C,Aliouat Z,Benmohammed M. An Adaptive Clustering Approach to Dynamic Load Balancing and Energy Efficiency in Wireless Sensor Networks[J]. Energy,2016(114):647-662.

[3] Arora V K,Sharma V,Sachdeva M. A Survey on LEACH and Other’s Routing Protocols in Wireless Sensor Network[J]. Optik-International Journal for Light and Electron Optics,2016,127(16):6590-6600.

[4] 吴勇,张灵. 基于多目标优化的WSN簇首选择算法[J]. 传感技术学报,2016,29(7):1062-1067.

[5] Barati H,Movaghar A,Rahmani A M. EACHP:Energy Aware Clustering Hierarchy Protocol for Large Scale Wireless Sensor Networks[J]. Wireless Personal Communications,2015,85(3):765-789.

[6] Mohemed R E,Saleh A I,Abdelrazzak M,et al. Energy-Efficient Routing Protocols for Solving Energy Hole Problem in Wireless Sensor Networks[J]. Computer Networks,2017,114(2):51-66.

[7] Heinzelman W,Chandrakasan A,Balakrishnan H. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communication,2002,1(4):660-670.

[8] 李成法,陈贵海,叶懋,等. 一种基于非均匀分簇的无线传感器网络路由协议[J]. 计算机学报,2007,30(1):27-36.

[9] Lin H,Uster H. Exact and Heuristic Algorithms for Data-Gathering Cluster-Based Wireless Sensor Network Design Problem[J]. IEEE Transactions on Networking,2014,22(3):903-916.

[10] 陈海南,刘广聪,吴晓鸽,等. 一种基于遗传算法与概率转发的分簇协议[J]. 计算机科学,2015,42(3):71-73.

[11] 张雅琼. 基于K-means的无线传感网均匀分簇路由算法研究[J]. 控制工程,2015,22(6):1181-1185.

[12] Rodriguez A,Laio A. Clustering by Fast Search and Find of Density Peaks[J]. Science,2014,344(6191):1492-1496.

[13] 马春来,单洪,马涛,等. 一种基于CFSFDP改进算法的重要地点识别方法研究[J]. 计算机应用研究,2017,34(1):136-140.

[14] 蒋畅江,石为人,唐贤伦,等. 能量均衡的无线传感器网络非均匀分簇路由协议[J]. 软件学报,2012,23(5):1222-1232.

[15] 孙彦清,彭舰,刘唐,等. 基于动态分区的无线传感器网络非均匀成簇路由协议[J]. 通信学报,2014,35(1):198-206.

[16] Liu B Y,Towsley D. A Study of the Coverage of Large-Scale Sensor Networks[C]//Proceedings of 2004 IEEE International Conference on Mobile Ad-Hoc and Sensor Systems. Piscataway:IEEE Press,2004:475-483.

[17] 翟春杰,徐建闽,刘永桂. 基于分区的能耗均衡路由协议[J]. 传感技术学报,2016,29(1):80-87.

[18] 谢志恒,张向利,何龙,等. 基于距离和角度的无线传感器网络路由方案[J]. 计算机工程与应用,2010,46(31):109-110.

[19] 李建洲,王海涛,陶安. 一种能耗均衡的WSN分簇路由协议[J]. 传感技术学报,2013,26(3):396-401.

陶志勇(1978-),男,博士,副教授,硕士生导师,主要研究方向是多媒体通信,82456020@qq.com;

王和章(1992-),男,硕士研究生,主要研究方向是无线传感网路由协议;

刘影(1983-),女,博士,讲师,主要研究方向是无线网络定位和物联网。

ClusteringRoutingAlgorithmBasedonCFSFDPandPoissonMixtureModelinLarge-ScaleWirelessSensorNetworks*

TAOZhiyong*,WANGHezhang,LIUYing

(School of Electrics and Information Engineering,Liaoning Technical University,Huludao Liaoning 125105,China)

With the expansion of the scale in wireless sensor networks,the node energy utilization becomes lower. A clustering routing algorithm is proposed,which was based on CFSFDP and poisson mixture model(CRCPMM)for the large-scale wireless sensor networks. Its core idea is that it uses modified CFSFDP algorithm to estimate theKvalue of the number of clusters and select clustering center automatically at base station. Then it utilizes poisson mixture model to cluster the nodes reasonably to ensure the optimal clustering. In the inter-cluster,the CRCPMM algorithm adopts multi-hop transmission mode,which considers cluster-heads equivalent residual energy,the distances among cluster-heads and the angles between multi-hop paths and ideal optimal path. Simulation results show that compared with the LEACH(Low Energy Adaptive Clustering Hierarchy)protocol and the DEBUC(Distributed Energy Balanced Unequal Clustering routing)protocol,the CRCPMM protocol has obvious advantages in the large-scale networks,which can balance energy consumption of nodes and extend the network lifetime effectively.

wireless sensor networks;energy consumption balancing;CFSFDP;poisson mixture model;angle

TP393

A

1004-1699(2017)11-1719-10

项目来源:国家自然科学基金项目(61240014);辽宁省自然基金项目(2015020100);辽宁省博士启动基金(20170520098)

2017-04-17修改日期2017-07-05

10.3969/j.issn.1004-1699.2017.11.018