分簇方法

2024-07-27

分簇方法（精选7篇）

分簇方法篇1

异构网络(heterogeneous network,Het Net)改变了传统网络的拓扑结构,在传统宏小区之上,以层叠覆盖的形式加入大量的低功率节点(low power node,LPN),如微基站(Pico)、家庭基站(Femto)等,形成分层的异构网络组网形式,缩短了用户与基站之间的距离,减少了覆盖盲区,能够为系统提供更高的数据传输速率,降低网络成本,实现了移动网络覆盖和容量的双重提升,是LTE-A中的一项重要的技术[1]。本文主要研究的低功率节点为微基站。

多基站协作通信可以有效抑制边缘用户的小区间干扰,各协作基站之间通过高速的光纤互联来实现大量的信息交互[2]。为此,在LTE-A系统中通过应用Co MP传输技术,来协作分布在不同地理位置的站点共同为边缘用户传输数据。但当系统规模比较大时,为避免超负荷的信息量,一般对可协同的基站群进行分簇,令簇内的基站采用协同处理技术[3]。目前,协作基站分簇方法主要有静态分簇和动态分簇。静态基站分簇方法是在网络规划初期进行基站簇的划分,根据地理分布位置相邻的基站划分为一簇,其分簇方式简单,容易实现。但是其簇结够固定,小区间干扰得不到最大消除,系统的实时性较差。针对以上问题提出了动态分簇算法[4—6],用户将实时的信道状态信息(CSI)反馈给基站控制端进行分析,动态的选择CSI好的基站去参与协作,形成协作基站簇。但是,随着异构网络的发展,其组网结构不断向分层结构发展,其在异构网中的适应程度和效率仍有待研究。文献[7]在异构组网场景下,通过设定阈值,以最大化接收端的传输速率为目标,考虑用户接收功率大小和其他基站对该用户的平均干扰情况进行分簇。但是对于存在多用户移动情况下的协作基站分簇方法还需要进一步研究。文献[8]提出了一种近邻传播分簇法,用接收功率的大小来表示距离的远近,对于任意基站,与超过一定地理区域外的基站之间的协作可以忽略。但是,实际信号的传输过程会受到环境因素和各种噪声的影响,距离最近的用户接受信号质量可能不是最佳的,因此需要考虑信道的影响和其他发送信号的干扰。针对以上问题,在异构的组网模式下,本文借助路径损耗对基站进行分簇,把基站分簇问题转化为最大化接收端的数据传输速率问题,通过设置路径损耗门限为各用户判决与其通信的协作基站,形成协作基站分簇。

1 系统模型的建立

本文讨论的异构网络场景为:考虑异构网络下行系统,系统中有B个宏基站,一个宏基站形成一个小区。每个小区的边缘随机分布着L个微小区,有K个用户随机分布在微小区中,如图1所示。

在图1的传输场景中,微基站服务下的用户Pico user1不仅接收到微基站Pico BS1发射的有用信号,还接收到收到宏基站Macro BS的干扰信号以及多用户之间的信息干扰[9]。假设宏基站的发射功率为PM,每个宏基站有M根发送天线,微基站的发射功率为PL,每个微基站有N根发送天线,用户采用单天线接收。考虑宏小区i中微基站l服务下的用户j,除了接收到微基站l发出的有用信号,还受到本小区以及相邻小区基站的干扰,以及多用户之间的干扰,其接收信号强度为:

式(1)中,Hl,l,j表示第i个小区中第l个微基站向其服务下的用户j传输数据的信道矩阵,VLn,l,j和Vl,l,j分别表示宏基站和微基站向用户传输数据过程中的预编码矩阵[10],xl,l,j表示微基站l向其服务下的用户发送的数据信息流。基站端发送信号的能量期望式(1)中第一项表示有用信号,第二项表示除用户j之外的多用户干扰,第三项表示小区i中其余微基站对用户的干扰情况,第四项表示宏基站对用户的干扰情况,第五项表示其余小区中微基站对用户j的干扰,第六项Ni,i,j表示均值为1,方差为α2的高斯白噪声。

对于宏小区i中微基站l服务下的用户j,有用信号功率为

干扰信号的功率为

小区i中微小区l服务下的用户j接收到的信干噪比(SINR)为

此时,用户j的数据速率可以表示为

若在微基站服务范围内有K个用户,则协作区域内用户的和速率为

由于LTE系统频率复用因子为1,这就造成由于资源块的重叠造成的多用户干扰,为消除共信道干扰,通常需要在基站端对需要发送的数据进行预编码。本文采用迫零(ZF)预编码[11],预编码矩阵V满足:

式(7)中,(·)H表示矩阵的共轭转置,(·)-1表示矩阵的逆。编码后的数据通过信道矩阵H后非对角线上的数据均为0,从而达到了干扰消除的目的。经过预编码后用户j的信干噪比为

2 分簇方案的实现

假设无线信道服从准静态瑞利平坦衰落,各基站端完全已知所有用户的信道状态信息(CSI),基站通过无线信道向用户广播信息。分簇方案具体步骤如下。

(1)对于微基站服务下的K个用户,将微基站作为其主服务基站,计算主服务基站到各个用户的路径损耗PLmasterl,j,j=1,2,…,K,再对路径损耗值进行求和作为主服务基站对所有用户的路径损耗;j=1,2,…,K。

(2)分别计算除主服务基站外其余基站对K个用户的路径损耗值之和PLm,m=1,2,…,B+BL-1,其中宏基站到用户的路径损耗为:128.1+37.6 lg(D),微基站到用户的路径损为:140.7+36.7 lg(d),式中D,d单位均为km,路径损耗的单位为d B。

(3)设置路径损耗门限a,将K个用户到主服务基站的路径损耗之和与K个用户到其余基站的路径损耗之和的差值与a进行比较,确定需要协作的基站的集合Ccoop,即

(4)形成协作基站簇。

此时,协作后用户的接收信干噪比(SINR)表示为

协作后用户的和速率为

将式(11)与公式(8)比较可知,经过协作干扰信号功率降低,有用信号功率增加,分簇后用户的接收信干噪比增加,从而使用户的数据传输速率得到了提高。

3 仿真结果与分析

本文依据异构网络模型下提出的基站分簇方案,通过设置合适的参数,利用Matlab软件进行了仿真,通过将微小区中边缘用户的传输速率作为性能指标,验证其方法的可行性,仿真参数见表1。

首先,分别验证不同分簇方法中用户平均速率随信噪比变化的增长趋势;其次,通过仿真对比得出二者之间的差值;最后,通过改变门限值的大小来观察速率的变化情况,选择合适的门限值。根据设置的仿真场景与仿真参数,最后得出的结果如图2、图3所示。

如图2所示,随着信噪比的增加,文献[7]中提出的阈值法、文献[8]提出的最近距离(功率最大)法与本文提出方法(路径损耗门限法)获得的用户传输和速率都呈增长趋势,且路径损耗门限法的用户速率高于阈值法和最大功率法。在信噪比为18d B时,路径损耗门限法获得的速率为5.82 bit/s,阈值法获得的数据速率为4.96 bit/s,二者相比平均数据速率有大约17%的提升。

如图3所示,两种算法用户之间的平均速率差随着信噪比的增加而不断变大。随着路径损耗的增大,受距离、环境等的影响加大,使得信号在传输过程中的损耗增多,相当于干扰信号强度增加,有用信号强度降低,用户端的接受信干噪比(SINR)减小,数据速率降低。随着各个基站与主机站间路径损耗差值的增大,需要进行协作的基站数目减少,满足式(9)的基站与用户j所处小区的微基站协作共同向用户j传输数据的速率,与功率阈值法在信噪比增加到一定的数值范围内相差不大,故而信噪比—平均速率差曲线最终会趋于平缓。

由于路径损耗门限值设置的不同会影响到其余基站是否与主服务基站进行协作,和用户收到的干扰的大小,从而影响到SINR的大小,最终会对接收端的数据传输速率产生影响,所以需要合理的选择参考门限值。图4给出了不同门限值的情况下数据速率的变化情况。当路径损耗门限设为a=24 d B时,获得的数据传输速率最大,也最理想。

4 结束语

作为下一代无线网络中的关键组网模式和技术手段,异构网络和协作多点传输在消除小区间干扰,提高接收端数据传输速率等方面起到了至关重要的作用。本文通过分析现有方法的不足,从路径损耗方面着手,提出了基于路径损耗门限的基站分簇方法,并且分析了不同路径损耗门限下数据速率随信噪比变化的情况,通过与最大功率法和功率阈值法的比较,确定了该分簇方法的优越性,在一定程度上能够使数据传输速率得到提升。但是对于阴影衰落情况,多个用户之间共享资源的公平性没有进行考虑,同时对于用户端的移动性问题也需要更深一步的研究。

摘要：在异构网络组网形式下,为了降低小区间干扰对边缘用户的影响,提高系统容量,对基站进行分簇研究。在多用户下的情况,以最大化边缘用户的和速率为目标,通过设置路径损耗门限来选择为用户进行协作通信的基站。分析对比了不同分簇方式下的用户平均速率情况,并且通过观察不同的门限值对应的速率变化情况,合理的选择门限值。仿真结果表明,该方法在一定程度上能够有效提高数据传输速率,当信噪比为18 d B时,路径损耗门限法在系统的平均传输速率方面较阈值法提升了1.02 bit/s,即用户的平均数据速率获得了17%的提升。

关键词：异构网络,基站协作,分簇,路径损耗门限,传输速率

参考文献

[1]张琛,粟欣,王文清,等.异构网络跨层协作传输技术研究.通信学报,2014;35(8):198-205Zhang C,Su X,Wang W Q,et al.A cross layer cooperative transmission technology research in heterogeneous network.Journal of Communication,2014;35(8):198-205

[2]肖海林,王鹏,聂在平,等.基于遗传算法的多基站协作通信功率分配方案.电子科技大学学报,2014;43(1):26-31Xiao H L,Wang P,Nei Z P,et al.Multi base station cooperative communication power allocation scheme based on genetic algorithm.Journal of University of Electronic Science and Technology of China,2014;43(1):26-31

[3]郑丽清.协同基站群的动态分簇算法研究.解放军信息工程大学,2011Zheng L Q.Dynamic clustering algorithm of cooperative base station group.The PLA Information Engineering University,2011

[4] Dehghani M,Arshad K,Mac Kenzie R.LTE-advanced radio access enhancements:a survey.Wireless Pers Commun,2015;80:891-921

[5]黄开枝,郑丽清,李坤,等.基于协同度的基站群利益树动态分簇算法.电子与信息学报,2012;34(6):1469-1475Huang K Z,Zheng L Q,Li K,et al.A dynamic clustering algorithm of base station group interest tree based on coordination degree.Journal of Electronics and Information,2012:1469-1475

[6]李坤,黄开枝,鲁国英,等.基于平均信干噪比的基站群分簇模型.计算机应用研究,2012;29(12):4699-4702Li K,Huang K Z,Lu G Y,et al.A base station cluster model based on average signal to noise ratio.Computer Application Research,2012;29(12):4699-4702

[7]韩东升,丁莎莎,余萍.一种基于阈值的无线异构网络基站分簇算法.电信科学,2015;(4):93-98Han D S,Ding S S,Yu P.A clustering method based on the threshold in wireless heterogeneous network.Telecommunications Science,2015;08(6):93-98

[8] Ng C T K,Huang H.Linear precoding in cooperative MIMO cellular networks with limited coordination clusters.IEEE Journal on Selected Areas in Communications,2010;28(9):1446-1454

[9]唐浩.LTE-A异构网络中的干扰协调机制研究.中国科学技术大学,2014Tang H.Research on interference coordination mechanism in LTE-Aheterogeneous networks.University of Science and Technology of China,2014

[10]祁美娟.MIMO系统中预编码技术研究.重庆大学,2012Qi M J.Study on precoding technique in MIMO systerm(masterdissertation).Chongqing University,2012

[11]王宏宇.多用户MIMO系统下行链路用户选择算法研究.哈尔滨:哈尔滨工业大学,2013Wang H Y.Research on user selection method for multi-uer MIMOsysterms.Harbin:Harbin Industrial University,2013

基于CPK的安全分簇方案篇2

无线传感器网络是由大量低成本但具有传感、数据处理和无线通信能力的节点通过自组织方式形成的网络, 具有大规模部署、拓扑结构动态变化、节点资源受限和自组织的特点。在军事应用、环境监测、建筑行业、医疗监护以及智能家居等领域都有着广泛的应用前景。由于传感器节点自身能力受限以及无线通信特性使网络面临着很多的安全威胁。在网络成簇过程加入认证机制, 可以有效增强层次结构网络的安全性。

1分簇算法分析

不同的应用中网络也存在着不同的拓扑结构。当前, WSN (无线传感器网络) 的拓扑结构存在星型、网状、树型以及分簇的层次结构。层次型的拓扑结构具有很多优点, 例如, 由簇头节点担负数据融合的任务, 减少数据通信量;分簇式的拓扑结构有利于分布式算法的应用, 适合大规模部署的网络[1]。通过对4种结构在可靠性、能量功效性、可量测性和时延特性的对比分析, 分簇的层次结构在能量使用效能和可量测性方面有着显著优势[2]。WSN层次结构的网络模型如图1所示。

LEACH (low-energy adaptive clustering hierarchy) 是WSN中提出的经典分簇算法。基本思想是通过等概率地随机循环选择簇首, 将整个网络的能量负载平均分配到每个传感器节点, 从而达到降低网络能量耗费、延长网络生命周期的目的[3]。LEACH算法工作流程如图2所示。

LEACH之后发展出的很多分簇协议都是沿用的这种思想。RDCA (Responsive Distributed Clustering Algorithm) 不需预先得知节点自身及其他节点的位置信息, 而仅根据局部拓扑信息快速进行分布式的簇头选举, 并根据代价函数进行簇的划分, 适用于周期性获取信息的无线传感器网络[4]。EBCA (Energy Balancing Clustering Algorithm) 将WSN分成均匀的格, 在格内进行簇头的选举, 仿真结果表明这种分簇算法可以很好地均衡节点之间能量消耗, 延长网络寿命[5]。传感器网络中的分簇算法已经得到广泛的研究, 以上算法都没有引入安全机制, 这将为后续的安全实现带来过多的困难和过高的成本。

2CPK算法

CPK密钥管理体制既可以基于一般有限域离散对数问题构建, 也可以基于椭圆曲线离散对数问题构建。鉴于椭圆曲线离散对数问题在密码应用中具有在相同安全度条件下所占用资源小于一般有限域离散对数问题的优势。本文采用椭圆曲线离散对数问题构建该体制。以有限域Fp (p为不等于2和3的素数) 上的椭圆曲线群来说明CPK算法的数学原理和构建方法[6]。

2.1公、私钥矩阵的产生

在给定椭圆曲线参数T= (a, b, G, n, p) 的基础上可以构建公、私钥矩阵。设公钥矩阵 (PSK) 为m×h矩阵, 矩阵中的元素记为Xi j (1≤i≤m, undefined1≤j≤h) , 它们都是由基点G生成的子群S中的元素, 即Xi j= (xi j, yi j) 。私钥矩阵 (SSK) 同样是m×h矩阵, 矩阵中的元素为ri j, 私钥矩阵记为SSK, ri j是Xi j对于基点G的倍数值, 即ri jG=Xi j= (xi j, yi j) , SSK矩阵是离散对数矩阵。

2.2密钥对产生

一个实体的公、私钥对是根据该实体标识的映射值分别在公钥矩阵和私钥矩阵中选取对应位置的元素再进行组合而生成的。

设通过标识映射得到的公、私钥矩阵中点的坐标为: (i1, j1) , (i2, j2) , …, (it, jt) , 则得到的公钥为:

私钥为:

且满足公、私钥对的条件PK=SK×G。

3基于CPK算法的安全成簇方案

经典分簇算法LEACH周期执行, 每轮循环的基本过程是:在簇的建立阶段, 每个节点选取一个介于0和1之间的随机数, 如果这个数小于某个阈值, 该节点成为簇首。然后, 簇首向所有节点广播自己成为簇首的消息。其他节点根据接收信号的强弱来决定加入哪个簇, 向目标簇首进行回复。在数据传输阶段, 簇内的所有节点按照TDMA时隙采用CDMA编码向簇首发送数据。簇首将数据融合之后把结果发给基站。在持续工作一段时间之后, 网络重新分簇。以LEACH分簇算法为背景, 将CPK算法引入分簇过程。每轮分簇过程中, 节点要对选定的簇头进行身份认证, 当节点身份经过认证后, 节点发起入簇请求;同时簇头也要首先确认申请加入节点身份合法性, 而后进行时隙的分配。节点布设之前, 通过CPK密钥管理中心安全获取分配的标识、根据标识所得出的私钥、映射算法、椭圆曲线参数T= (a, b, G, n, p) 以及公钥矩阵。安全分簇过程描述如图3和图4所示。

图中, NH为簇头生成随机数值;BH为簇头的广播消息;h为簇头使用私钥对BH+NH的签名消息;PKH为根据簇头标识计算的簇头公钥;Nundefined为PKH对NH解密消息;B1H为PKH对BH解密消息;IDCH为簇头节点标识;IDON为普通节点标识。

节点确定可以成为簇头之后, 作为候选簇头节点:

① 生成随机数NH, 用自身私钥对NH和广播消息BH加密, 得到h=SIGSKH (BH+NH) ;

② 广播广播消息BH、h和自己的ID;

③ 等待节点加入消息。收到广播消息的普通节点;

④ 选取接收信号强度最大节点的ID, 根据公钥矩阵计算该候选簇头节点的公钥PKH;

⑤ 用PKH对接收的广播消息h进行解密, 得到B1H+N1H, 比较B1H和BH。2个值相等则执行步骤⑥, 否则执行步骤⑦;

⑥ 认为该候选簇头节点为簇头节点, 向该簇头发送N1H、加入该簇的请求消息以及自己的ID;

⑦ 广播该节点属于非法节点消息, 将该节点列入黑名单, 重新返回步骤④。簇头节点收到节点入簇请求后;

⑧ 验证N1H是否与NH相同, 如果2个值相等, 则执行步骤⑨, 否则执行步骤⑩;

⑨ 将该节点标识列入成员列表, 发送TDMA列表和CDMA编码消息;

⑩ 广播该节点为非法节点消息, 将该节点列入黑名单。

4性能分析

无线传感器网络的分簇过程是典型的一对多、多对一通信模式。节点广播自身成为簇头消息时, 属于一对多通信模式。簇头对自身的广播消息签名, 选择该节点为簇头的其他节点根据该节点标识计算出其公钥, 验证该簇头的真伪性。当节点确定簇头真伪性后, 向簇头发起入簇请求, 此时属于多对一通信模式, 如果仍然按照由接收节点计算公钥而后进行认证将给簇头节点带来过多的通信、计算、存储开销。所以在簇头广播时, 广播消息附带经过加密的随机数值, 节点只有拥有映射算法、椭圆曲线参数T= (a, b, G, n, p) 以及公钥矩阵才可以得到该随机数值。簇头节点在收到入簇的请求消息后, 辨别请求消息中的随机数是否为自己产生的随机数值, 判定请求入簇节点是否是合法节点。

4.1安全性

基于CPK的密钥建立过程, 首先确保私钥矩阵的安全存储以及节点私钥的发放和存储安全。在给定初始参数和公钥的基础上, 在数学上计算出节点的私钥极其困难。通过分簇过程引入认证, 可以有效防止非法节点假冒簇头以及恶意节点申请加入簇内, 分簇过程中将非法节点屏蔽在簇外。通过对发现的非法节点及时广播, 可以使广播范围内的节点都可以共享到非法节点的信息。

4.2引入开销

节点首先引入了私钥、映射算法、椭圆曲线参数以及公钥矩阵的存储开销, 由于CPK组合公钥的优势, 对于m×32的公钥矩阵, 公钥组合量为m32。节点在分簇过程中, 引入了对于公钥的计算开销, 但这种认证方式完全脱离第三方的参与, 只是通过在分簇消息中附带信息, 只需要一次会话就完成了相互认证, 并未给传感器网络带来过多的通信开销。

4.3扩展性

对于新节点的加入, 首先通过管理中心申请到合法标识、公钥矩阵、椭圆参数、映射算法, 然后安全获得管理中心根据节点标识计算出的节点私钥, 就可以脱离中心同已经部署节点进行相互认证。由于CPK通过对矩阵元素进行选取和组合, 可以生成数量庞大的公开密钥和私有密钥组成的公私钥对, 即使大规模的认证扩展也不会带来太多问题。

5结束语

传感器网络最初是因军事应用而诞生, 在很多应用中首先都要确保网络的安全性。但由于节点能力受限、无线通信特点以及应用环境复杂, 在应用中面临着诸多的安全威胁。新一代安全主题就是构建可信世界, 高可信的传感器网络有着很好的应用前景。接下来将针对传感器网络如何做到进一步可信、可管、可控进行研究。

参考文献

[1]孙利民, 李建中.无线传感器网络[M].北京:清华大学出版社, 2005:96-98.

[2]SHRESTHA A, XING Liudong.A Performance Comparison of Different Topologies for Wireless Sensor Networks[C].Technologies for Homeland Security, IEEE Conference, 2007:280-285.

[3]HEINZELMAN WR, CHANDRAKASAN A, BALAKRISHNAN H.Energy-Efficient Communication Protocols for Wireless Microsensor Networks[C].Proceedings of the33rd Annual Hawaii International Conference On Systems Sciences, 2000:1-10.

[4]胡静, 沈连丰, 宋铁成, 等.新的无线传感器网络分簇算法[J].通信学报, 2008, 29 (7) :20-26.

[5]LI Lanying, JIANG Xiuli, ZHONG Shenghai, et al.Energy Balancing Clustering Algorithm for Wireless Sensor Network Networks Security[C].NSWCTC09, 2009:61-64.

改进节点度分簇路由协议研究篇3

关键词：移动自组网,分簇路由协议,节点度,簇首

0 引言

传统的有线网络中路由器固定,组网后网络拓扑稳定,路由信息可长时间不用更新。移动自组网是无固定基础设施、无中心的自组织网络,网内节点在移动状态下组网,组网具有灵活以及不受地理环境限制的优势,所有节点具备路由功能,节点可以随时加入或离开自组网而不会导致网络瘫痪,因此,移动自组网路由协议是保证组网稳定高效的关键技术之一。针对移动自组网不同网络规模和任务需求,已经发展大量的路由协议技术,其中在大规模节点情况下,普遍采用技术成熟的分簇路由协议实现高效组网。本文研究改进节点度的分簇路由协议,在原有最高节点算法的基础上对簇首变更提出改进方法,降低簇首变更频率,节省网络维护资源,提高网络拓扑稳定性。

1 分簇路由协议研究现状

分簇路由协议区别于平面路由协议。在平面路由协议中,所有组网节点地位平等,节点在功率覆盖范围内可以互联互通,距离较远则多跳传输。平面路由协议适合节点规模较小的自组网,路由信息更新快,路由建链维护方便,但是节点数目增多会导致路由开销大,造成网络资源浪费。分簇路由协议基于分簇结构的自组网,簇的划分主要根据网络中结构功能类似的节点进行划分,簇内包含一个簇首和若干簇成员,组网示意如图1所示。簇首一般根据最小ID、最高节点度、最低移动性、节点位置等条件进行选举,主要控制并管理簇内成员,协调簇成员报文传递,对簇内信息收集以及数据处理,将信息数据共享给其他簇首。分簇路由协议相比平面路由协议能够有效控制洪泛广播信息,簇成员功能相对简单,不需要维护复杂的路由信息,在跨簇传播时主要在簇首层级传播,网络规模不受限制,在大规模节点情况下能够实现降低节点能耗和提高网络通信质量的目的,但是簇首的维护比较复杂,在网络拓扑变化时,簇首的变更也会占据网络路由开销,而且,路由通过簇首寻路,因此所寻路径不一定是最优路径。

2 最高节点度分簇路由协议

在分簇路由协议中,一个节点与相连一跳距离的节点(邻居节点)数量称为节点度。最高节点度算法根据最大节点度对自组网进行划分。采用该算法的路由协议,将拥有最高节点度的节点选举为簇首,度数相同则随机选择节点作为簇首,簇首的邻居节点作为簇成员,簇首和簇成员一起组成簇,自组网对所有节点进行上述过程,直至所有节点身份确定。具体算法描述如下:

假设区域内存在N个节点,每个节点分配标识为1,2,3,…,N。任意节点通过广播问询的方式与其他节点交互信息,得到该问询信号的节点会向广播问询的节点发送应答信号,这样每个节点都会得到一个判决矩阵,公式如下:

式中,当第i节点与第j个节点不临相邻时,aij=0;当第i个节点与第j个节点相邻时,aij=1;同时定义i=j的情况下,aij=1。

判决矩阵A包含了本节点同其他节点的位置关系信息,反映了网络的拓扑结构。矩阵中主要由0和1两个元素构成,当aij=0时,表示节点i和j不相邻;当aij=1时,表示两节点相邻。在已经获得判决矩阵信息的情况下,可以计算每一个节点的节点度,再根据节点度对自组网进行分簇。

节点i的度数DN(i)计算公式如下:

式中i=1,2,3,…,N。

在计算最大节点度后,按照节点度数值高低的依次选举为簇首,选举簇首后,判决矩阵需对与簇首节点相连的邻居节点剔除判决矩阵,再重新选举其他簇首。计算形式如下:

定义,第k个节点的度数为DN(k),公式如下:

节点k为第1个簇首H1,将DN(k)记录并保存到选举度S(k)=DN(k)中。令k’V-Ntotal(i),i’V-Ntotal(i),继续在剩余节点中选择簇首,公式如下:

节点k’被选为第2个簇首H2,保存选举度S(k’),用同样的方法继续选择簇首,直到自组网分簇完毕。

按照最高节点度算法将自组网划分为不同簇区域,能够尽量减少自组网簇的数目。业务报文簇内转发概率增加,簇间转发效率提高,从系统整体上有效降低传输时延。但是,基于最高节点度的分簇算法,簇首变更频繁,引发大量维护开销,造成网络资源浪费。

3 改进节点度分簇路由协议

改进节点度分簇路由协议主要针对原协议簇首变更频繁的问题,在设计时引入门阈值T,既降低簇首变更频率,同时能够在拓扑结构变化较大时及时变更簇首,提高系统效率。改进节点度分簇路由协议主要包括分簇的建立和维护两部分内容。

3.1 分簇建立

改进节点度分簇路由协议在组网之初,采用最大节点度算法的思路,尽可能减少组网簇首的数量,具体算法如下。

通过广播问询以及统计应答信息,建立判决矩阵A:

其中判决矩阵A中,当i=j时,aij=1。N为节点总数量,所有节点从1到N对应不同序号进行标识;aij表示第i个节点与第j个节点的位置关系,当aij=0时,表示节点i和j不相邻;当aij=1时,表示两节点相邻。

根据判决矩阵计算节点度:

公式中ai代表第i个节点。计算所有节点度后,得到节点度矩阵DN,并根据节点度矩阵选取其中节点度最大的节点,作为簇首。

第一个簇首节点记为H1,节点度为:

对簇首选举度S(H1)进行赋值并保存选举度在本节点:

簇首决定后,该节点ai根据判决矩阵A中第i行中的值判断与簇首相连节点的位置关系。aij=1代表与簇首相连的邻居节点,这些作为簇成员不参与其他簇首选举,簇与簇成员组成簇;aij=0表示其他节点不与簇首ai一跳相连,参与其他簇首选举。簇确定后,需要根据判决矩阵从所有节点集合N中删除簇和簇成员节点,该簇节点集合定义为J,表示为:

剩余节点集合定义为N’,表示如下:

第二个簇首节点记为H2,需要在剩余节点集合中选取簇首,节点度为:

对簇首选举度S(H2)进行赋值并保存选举度在簇首节点H2中:

簇首选举之后,同样根据判决矩阵完成簇成员身份确定,完成第二个簇的建立,并从N’中删除簇首和簇成员集合,继续进行簇首选举,直至所有节点身份确定,完成组网过程。

3.2 路由维护

3.2.1 变更判决

组网完成之初,采用最大节点度算法的分簇网络保证簇首节点数量尽可能小。但是,由于移动自组网的移动性和开放性,节点位置可能不断变化,普通节点可能随时加入自组网,网络拓扑动态变化。原路由协议在网络拓扑变化后,始终根据节点度进行分簇,在节点移动速度快的情况下,可能引起簇首不断变更,虽然能够保证网络效率,却导致系统大量的路由维护。

采用改进节点度路由协议维护路由过程中,当簇首ai节点度变化时,计算当前节点度DN(ai),并与簇首保存选举度S做差运算,引入比较门阈值T,降低簇首变更骤然性,增加变更条件余量。

若簇首节点度满足如下条件:

则不需要变更簇首,即便簇内存在节点度大于簇首的簇成员,系统依然保持簇结构,保证网络稳定性,反之,则进入簇变更程序。

公式中,门阈值T的取值,根据自组网业务量多少和节点设备功率、传输能力等进行预先设置。在系统业务量繁重或者节点设备功率大、功能全面等情况下,可以将T的取值增大,减少簇首变更,维持自组网拓扑结构,反之,则减少T的取值,及时变更簇首,调整到系统最佳状态,提高系统效率。

3.2.2 状态变更

在改进节点度的路由协议中,节点状态(c_state)包括4种状态:簇首状态(CH)、成员节点状态(MEMBER)、网关状态(GW)、簇首竞争状态(CH_READY)。几种状态变更示意图如图2所示。

(1)簇首状态

簇首与邻居节点以一跳距离相连,组成簇,簇与簇之间通过簇首相连。在其他节点加入该簇或者本簇节点离开该簇,簇首节点度变更超过阈值,进行变更,重新计算簇内节点节点度,若原簇首仍适合作为簇首状态,则不作改变,若连续3个周期存在簇首竞争状态,则将簇首竞争状态节点作为簇首,原簇首降为成员节点状态,并在本簇范围内广播发送强制变更消息。

(2)成员节点状态

成员节点状态是簇内可以随时作为其他状态的节点。

在当前拓扑更新周期内,若新增处于CH状态的双向邻居、且该CH所在簇的容量未满时,加入该CH所在的簇;若本节点的邻居中CH数量>1,则成为网关节点,转入GW状态。

节点加入某簇的情况下,在当前拓扑更新周期内,若新增处于CH_READY状态的双向邻居,当本节点更适合作为CH时,进入CH_READY状态。

节点加入某簇的情况下,若在当前拓扑更新周期内,只收到处于双向MEMBER状态的节点发来的邻居通告,比较本节点及所有邻居的节点度,若本节点更适合作为CH,转入CH_READY状态。

节点尚未加入任何簇的情况下,若连续3个周期未收到处于CH_READY状态的节点发送的邻居通告,则自动转入CH_READY状态。

(3)簇首竞争状态

在当前拓扑更新周期内,若新增处于CH状态的双向邻居、且该CH所在簇的容量未满时,则加入该CH所在的簇,并转入MEMBER状态。

在当前拓扑更新周期内,若新增处于CH_READY状态的双向邻居,当对方更适合作为CH时,本节点转入MEMBER状态。

本节点若连续2个周期处于CH_READY状态,则表示竞争簇首成功,进入CH状态,并将此时的节点度记为选举度S。

(4)网关状态

在当前拓扑更新周期内,若新增处于CH状态的双向邻居、且该CH所在簇的容量未满时,加入该CH所在的簇,作为该簇的网关。

当本节点邻居中的CH数量降为1时,不再充当网关,转入MEMBER状态。

当本网关与相邻的成员节点或网关节点所属簇首不同时,相邻的成员节点或网关节点则成为本网关的协作网关节点。

3.3 路由协议过程

改进节点度分簇路由协议主要包含两部分内容:簇内路由过程和簇间路由过程。

(1)簇内路由过程

节点收到上层的单播业务请求,目的节点位于簇内时,直接查询簇内路由表,若存在到达目的节点的一跳路径,则选取簇内路由表中最小的路径作为传输路径;若不存在,选取路由表中最小的两跳路径作为传输路径(必然存在簇首作为中转节点的传输路径),然后,将传输路径写入业务报文首部。

(2)簇间路由过程

节点收到上层的单播业务报文请求,目的节点位于簇外时,通过查询网关列表、簇间路由表,若存在可用路由,则将传输路径写入业务报文首部,进行报文传递。若查询后不存在可用路径,生成路由请求RREQ消息。查询路由请求表后,将路由请求消息传递给目的节点,目的节点生成应答消息RREP,生成“本地-目的节点”的路由加入簇间路由表,完成簇间路由。

4 仿真与结果分析

设计路由协议可以更好的构造一个高效率的自组网,分簇路由协议主要应用节点较多的场合,分簇算法将自组网分成多个簇,算法的好坏直接影响移动自组网性能。本研究采用OPNET软件进行仿真验证。本论文研究的改进节点度分簇路由协议,主要在不同节点移动速度的情况下,对该协议和原有路由协议进行比较。在仿真过程中,门阈值统一设为T=2,设定其他参数一致的前提下,比较二者簇首变更频率的不同,传输时延的不同。仿真具体参数设置如仿真模拟实验参数表1所示。

5 总结

本文基于最高节点度算法路由协议,提出改进节点度路由协议,对簇首的变更条件进行改进,并给出详细算法,从理论和初步试验证明了改进节点度分簇路由协议在簇首变更频率和传输时延方面对自组网性能的提高。

参考文献

[1]臧小东.Ad Hoc网络路由协议的改进研究[学位论文].南京邮电大学,2013.

[2]刘凯歌.基于分簇结构的Ad Hoc网络路由协议的研究与仿真[学位论文].武汉理工大学,2007.

[3]LIN CR,GERLAM.Adaptive clustering formobile wire-less networks[J].IEEE Journal on Selected Areas in Communications,1997.

[4]郑少仁,王海涛.Ad Hoc网络技术[M].北京:人民邮电出版社,2005.

[5]陈敏.OPNET网络仿真.北京:清华大学出版社,2004.

[6]Jiang M,Li J,Tay Y.Cluster based routing Protoeol(CBRP)funetional specification[Z].IETF Intemet-Draft,Aug1998.

[7]倪旻明.移动Ad Hoc网络中分簇组网技术的研究[D].[博士学位论文].北京:北京交通大学,2012.

无线传感网络移动分簇路由策略篇4

无线传感网络WSN作为一种新的信息获取方式和处理模式,目前已成为国内外备受关注的研究热点。几年前当无线传感网络开始引起人们的关注时,大部分的应用和研究关注的是静态的场景。随着社会的发展在很多移动环境应用了无线传感器,如海洋的监测、移动车辆的监测和动物的监测等,因此研究移动环境下的无线传感器网络越来越重要[1]。

无线传感网络中采用移动的感知节点和网关节点相对于静态设置具有明显的优势[2],但是传感网络的移动性带来许多问题。因此在移动环境里传感器网络需要设计支持移动性的路由协议。在传感网络中分簇机制可以避免感知节点之间的信息传输,通过簇头进行数据融合,减少数据冗余,降低了发送信息量和能耗,能更好地支持移动性。LEACH[3]是WSN中最早提出的分簇路由协议,循环随机选择簇头来实现负载均衡,但不能保证簇头均匀地分布在整个网络。M-LEACH[4]是基于LEACH与LEACH-C[3]提出的,选举簇头时考虑到了节点剩余能量、簇的节点数量及节点的移动速率,但是在簇的建立阶段没有解决移动性问题。LEACH-M[5]的基本思想是确认移动节点是否能与指定簇头进行通信。在分配的TDMA调度表的时间片内,节点请求指定簇头,簇头将数据的消息回馈给移动的节点。LEACH-ME[6]对LEACH-M进行改进,更适合移动的传感网络。下面为了能量高效提出了基于分簇的移动路由策略。

1 EM-LEACH算法

WSN的分簇算法可以分为3个阶段来设计:簇头的选择、簇的形成及数据传送。根据剩余能量、节点距离(感知节点与簇头的距离、簇头与网关节点的距离)、簇头的分布和网络覆盖实现能量高效的移动分簇路由协议(Energy-efficient LEACH for Mobility,EM-LEACH),即基于LEACH提出的能量有效的分簇策略。EM- LEACH是通过簇头的选取和簇的形成进行分析和创新,让分簇路由协议在支持移动性的状态下降低能耗。能量的消耗利用Heinzelman提出的消耗模型[7]进行计算。采用模型如图1所示,其中网关节点是固定的,感知节点和簇头是移动或者静止的;每个簇头都与BS直接通信。

1.1簇头的选取

在每一个区域中都有一个区域头或者簇头,就像簇中感节点与基站(BS)或者其他的簇头之间的网关节点.分簇技术中,簇头的选取非常关键,要在信息安全传输下降低能耗;在每轮产生簇头数量应尽可能保持一致,这样才能延长簇的寿命。若在一个轮中没有簇头产生,每个传感器节点将会直接与sink通信,消耗更多的能量。在所有产生的簇当中,簇的大小应均匀,确保能量消耗均衡。

簇头选取中首先要确定簇头的数量,若簇头数量为M,M将作为系统参数在每一轮选取簇头时都应保持不变。若簇头数量过大,则数据融合能力降低,向网关节点发送信息量增大,增大了能量消耗;若簇头数量过少,每个簇头都要收集簇区域内所有感知节点的感知信息,增大了簇头的负担,易造成簇头早死现象。

在无线传感网络中能量的消耗主要是节点之间信息传输距离决定的,因此簇头的位置将影响整个簇区域的能量消耗。在簇区域中簇头有一个最佳位置,在此位置的簇头与簇中其他感知节点距离总和最短,因而信息传输能量消耗最少。在簇区域内感知节点的移动方向和移动速度都是不确定的,因此在一定的时间内,感知节点可移动到簇头最佳位置或者偏离最佳位置,甚至可能离开整个簇区域而进入另外的簇。

首先按照剩余能量筛选节点,这样可以加快选取簇头的速度,并且可以避免剩余能量低的节点成为簇头造成早死现象,因此用阈值Eselect进行筛选。

为了支持无线触感器网络的移动性,在簇头选取时要考虑的因素主要是簇头剩余能量、簇头的分布和簇头的移动信息(速度、方向和位置)。为了让簇头均匀分布并对整个传感网络实现完全的覆盖,把整个区域分成M个子区域,在每一个子区域中选取一个簇头。假设第j子区域节点数Nj,每个节点坐标为(xi,yi),速度为vi。簇头的最佳位置S0(x $_{m}^{c}$ ,y $_{m}^{c}$ )计算方式如下:

$x_{m}^{c} = \frac{1}{Ν_{j}} \sum_{i = 1}^{Ν_{j}} x_{i}, y_{m}^{c} = \frac{1}{Ν_{j}} \sum_{i = 1}^{Ν_{j}} y_{i}$ 。 (1)

移动方向用θi(0≤θi≤180)表示,其是节点i的移动方向和连接节点指向最佳位置的直线形成的夹角(速度和直线的最小夹角)。最佳选择则是节点移动方向是S0,即夹角越小越好。角度θ*i则是处理后的角度,其中θt是角度阈值。

$θ_{i}^{*} = {\begin{cases} θ_{i} i f (θ_{i} > θ_{t}) \\ θ_{t} i f (θ_{i} \leq θ_{t}) \end{cases}$

, (2)

$v_{i}^{*} = {\begin{cases} v_{i} i f (v_{i} > v_{t}) \\ v_{t} i f (v_{i} \leq v_{t}) \end{cases}$

, (3)

如果簇头移动速度过快,则容易造成簇的破坏;移动过慢,则适合整个网络的移动速度。节点v*i是处理后的速度,其中,vt是速度阈值,vi为节点i的速度。

由于距离决定信息在传输过程中的能量消耗,因此,选取的节点距离d*i越近越好。

$d_{i}^{*} = \sqrt{(x_{i} - x_{m}^{c})^{2} + (y_{i} - y_{m}^{c})^{2}}$ 。 (4)

利用3个因素形成代价函数,得到的最佳簇头则是靠近最佳位置、移动方向是最佳位置、速度相对较慢的节点,因此节点i为簇头的代价函数为:

C $_{i}^{m}$ =θ*iv*id*i, (5)

由上式看到,θ*i、v*i和d*i变小时,C $_{i}^{m}$ 值也变小,θ*iv*i则是节点i的速度因子,因此C $_{i}^{m}$ 最小的节点为簇头最理想的节点,若存在多个节点的C $_{i}^{m}$ 为最小值,则其中随机产生一个节点为簇头。

1.2簇的形成

在簇的形成过程中由于簇头和感知节点都可能处于移动状态,因此感知节点和簇头的速度很难进行计算,并且要同时考虑感知节点与簇头、簇头和基站的距离。

由于感知节点和簇头在保持一定距离下都处于移动状态,因此速度和距离之间的关系比较复杂,例如2个节点相向移动、相反移动及不定方向形式。为了降低复杂性,把速度大小和速度方向一起分析,因此利用速度和角度得到速度因子v*i。

$v_{i}^{*} = \sqrt{v_{i}^{2} + v_{0}^{2} + 2 v_{i} v_{0} \cos θ_{i 0}^{*}}$ 。 (6)

式中,θ*i0=(θi+θ0)/2,vi根据速度阈值计算,θi是感知节点移动方向和连接感知节点、簇头直线形成的夹角,θ0是簇头移动方向和连接簇头、感知节点的直线形成的夹角。可以看出移动因子不是2个速度的矢量和,而是考虑到2个速度的移动方向变化,能够简单高效地对节点移动性进行评估。

基于EECS[8]的通信代价函数,结合移动因子提出新的通信代价函数:

Cost(i,j)=wEv*ig[d(Si,CHj)]+

(1-w)f[d(CHi,BS)], (7)

$f = \frac{d (Ρ_{j}, C Η_{i})}{d_{f_\max}}$ , $g = \frac{d (C Η_{i}, B S) - d_{g_\min}}{d_{g_\max} - d_{g_\min}},$

df_max=EX(max{d(Pj,CHi)}),

dg_max=max{d(CHi,BS)},

dg_min=min{d(CHi,BS)},

其中,E=En_init/En_current,w是具体环境决定的权值,CHi是区域i的簇头,BS为基站,d(CHi,BS)是距离,g是两者之间的通信代价。Si为感知节点,d(Si,CHj)是两者之间的距离,f是通信代价。Cost(i,j)表示为成员节点i到簇头j的通信代价,在簇的形成过程中每个成员节点选取通信代价最小的簇头加入簇区域。

1.3移动性支持

在大部分的分簇算法中都不能直接地支持移动性,在每个时间环内,如果一个节点正在移动脱离当前簇,这个节点为了保持连接必耗费更多的能量,当这个节点进入另一个簇中仍然保持原来的簇头,则不能有效地利用能量。为了支持移动性EM-LEACH在M-LEACH的基础上提出了新的通信策略。分簇的流程类似于M-LEACH,其中对算法进行了改进,能更好地支持移动性。

在EM-LEACH的初始阶段,每一个几点发送到BS的信息包括本地位置、速度、方向和能量级,BS基于接受到的信息利用式(5)计算出簇头并向每一个节点发送时间表。每一个节点根据接收到的信息利用式(7)进行计算,选出通信代价最小的值为自己的簇头,同时利用这些信息设置自己的时间表。为了降低簇内信息传输的干扰,确保数据的安全性,每一个节点在自己的时间片内利用DSSS传输编码进行传输。

传输阶段每个节点在允许的时间片内传输数据,由于时间片是不变的,每个节点基于簇中节点的数量安排下一次的分配时间。在簇头接收传感器节点数据之后进行数据融合,最终把数据发送到基站。

2 实验结果

通过仿真平台对算法进行仿真模拟,得出算法的性能,并与M-LEACH算法进行性能比较。把100个节点随机分布在100*100的区域中,同时BS也随机选择自己的位置。每一个感知节点的速度都是在一定的阈值范围内随机产。每个节点的初始能量相等,在数据传输过程中,当节点的能量低于能量阈值时,该节点被设定为死亡。

图2展现的是M-LEACH协议与EM-LEACH协议存活节点数量随时间变化。随着时间的变化,M-LEACH协议中早死节点提前出现,主要因为在此协议算法中并没有很好地考虑速度和距离因素,因此在簇头选取和簇形成之后,很容易出现早死现象。随着时间的发展,2种协议剩余节点数量差距逐渐变大。

图3展现的是2种协议存活节点数量随传输数据的变化,可以看出,随着数据的传输,2种协议的节点逐渐出现死亡,但是M-LEACH比EM-LEACH提前出现。随着数据传输量的增大,2种协议的死亡节点的数量差距越明显,最终EM-LEACH提前出现有的节点死亡。充分体现出在EM-LEACH算法中考虑到移动速度和方向、节点间的距离因素,能较好地支持移动性,实现降低能耗。

实验结果表明EM-LEACH能够有效地降低能耗,实现负载均衡,延长生存时间,提高数据传输。

3结束语

无线传感网络中节点的移动对路由协议具有很大的影响。为了让路由协议很好地支持无线传感网路的移动性,首先在簇头选取、簇建立过程中考虑移动因子,把移动速度与移动方向合理结合,从而更好反应节点移动造成位置变化对整个网络能量消耗造成的影响。其次研究了感知节点与簇头、簇头与网关节点之间的距离。最后结合剩余能量建立了关于簇头选取、簇形成的代价函数,提出基于EM-LEACH算法。通过仿真实验证明,EM-LEACH在支持网络移动的情况下,有效降低能耗和延长生存时间。但是EM-LEACH仍然有很大的提升空间,仍需对分簇中算法进行研究,提出高效并支持移动性的分簇算法。

参考文献

[1]AKYILDIZk L F,WEILIAN S,SANKARASUBRAMANI-AMY Y,et al.Asurvey on Sensor net works[J].IEEECommunica-tions Magazine,2002,40(8):102-114.

[2] AL-KARAKI J N,KAMAL A E.Routing Techniques in Wireless Sensor Networks:A Survey[J].IEEE Wireless Communications,2004,11(6):6-28.

[3]HEINZELMAN W R,CHANDRAKASAN A,BALAKRI SH.Energy-efficient Communication Protocol for WirelessMcrosensor Networks[C]∥Proceedings of the 33rd An-nual Hawaii International Conference on System Sciences(HICSS),Maui,HI,2000:1-10.

[4]NGUYEN L T,DEFAGO X,BEURAN R,et al.An EnergyEfficient Routing Scheme for Mobile Wireless Sensor Net-works[C]∥Proceedings of the 2008 IEEE InternationalSymposium on Wireless Communication Systems(ISWCS),Reykjavik,2008:568-572.

[5]KIM Do-Seong,CHUNG Yeong-jee.Self-OrganizationRouting Protocol Supporting Mobile Nodes for WirelessSensor Network[C]∥First International Multi-Symposi-ums on Computer and Computational Sciences(IM-SCCS),2006:622-626.

[6] KUMAR G S,VINU P M V,ATHITHAN G,et al.Routing Protocol Enhancement for Handling Node Mobility in Wireless Sensor Networks[C]∥2008 IEEE Region 10 Conference,Hyderabad,2008:1-6.

[7]HEINZELMAN W R,CHANDRAKASAN A,BALAKRISH-NAN H.An Application-specific Protocol Architecture forWireless Microsensor Networks[C]∥IEEE Transactions onWireless Communications,2002,1(4):660-670.

可重构分簇式分组密码处理架构篇5

随着可重构技术研究的深入，面向分组密码处理的可重构架构日益增多。基于VLIW结构的处理架构有:可重构分簇式分组密码处理器RCBCP[1]、多Cluster结构的安全处理器SophSEC[2]、可重构分组密码芯片结构COBRA[3]等，基于VLIW结构的分组密码处理系统通过开发分组密码算法的指令级并行度，将可并行执行的指令组合成一条指令，在一个指令周期内完成，提高了分组密码算法的实现性能。但是上述结构每个时钟周期处理单元最多只能有一种运算逻辑工作，存在资源利用率低的问题。基于阵列结构的处理架构有:可重构密码处理结构RC-PA[4]、可重构层次互连密码处理结构RHCA[5]等，基于阵列结构的分组密码处理系统能够以较大的并行度和流水深度进行密码处理，但是阵列结构存在处理粒度小、互联资源多、布局布线复杂等问题，并且文献[4,5]提出的处理架构采用同构化设计，功能单元的利用率低下。

本文针对分组密码算法的处理特征，提取分组密码算法的共性逻辑，立足提高可重构功能单元的利用率，开发密码算法实现的并行性，提出了基于Crossbar互连的可重构分簇式密码处理架构RCCPA，完成了RCCPA的原型设计，并评估了分组密码算法在该结构上的映射及实现性能。

1 分组密码算法处理特征分析

分组密码大都基于相似的设计理论，如基于Feistel网结构或扩展Feistel网结构设计的DES、FEAL、Lucifer、LOKI、GOST、DFC、MARS及RC6等算法;基于SP网络结构设计的CRYP-TON、SAFER、AES及SERPENT等;基于不同代数群的混合运算来设计的IDEA、MMB等。基于相同或相似设计理论的分组密码有相似的处理结构、操作类型较大交集[5]。通过分析常见的分组密码算法，可以归纳出分组密码处理结构特点:

(1)计算粒度，分组密码算法的分组长度一般为64/128位，分组密码算法运算过程中的处理粒度一般为8～32位，并以32位的运算位宽较为常见，因此本文设计的可重构密码处理单元RCU的处理位宽为32 bit。

(2)并行处理，如图1所示，横向上分组密码算法大都是将数据分组拆分为字长数据，各个字并行处理。纵向上多个分组数据，在无反馈模式下，通过设置多个处理单元可以实现多个分组的流水操作;在反馈模式下，采用交替技术，也可以实现多个分组数据在多个处理单元上的流水操作。

(3)分支控制，分组密码算法的轮运算基本相同，算法各操作之间存在前后数据相关，但是分支较少、反馈较少，因此分组密码算法控制相对简单，适合流水执行。

(4)操作类型，各分组密码算法的操作类型交集较大，基本上由9类基本操作完成:基本逻辑运算、模加/减运算、固定移位操作、变量移位操作、S盒替代操作、置换操作、模乘运算、模乘逆运算、有限域GF(2n)上乘法运算等。

通过对DES、IDEA、AES候选算法等41种公开的分组密码算法加解密结构进行分析研究，可以得出分组密码算法9类基本操作在各算法中的应用情况如图2所示。

从图2可以看出，除模乘逆之外，其它基本操作在41中分组密码算法中所占比例都超过15%以上。根据统计分析结果，运用可重构设计思想，共设计了6种32 bit位宽的可重构密码处理单元RCU:S盒替代单元、32 bit移位单元、有限域GF(2n)上的矩阵乘法单元、算术乘法单元、算术模加/减单元、逻辑运算单元等，为了对SERPENT、CRYPTON等算法中出现的128 bit置换及IDEA中涉及的128 bit长移位提供支持，专门设计了2个超长位宽(128 bit)的处理单元:128 bit的置换单元和128 bit的移位单元。另外由同余定理和费马定理可知，模乘逆运算可以通过反复调用模乘操作得以实现，并且模乘逆运算应用较少，因此不再设计模乘逆运算单元。

2 可重构分簇式分组密码处理架构

分组密码算法适于分组(或分块数据)内并行、分组间并行或流水处理，并且具有分组(或分块数据)间数据交互少的特点，本文在分析分组密码算法特点、提取分组密码算法共性逻辑的基础上，提出了基于Crossbar互连的可重构分簇式密码处理架构RCCPA，并重点研究互连网络、寄存器堆、配置方式等问题。

2.1 总体架构设计

结合分组密码算法处理特点，本文提出的RCCPA架构如图3所示。架构采用分簇式设计，包含4个处理簇、配置单元、通用寄存器堆、子密钥寄存器堆、控制逻辑和I/O接口，每个处理簇包含有针对分组密码算法设计的8种可重构密码处理单元RCU，对于超长处理位宽(128 bit)的可重构处理单元:比特置换、长移位单元将其输入、输出信号分为4组32比特接入到4个处理簇中。处理簇内的RCU通过基于Crossbar互连的Level-1总线进行数据交互，任一RCU的输出可以接到任一RCU的输入上，不同簇间的数据交互通过Level-2总线完成。RCCPA可以根据密码处理的需要，灵活配置簇内、簇间的互连结构，在纵向和横向上组织各个RCU，组成不同的处理路径，充分适应密码处理的并行及流水特性，完成密码运算。

配置单元包括静态配置单元和动态配置单元两部分，其中静态配置主要完成各功能单元的功能配置，动态配置单元根据密码算法的处理流程动态重构互连网络，完成密码处理。通用寄存器用于存储密码处理过程中产生的输入/输出/临时数据，子密钥寄存器用于存储密码运算需要的子密钥数据、常数及IV向量。

在可重构分簇式密码处理架构RCCPA中，配置数据首先在控制单元的控制下分别存储于动态配置单元及静态配置单元中，控制单元根据静态配置单元中存储的配置信息完成可重构处理单元RCU的配置，完成静态配置后，RCCPA接收外部输入的数据进行子密钥生成或密码处理运算，此时控制单元根据动态配置单元的内容动态配置互连网络，控制处理数据的处理序列及输入、输出，并实时地将状态信息写入到标志寄存器中。此外控制单元还可对无需参与运算的RCU进行旁路处理，以减小系统时延提高性能。

2.2 互连网络设计

可重构密码处理器的内部连接网络是各个基本密码运算模块之间进行数据传输的通路。其功能和特性对可重构密码处理器的灵活性、适应性、扩展性、性能和规模具有至关重要的影响[6]。常用的内部连接网络主要包括:全互联网络、单总线网络、多总线网络等，相对于其它两种互联方式，全互联网络具有最大的网络宽度，并且采用Crossbar实现的全互联网络可以动态重构，灵活性高。较大的网络宽度和较强的灵活性，可以提升分组密码处理架构的处理性能和适应性。因此本文选用基于Crossbar的互连网络实现RCCPA中各功能的连接。但是全互联网络规模较大，当处理单元增多时，其网络规模增长较快。分组密码算法的功能单元数量不多，且分组(或分块数据)间数据信息交互较少，因此可以通过分簇、分级的方式设计互连网络，以减小互连网络的规模。本文基于以上分析设计了Level-1、Level-2两级互连结构，每个处理簇包含1个Level-1互连结构，用于簇内各个可重构处理单元RCU之间的互连。Level-2互连结构用于簇间的数据交互。

如图4所示簇内采用Level-1的全Crossbar互连实现簇内8个功能单元间的全连接，Level-1互连结构还将通用寄存器堆数据、输入寄存器数据接入到互连网络上，以实现上述数据到各RCU的连接。同时为了保证处理结果输出灵活性，Level-1互连结构专门设置了数据输出端口，使处理结果可以灵活地写入到通用寄存器堆、子密钥寄存器堆以及输出寄存器堆。Level互连结构的位宽设置与各RCU的处理位宽一致均为32 bit。

为实现4个处理簇之间的数据交互，在RCCPA中设置了Level-2互连结构，在每个处理簇中设置了6个输入端口、6个输出端口，每个端口的位宽为32 bit，分别用于接收其它3个BANK的运算结果或将当前BANK的运算结果发送到其他BANK，其互连结构如图5所示。

通过动态重构互连网络可以将各BANK中的RCU配置成处理分组密码运算的数据路径，图6给出了一种配置方式下形成的数据路径:数据输入->RCU6->RCU1->RCU0->RCU2->结果输出。数据路径中多个RCU协同工作，形成多级流水线，可以同时处理多个密码分组，提高了RCU资源利用率。同时通过Level-2总线互连，还可以将数据路径动态地重构成4个32 bit簇、2个64 bit簇和1个128 bit簇，满足了分组密码处理灵活性的要求。

2.3 分簇式寄存器堆设计

分组密码处理过程中存储的数据大致可分为三类:S盒查找表数据、子密钥数据、输入/输出/临时数据，S盒查找表数据存储在功能单元内部设置的存储器中，与寄存器结构无关。另外两类数据有着不同的用途、使用特点[7]:子密钥一般数据量较多，占用较大的存储空间，但在加解密处理过程中保持不变，只有在主密钥变更时，才会由密钥扩展程序重新计算生成;输入、输出和计算过程中临时数据的存储容量需求不大，但其中某些数据需要频繁的改变。为此设计了两个寄存器堆:子密钥寄存器堆和通用寄存器堆，实现对两类不同数据的存储，寄存器堆采用分簇式设计，其整体结构如图7所示。

通用寄存器堆采用4个独立的寄存器堆实现:GPR_A、GPR_B、GPR_C、GPR_D，每个通用寄存器堆包括1个任意写端口和1个任意读端口，通用寄存器堆GPR_A只能由BANKA直接读写，相应的GPR_B、GPR_C、GPR_D只能由对应的BANKB、BANKC、BANKD直接读写。由于互连结构提供了簇间交互机制，当BANK需要使用其他BANK对应的寄存器数据时，可以通过Level-2互连总线进行读取。根据相同原理设计了子密钥寄存器堆，其读写机制与通用寄存器堆类似，只是面向的功能应用不同，存储空间不同。

RCCPA设计的4个密钥寄存器堆的容量为:128×32，通用寄存器堆的容量为:64×32 bit。通用寄存器堆与密钥寄存器堆的整体结构如下图8所示。通用寄存器堆的输出直接接入到各BANK的互连网络上，每个BANK通过互连网络可直接对本BANK所对应的通用寄存器堆进行读写操作，系统可以通过Level-2总线间接读写其它BANK所对应的通用寄存器。子密钥寄存器堆的设计思想与通用寄存器堆类似，只是子密钥寄存器堆的输出直接接入BANK的功能单元上。

2.4 配置方式研究与设计

采用静态配置与动态配置相结合的方式完成RCCPA中可重构密码处理单元RCU与互连网络的配置，RCU的配置采用静态配置，互连网络的配置采用动态配置。RCCPA中RCU所需要的配置信息存储于RCU的专用配置寄存器中，当需要执行某个配置时，控制单元通过静态配置的方式将配置信息写入到RCU相应的专用配置寄存器中。互连网络的配置信息存储于配置信息存储器中，在算法执行的每一个时钟周期，控制单元将配置信息动态译码输入到相应的互连网络的控制端，组织成不同的数据通路。动态配置互连网络的方式有效减少了配置指令的长度，降低了译码的复杂性，同时保持了较高的编程深度和重构灵活性。

RCCPA在控制单元的控制下完成分组密码处理，控制单元通过状态机实现。RCCPA架构的控制单元各状态之间的转换如图9所示，共包括6种状态:Idle、Config_in、S_config、Wait、Key_gen、Cip_pro。控制单元各状态的具体含义及转换条件如表1所示。

3 原型验证与性能分析

以分组长度和密钥长度都是128位、圈数为10的AES算法为例，说明分组密码算法在RCCPA上的映射。AES由三部分组成:初始圈密钥加法，圈变换和末尾圈变换。初始圈密钥加法是将输入的明密文与初始子密钥进行异或。算法中除了末尾圈变换省略列混合变换外，每圈变换包含字节代替变换、行移位变换、列混合变换和圈密钥加法，因此将4种可重构处理单元RCU:S盒替代单元、置换单元、有限域GF(2n)上的矩阵乘法单元、逻辑运算单元组成数据路径。由于RCU与互连网络输出都含有一级寄存器，因此共可流水处理8个数据分组，AES算法在RCCPA上的映射如图10所示。

为验证设计的正确性，使用NC-Verilog对可重构分簇式密码处理架构RCCPA进行了仿真测试。使用Synopsys公司的Design Complier for Solaris工具，采用0.13μm CMOS工艺标准单元库及相应负载模型和RAM硬核对RCCPA进行逻辑综合，综合结果如表2所示。

经算法适配验证，RCCPA可灵活适配Feistel网结构或扩展Feistel网结构、SP网络结构、代数群混合结构的常用算法。为了对比RCCPA的实现性能，选择不同结构、不同位宽的AES、DES、IDEA算法的实现性能，与其它可重构分组密码处理器进行了对比，性能对比结果如表3所示。

单位:Mbps

RCBCP[[11]]是一款采用VLIW结构设计的具有4路并行的可重构分簇式密码处理器，Crypto-nite[8]采用两路并行的RISC结构，每路RISC处理位宽为64 bit,RCPA[4]是基于阵列结构的可重构密码处理架构。通过适配多种分组密码算法及表4对比结果可以得出，RCCPA结构可以灵活适配分组密码算法，并且对不同设计结构、不同处理位宽、不同操作位宽的分组密码算法均有较高的处理性能，与其它专用可重构密码处理结构相比处理性能提高了2.5～11.3倍。

4 结语

本文在分析分组密码算法处理特征的基础上，立足于提高可重构处理单元RCU的利用率，设计了基于Crossbar互连的可重构分簇式密码处理架构RCCPA，通过动态重构互连网络的方式，可将数据路径动态地重构成4个32 bit簇、2个64 bit簇和1个128 bit簇，并可将可重构处理单元RCU组织成多级流水的处理路径，满足了分组密码处理灵活性的要求。基于分簇式的处理架构，降低了互连网络、寄存器堆设计的复杂性。静态重构与动态重构相结合的配置方式，提高了分组密码适配的灵活性，降低了配置译码的复杂性。与其他可重构分组密码处理架构相比，RCCPA具有更大的灵活性、更高的资源利用率和更强的处理性能。

摘要：针对现有可重构分组密码系统资源利用率低的问题,在分析分组密码算法处理特征的基础上,提出基于Crossbar互连的可重构分簇式分组密码处理架构RCCPA(Reconfigurable Clustered Cipher Processing Architecture),研究了RCCPA的互连网络、分簇式寄存器堆及配置方式。RCCPA通过重构互连网络可将各处理簇动态地重构成4个32 bit簇、2个64 bit簇和1个128 bit簇,并可将可重构处理单元RCU(Reconfigurable Cipher Processing Unit)组织成多级流水的处理路径,满足了分组密码处理灵活性的要求,提高了RCU的利用率。采用RCCPA实现AES/DES/IDEA的处理性能分别达到了2 867.2 Mbps、1 442.6 Mbps、1 462.4 Mbps。

关键词：密码处理,可重构,分组密码,Crossbar,分簇式

参考文献

[1]孟涛,戴紫彬.分组密码处理器的可重构分簇式架构[J].电子与信息学报,2009,32(2):453 456.

[2]黄伟.面向云计算的性能与功耗可配置安全终端技术研究[D].上海:复旦大学,2011.

[3]Adam J Elbirt.Reconfigurable Computing For Symmetric-Key Algorithms[D].Massachusetts:Electrical and Computer Engineering Department University of Massachusetts Lowell,2002.

[4]杨晓辉,戴紫彬,张永福.可重构分组密码处理结构模型研究与设计[J].计算机研究与发展,2009,46(6):962 967.

[5]姜晶菲.可重构密码处理结构的研究与设计[D].长沙:国防科技大学,2004.

[6]曲英杰.可重构密码处理器内部连接网络的设计与分析[J].计算机工程与应用,2007,43(23):167 170.

[7]戴紫彬.面向分组密码处理的协处理器体系结构研究与设计实现[D].解放军信息工程大学,2007.

一种节能的分簇路由算法研究篇6

无线传感器网络是一种面向具体应用、以数据为中心、传感器节点资源有限、网络拓扑经常发生变化的大规模自组织网络。随着传感技术、微电子技术、嵌入式计算技术和通信技术的快速发展和高度集成, 它的应用前景也越来越广阔, 如:军事领域、防恐与反恐、环境监测与预报、空间探索、城市交通管理、智能家居等, 已逐渐深入到人类生活的各个领域, 被认为是对21世纪产生巨大影响力的技术之一[1]。传感器节点通常由能量有限的电池供电, 在目前的技术水平下, 通过提高电池的容量或人工更换电池的方式补充能源是不切实际的。因此, 对无线传感器网络路由算法的设计应当把节约能源放在首要位置, 综合考虑能量消耗的均衡性问题, 以达到最大限度的延长网络生命周期的目标。

对无线传感器网络的节能研究主要集中在硬件的设计、MAC协议及路由协议设计方面。目前提出的无线传感器网络路由协议主要有两类:平面路由协议和层次路由协议。传统的平面路由协议需要在每个节点中维护一张路由表, 通过节点之来的信息交换来实现路由的选择, 这样需要消耗大量的路由空间并增加了网络的通信负担。层次路由协议的基本思想是将网络分成多个簇, 由簇头节点对各自簇内的数据进行简单的处理并传输到sink节点, 这样簇头节点便成为分层路由协议中的瓶颈节点。采用基于分簇的层次路由算法相对平面路由算法具有更好的适应性和节能性[2]。文献[3]提出了DDCH算法, 利用由具有局部最大剩余能量的节点所构成的“能量核”来进行路由, 选择一条自源节点到目的节点的局部最短路径来进行数据的传输该算法具有较低的时间复杂度和较好的可扩展性文献[4]提出了DEEC算法, 从节点剩余能量及其与基站之间的距离为出发点, 提出按功能设置四种不同类型的节点, 除簇头节点外, 其余三种分别完成数据收集、数据处理、数据转发的功能。该算法能在较小的网络延迟下有效地延长网络的生命周期并均衡网络的能量消耗, 但增加了信息交换与数据传送的次数, 增加了额外的消耗能量。文献[5]提出了一种基于簇的多跳高效节能路由算法, 该算法中节点自主地根据其剩余能量来竞争簇头, 分簇完毕簇成员如果没有感知任务就处于休眠状态;簇头之间通过建立路由树以多跳方式将收集到的数据经根节点发送到sink节点。文献[6]对最小ID分簇算法进行了改进, 通过调整簇头节点的功率大小来增加或减少簇内节点的数量, 以达到最佳的网络性能。文献[7]提出了一种基于LEACH的固定聚类路由算法。

本文在基于LEACH的固定聚类路由算法的基础上结合已有的研究, 提出了一种新的节能的分簇路由算法, 其基本思想是在簇头节点的选举过程中引入了“捎带”技术以减少网络的通信流量, 降低延时;簇头节点之间通过构造邻节点的路由表并选择具有较大剩余能量值、通信距离较短的路径将数据发送到基站, 以实现使能量的消耗均衡的目的, 从而延长网络的生命周期。理论分析和仿真结果表明, 该算法是可行的并表现出更好的性能。

1 一种节能的分簇路由算法

1.1 相关工作及问题分析

基于LEACH的固定聚类路由算法的是以聚类的方式来组织节点的, 其基本思想为: (1) 根据被监测区域的面积以及传感器节点的总数目, 通过数学计算得到固定聚类路由算法的最优聚类首领数; (2) 根据节点的地理位置信息及最优聚类首领数, 由BS统一将被监测区域划分为面积大体一致的固定聚类区域; (3) 聚类区域一旦划定便固定下来, 从第二轮开始由具有最大剩余能量值的节点担任聚类首领; (4) 聚类内节点采用单跳的方式与聚类首领通信; (5) 聚类首领之间通过建立路由树, 形成层次化聚类结构与BS进行通信。

该路由算法可以延长网络的生命周期, 并在一定程度上均衡了能量的消耗。但是在步骤 (3) 聚类首领的选举过程中, 聚类内的所有节点将自己的当前能量值与阈值相比较, 若大于阈值, 则向前一轮的聚类首领报告自身的能量值, 再由前一轮的聚类首领选定具有最大剩余能量值的节点担任聚类首领, 并将信息广播给聚类内的所有节点。该过程进行了一轮计算机和两轮额外的信息传输, 虽然减少了需要传输信息的节点的数量, 但还是增加了通信的流量和能量的消耗。步骤 (5) 聚类首领通过比较自身和其它聚类首领的剩余能量值, 选择具有最大剩余能量值的聚类首领作为其父节点的方式建立路由树。该过程忽略了节点之间的距离信息。由于通信损耗能量同传送的数据量和到达目标的距离平方成正比, 在通信方式上, 一般认为短距离的无线低功率通信技术最适合传感器网络使用[8]。

1.2 算法模型和假设

本文中采用二层架构模型。上层为簇头节点层, 主要负责通过簇头之间的路由表选择最佳的转发路径将簇内收集的数据发送给基站以及下一轮簇头节点的选举;下层是簇内节点层, 主要负责完成数据的收集任务。本文在该模型中做如下假设:

(1) 网络中所有的节点功能都是一致的 (即簇内所有的节点是平等的) ;

(2) 每个节点均有一个固定的ID号, 并且具有获取本身当前剩余能量值的能力;

(3) 所有节点具有感知自身地理位置及路由的功能;

(4) 初始状态各节点的能量是相同的;

(5) 被监测区域面积及传感器节点的数目是已知的。

1.3 算法详细描述

本文所提出的节能的分簇路由算法其基本思想为:将节点分成簇内节点与簇头节点两级拓扑结构, 簇内节点负责某个具体区域内的数据采集任务, 簇头节点负责将本簇内的数据进行必要的处理并传送给基站。固定的分簇及第一轮簇头的选举在初始阶段由基站完成, 其余簇头节点的选举依据最大剩余能量值的原则通过在簇内节点的最后一个数据包中“捎带”自身剩余能量信息竞争完成, 簇头节点之间形成网状拓扑结构, 并维持一张由邻居节点梯度、距离及剩余能量值组成的权值路由表, 通过选择权值最小的路径进行数据的传输。

算法描述为如下步骤:

Step1:在监测面积 (a×a) 和传感器节点总数

(N) 已经确定的情况下, 由公式推导出最优的分簇数, 其中LBS表示节点与基站之间的距离, λ为无线信号传播参数;

Step2:基站根据已经推导出的最优分簇数把被监测区域划分成k个固定的分簇, 并随机的为每个簇指定一个簇头节点;

Step3:成为簇头的节点发送一个消息给基站, 基站根据接收到信号的时间先后及强度给每个节点返回一个梯度值, 建立一个梯度场, 如下图1所示;

Step4:每个簇头节点在一跳的范围内 (邻节点) 建立一张路由表, 保存其邻节点的梯度值、当前剩余能量值、两节点之间的距离等信息, 其格式如表1。

簇头节点以一定的功率发送消息给它周围一跳范围内的邻居节点, 邻居节点收到消息后返回一个包含自身ID号、梯度值及当前剩余能量值的消息给该簇头节点, 簇头节点根据收到消息的时间及强度判断与邻居节点的距离, 并按上表设计的格式将信息存储在路由表中;

Step5:簇内节点将收集到的数据在自己的时间间隙内发送给簇头节点, 在簇头节点进行必要的数据融合等处理后发送给基站。由于网络内节点密度大导致同一分簇区域内数据的相关性与冗余性比较大, 数据融合技术是指在数据收集的过程中, 利用节点本地计算机和存储能力对数据进行操作, 去掉冗余信息, 达到减少通信量, 节约能量的目的;

Step6:簇头节点向基站发送信息时首先在路由表中找出所有梯度值比自己小的邻节点, 然后将其当前剩余能量值与一个参考量ξ进行判断, 若该值小于ξ则不再考虑将数据转发至此邻节点, 若该值大于ξ再根据两节点间的距离进行选择。节点之间的距离可以转化为它们之间响应的时间长短及信号的强弱, 距离越近, 响应时间越短, 信号越强。簇头节点选择距离较近的邻节点进行数据的发送。

Step7:数据发送完成后进行下一轮的簇头节点的选举。上一轮中簇内节点在发送最后一个数据包的时候将自身的当前剩余能量值插入到数据包的尾部进行“捎带”传送, 簇头节点通过判断提取出它们的当前剩余能量值并进行比较, 选择具有最大当前剩余能量值的簇内节点成为下一轮的簇头节点, 并将自己的梯度值嵌入到通知包中发送给下一轮的头节点;如果簇内节点的当前剩余能量均小于簇头节点, 则簇头节点继续担当下一轮的簇头节点;最后一个数据色的结构如表2;

Step8:返回step4重复执行, 直到网络内大部分的节点因能量耗尽而失效, 那么网络也就死亡。

2 仿真实验及性能分析

为了更好、更准确的评价本文所提出的节能的分簇路由算法, 本文设计了以下场景, 并从节点的死亡率与算法轮数的关系以及节点数据发送量与能量消耗之间的关系两方对其性能进行了分析。

无线传感器网络由200个传感器节点组成, 节点随机分布在被监测区域面积大小为100m×100m的区域内, 基站位于坐标为 (50, 100) 的位置。节点初始能量1.5J, 数据包长度500Bytes, 发送和接收数据的能量消耗为50nJ/bit, 放大电路功耗为100pJ/bit·m-2。

从图4 (a) 实验结果可以看出, 由于本文中所提出的分簇路由算法在簇头节点之间通过构造路由表并选择最佳路径进行数据的发送, 第一个节点的死亡时间比基于LEACH的固定聚类路由算法有明显的延迟, 节点全部死亡的时间也有明显的延迟。这说明本文中所提出的算法能更有效的延长网络的生命周期, 使能量的消耗更加均匀的分配到所有节点上。

从图4 (b) 的实验结果可以看出, 由于本文中所提出的分簇路由算法使用了最后一个数据包“捎带”节点当前剩余能量值的技术, 减小了网络中的通信流量, 所以算法的能量有效率相对于基于LEACH的固定聚类路由算法来说有明显提高。这表明本文中所提出的算法能够更加有效的利用能量, 更好的实现了能量的节约。

3 结论

本文所提出的分簇路由算法在簇头节点的选举方面主要考虑了通过减少网络的通信流量来达到减少开销, 节约能量的目的;簇内节点将数据发送到簇头节点后进行必要的数据融合, 去掉冗余的信息;簇头节点到基站之间的数据通过构造路由表并选择一条最佳路径进行发送。仿真实验结果表明, 本算法能有效的提高能量的使用效率, 达到节约能量, 均衡能量消耗, 延长网络生命周期的目的, 具有较好的性能。

参考文献

[1]崔莉, 鞠海玲, 苗勇, 等.无线传感器网络研究进展.计算机研究与发展, 2005;42 (1) :163—174

[2]梁英, 曾鹏, 于海斌.无线传感器网络中一种能量自适应的簇首选择机制.信息与控制, 2006;2 (35) :141—146

[3]林亚平, 王雷, 陈宇, 等.传感器网络中一种分布式数据汇聚层次路由算法.电子学报, 2004;11 (32) :1801—1805

[4]孙国栋, 廖明宏.一个用于传感器网络的分布式节能组簇方法.哈尔滨工业大学学报, 2006;9 (38) :1431—1435

[5]Lindsey S, Raghavendra C S.PEGASIS:powerful-efficient gathering in sensor information systems.GregRichardson.2002IEEEAerospace Conference Proceedings.Big Sky, MT, USA:IEEE Computer Society, 2002:9—16

[6]赵静, 陈向东.通过功率控制建立密度自适应的分簇无线传感器网络.传感技术学报, 2006;6 (19) :2751—2759

[7]肖伟茂, 王力.一种基于LEACH的无线传感器网络路由算法[硕士学位论文].陕西西安:西安电子科技大学, 2006

[8]任丰原, 黄海宁, 林闯.无线传感器网络.软件学报, 2003;14 (7) :1282—1291

无线传感器网络分簇路由协议综述篇7

1 无线传感器网络分簇路由协议设计常见问题

(1) 网络节点的动态性。无线传感器网络分簇路由协议大体包括三类节点, 基站, 簇首节点以及簇内成员节点, 通常情况下设计的路由协议都是假设节点是静态的, 如温室环境监测等, 而无线传感器网络在一些运用场合节点存在移动性, 如目标追踪等, 静态的拓扑结构相对较简单, 而动态的拓扑结构相对较复杂, 因此必须根据实际需要设计相应的路由协议。

(2) 网络节点的部署问题。无线传感器网络不同于其他的无线通信协议, 大部分情况下, 节点的位置事先是不知道的, 整个网络节点分布不均匀, 因此有效合理的选择簇首节点, 簇首节点的个数以及位置对均衡整个网络的功耗起到决定性的作用。

(3) 网络节点的构造问题。早期的无线传感器网络路由协议假设节点是同构的, 即每个节点拥有相同的能量, 相同的存储、处理能力, 相同的通信能力等。然而即使刚开始节点同构, 簇首节点以及远距离节点能量消耗相对较快, 一段时间后也会出现异构现象, 而且在网络布置一些高能量节点, 以及存储能力较强的节点可以有效的延长网络的生存期。在一些场合, 各个节点所需要采集的信息也可能不一样, 如光、湿度、温度以及有害气体检测等, 根据实际需要每个节点采集数据的速率、周期可能存在不一致等, 因此设计异构的路由协议显得非常重要。

(4) 网络节点的数据处理与融合问题。无线传感器网络节点数据的采集可以是周期性的采集, 也可以是事件驱动性, 有事件驱动的情况下采集数据, 否则处于休眠状态。无线传感器网络中布置着大量的节点, 如果每个节点对采集到的数据不进行处理而直接传输给上一级节点, 大量的数据在无线信道中传输就会出现数据碰撞、冲突等, 因此节点有效的处理数据, 可以减少大量的冗余数据, 相似性数据, 提高带宽的利用率以及减少能量的消耗。

(5) 网络节点的容错能力。无线传感器网络节点可能布置在恶劣的环境中, 以及可能存在一些自然的破坏以及人为的攻击等, 也可能存在部分节点硬件的故障以及能量的耗尽等, 因此在出现这些情况下, 就要求路由协议具有一定的重构性以及节点具有一定的数据容错能力。

2 无线传感器网络典型的分簇路由协议

无线传感器网络分簇路由协议的形成大体分成两个阶段, 第一阶段为簇首节点的确定, 簇型结构的形成, 第二阶段为稳定阶段, 即数据的传输与融合阶段。

2.1 簇首节点的选择与簇型结构的构建

(1) LEACH分簇路由算法。为了提高整个网络的的生存时间, 将功耗均衡的分配到网络中的每个节点, 麻省理工学院的Wendi Rabiner Heinzelman等人提出了一种低功耗的自适应路由协议, LEACH协议 (Low-Energy Adaptive Clustering Hierarchy) [2]。在LEACH协议中, 每个传感节点都有机会充当簇头节点, 簇头节点的选择主要依据网络中所需要的簇头节点个数与到目前为止每个节点已经充当簇头节点的次数来判定的。网络中每个节点在0到1之间随机选择一个数, 如果选择的数小于规定阀值T (n) , 则该节点就充当为簇首节点。LEACH算法通过设置T (n) 值, 以保证每个节点在每回合内都有机会充当一次簇头节点, 从而平衡了节点的能量消耗。簇首节点确定后, 簇内节点选择接收信号强度最强的簇首, 加入该簇, LEACH协议的作者根据LEACH算法中每轮产生的簇头数与位置的随机性, 提出LEACH-C算法[3], 该协议是LEACH算法的集中式控制版本, 采用模拟退火算法获得更优的簇头选举策略, LEACH-C算法可以把每个节点的地理位置以及节点当前的能量报告给基站。基站把所有节点的能量取平均, 当网络中某些节点的能量低于平均值时, 将不能成为候选簇头节点, 从而更加有效的解决了低能量节点成为簇头节点的概率。

(2) 基于模糊逻辑学的分簇路由协议。文献[4]采用模糊逻辑学的原理来选择簇首节点, 采用了三个参数来判断节点成为簇首的概率, 即节点的剩余能量, 分成低、中、高三个等级, 节点的密集性, 分成低、中、高三个等级, 节点距基站的距离, 分成近、适中、远三个等级。模糊逻辑学根据三个参数, 每个参数拥有三个等级, 最终输出27种结果, 即根据27个等级来判断节点成为簇首的概率。例如一个节点的能量等级高, 密集性高, 距离近, 则该节点成为簇首的概率最大, 通过实验表明, 相比于LEACH协议, 该协议有效的延长了节点的生存时间。然而在该文献中为了选择簇首, 基站必须收集每个节点的位置与距离, 造成一定的能量开销, 为了克服这个缺陷, 文献[5]提出了CHEF协议, CHEF协议由每个节点自身判断是否成为簇首, 而不是由基站决定的, 首先每个节点在 (0, 1) 之间随机产生一个值, 当该值小于指定概率时, 该节点采用模糊理论计算自己成为簇首的几率, CHEF采用两个模糊变量, 即节点的剩余能量, 该节点在r距离范围内一跳节点距离的总和, r为簇首节点在整个区域中的平均通信距离。通过两个参数, 剩余能量采用低、适中、高三个变量, 距离的总和采用近、适中、远三个变量, 通过模糊理论后输出9种等级结果。通过这样的方式选择节点剩余能量最多, 局部最优化的节点成为簇首, 相比于LEACH协议, CHEF有效的延长了22.7%的生存时间。

(3) 基于遗传学的分簇路由协议。文献[6]中采用遗传学选择簇首节点, 每个节点代表一个染色体位, 簇首用1表示, 成员节点用0表示, 适应度函数包含了5个参数, (1) 成员节点直接与基站通信的距离和; (2) 成员节点与对应的簇首距离总和加上该簇首节点与基站的距离; (3) 簇距离的标准差; (4) 能量消耗, 包括, 成员节点传输数据到对应簇首的能量消耗, 簇首接收成员节点发送过来数据的能量消耗, 以及簇首融合成员数据传输到基站的能量消耗; (5) 网络中节点传输数据量的大小。通过适应度函数不断调整最优的簇首集, 均衡簇规模的大小, 以及网络能量消耗的最小化。文献[7]中也采用遗传学选择最优的数据聚合点, 并结合梯度算法优化结果, 目标在于使整个网络的生命期最大化。

(4) 基于博弈论的分簇路由协议。博弈论一种处理竞争与合作问题的数学决策方法, 博弈论中主要体现决策人, 局中人, 策略等几个因素, 无线传感器网络中节点为了保留能量可以自私的拒绝存储与转发下级节点的数据, 因此, 节点一旦加入数据的存储与转发就会消耗他们的部分能量, 减少其生存时间, 效用函数可以是通过不合作的方式来到达存储能量, 因此博弈论非常适用于无线传感器网络的能量效应路由协议与数据传输、融合机制中[8,9]。文献[10]中基于贝叶斯博弈论提出BGCRA分簇路由协议, 该协议采用异构网络, 网络中拥有两类节点, 能量高的与能量低的, 采用贝叶斯博弈论让能量高的竞选成为簇首节点, 该协议假设邻居节点服从泊松分布, 簇首节点竞选效用函数主要与节点初始能量度量, 路径能量损耗有关, 即节点的初始能量越高, 与邻居节点的通信能量越低, 该节点成为簇首的概率越大。该协议作者通过实验表明, 相比于LEACH协议, 该协议在簇首分布的均匀性以及节点的生存时间等都优于LEACH协议。

(5) 异构多级网络分簇路由协议。根据整个网络中节点初始能量的不同, GEORGIOS SMARAGDAKIS等人提出了一种异构的无线传感器网络SEP算法[11], SEP采用与LEACH类似的分簇方法, 不过SEP协议将整个网络分成两类节点, 能量较高的节点称为高能量节点, 能量低的称为正常节点, 高能量节点与正常节点分别采用各自的簇首选择阈值, 两类节点成为簇首的概率不同, 高能量节点成为簇首节点的机会大于低能量节点。高能量节点成为簇首每回合的轮数低于正常节点, 即高能量节点成为簇首的概率、频率高于低能量节点, 相较于LEACH算法, 在异构网络中, SEP均衡了两类节点的生存时间, 从而充分利用了整个网络的功耗。SEP协议虽然考虑了节点初始能量两级的异构性, 但不适合更多级能量的异构性, 文献[12]中针对节点初始能量不同, 即正常节点, 高能量节点, 超级能量节点, 提出了一种的三级异构EEHC分簇协议, 三级节点采用各自的簇首的选择阈值, 三级节点成为簇首的概率不同, 即超级节点成为簇首的概率与频率最高, EEHC可以平衡三级节点的生存时间。在文献[13]中, 作者提出了一种针对节点初始能量多级的异构网络DEEC协议, 在选择簇首节点时, 同时考虑了节点的剩余能量, 即节点成为簇首的轮转周期随节点的初始能量与剩余能量不同而变化。拥有更高的初始能量与剩余能量的节点成为簇首的概率与频率更大, 剩余能量采用估算的方式获得。实验表明, 在异构的网络中, 采用多级的分簇协议可以有效的均衡网络各类节点的生存时间。

(6) 混合能量与通信代价的HEED分簇协议。文献[14]中提出结合节点的剩余能量与通信代价的HEED分簇路由协议, 该协议在选取簇首节点的时候只要依据两个参数, 第一参数为节点的剩余能量, 根据节点的剩余能量情况选举初始的簇首节点, 节点能否成为最终的簇首依据节点竞选簇首过程中的迭代次数, 即节点剩余能量越高的节点在簇首竞选过程中的迭代次数越少, 越容易竞选成为簇首。第二参数为簇内通信代价, 用来判断重叠区域节点, 即在多个簇首节点通信范围内的节点归属问题, 判断的依据为簇内平均可达能量, 即簇内节点到达簇首节点的平均能量消耗。相比于LEACH协议, HEED协议分簇更均匀, 簇首选举速度更快, 节点能耗更均匀。

(7) EEPA分簇协议。文献[15]针对大规模的无线传感器网络提出一种新的能量效应动态分簇路由协议, EEPA协议, 通过接收到邻居节点的信号功率, 每个节点实时统计活动节点数量以及自身成为簇首的概率。该协议具体的实现方法, 首先统计网络中活动节点数, 设置隔离度, 隔离度越高代表节点越孤立, 每个节点测量在通信范围内所有邻居节点的信号功率和, 每个节点估算网络中活动节点数量, 每个节点可以根据阈值来判断是否更新簇首选择处理过程, 如果最后一个簇更新超过预先设置值, 激活簇更新进程。每个节点更新自身成为簇首的概率, EEPA通过动态的调整簇首总量与簇内成员集, 将能量较均衡的消耗在每个节点上, 延长了网络的工作寿命, 且每个节点完全自主的进行簇的更新过程。当节点数为2000时, 该协议的能量消耗是HEED的二分之一, 是LEACH的三分之一。

(8) Hausdorff分簇路由协议。文献[16]中提出了Hausdorff分簇路由协议, 首先结合节点的位置, 通信效率以及网络的链接性采用Hausdorff测距技术[17]将整个网络分成不同的簇, 其次结合节点的剩余能量与节点邻居的密集程度, 采用贪婪算法选举簇首节点, 最后簇首节点收集簇内节点采集的数据、融合后采用Dijkstra最短路由优先算法将数据传输给基站, 如果存在多条路径的话, 采用节点剩余能量较多的路径传输。相比于HEED协议, Hausdorff分簇过程能量开销更小。

(9) TABU-RCC分簇路由协议。文献[18]中提出TABU-RCC分簇协议, 该协议考虑了事件监测区域节点的覆盖问题与网络的连通性问题。在每个事件区域内都有足够有效的节点采集数据, 簇首节点之间可以构成一个有效的生成树, 保证整个网络节点之间的连通性。为了平衡每个节点的能耗, 选择簇首时, 该协议定义了一个节点线性组合函数分值, 该函数的分值主要取决于两个因素, 节点的剩余能量与节点所处状态 (激活, 休眠, 簇首) 所需要消耗的能量, 通过该函数来平衡网络中节点的能耗, 当然该函数也有一些前提约束条件, 必须保证每个事件监测区域至少有一个有效节点可采集数据, 每个有效的传感节点在通信范围内至少有一个簇首节点, 每个簇成员节点具有一定的上限, 所有簇首节点之间可构成一个有效的生成树, 保证整个网络的连通性。

(10) KOCA重叠式分簇路由协议。文献[19]中提出了重叠式分簇路由协议, KOCA协议, 通常的分簇协议中, 一个成员节点只属于一个簇首, 而KOCA协议定义了三类节点, 簇首节点, 正常节点, 边界节点, 正常节点只属于一个簇首节点的成员节点, 而边界节点可以成为多个簇首节点的成员节点。KOCA采用分布式协议, 初始情况下, 每个节点都以概率P竞选成为簇首。竞选成为簇首的节点广播告知周围的邻居节点, 广播消息中包含发送节点的ID号, 簇首节点的ID号, 允许成员节点加入该簇首节点的最大跳数K, 如果一个节点在K跳内无法寻找一个簇首节点, 则该节点就成为簇首, 每个成员节点也维护一个信息表, 该表包含了该成员节点归属的簇首ID, 该成员节点的ID, 到达该簇首的跳数HC, 如果成员节点接收到新的簇首发送的消息, 选择HC小的加入该簇, 如果一个节点同时拥有几个簇首节点, 那说明该节点为多个簇的交集、边界节点, 否则为正常成员节点, KOCA协议得到平均簇规模大小E (NC) =dk2, 各个簇的平均重叠度AOD=dk2/4, 簇首节点的通信开销MCHAD=O (dk2) , 成员节点的通信开销MJREQ=O (dk3) , 式中d表示每个节点的邻居集, k与簇首节点的通信距离有关。通过实验表明KOCA协议能够保证整个网络的连通性, 均衡每个簇规模的大小。

(11) 非均匀分簇路由协议。大部分作者的研究都考虑均衡每个簇规模的大小, 以均衡每个簇的能耗, 但是并没有考虑簇首节点的能耗问题, 通常情况下, 靠近基站的簇首节点不但要处理本簇节点收集过来的数据, 还有处理下一级簇首节点的数据, 因此功耗较大, 为了均衡每个簇首节点的能耗, 文献[20]中首次针对多跳路由协议中的“热区”问题, 提出了UCS非均衡分簇协议, 该协议采用不均衡分簇的方式, 靠近基站的簇规模相对较小, 减轻靠近基站的簇首节点处理本簇数据的能耗, 让其拥有更多的剩余能量处理下一级簇传输过来的数据。该协议采用的是以基站为圆心的两层同心圆结构, 即第一层簇首位于以R1为半径的圆内, 第二层簇首位于以R1到R2区域内, 第一层内的簇首不但要处理本簇的数据, 还要处理转发下一级簇首转发的数据。为了均衡两级簇首节点的能耗, 因此需要通过减小第一层的簇成员数目来降低其在簇内处理中消耗的能量。文献[21]中也提出了UCR非均匀分簇协议, 该协议假设传感节点布置在一个方形区域内, 基站位于该区域外, 首先每个节点以预先设置的概率阈值试探性的成为候选簇首, 如果一个节点竞选获胜, 则在该节点的通信范围内其他的候选簇首将不能成为最终的簇首, 为了减少靠近基站的簇规模大小, 靠近基站的候选簇首的竞争半径相对较小, 候选节点的竞争半径与网络中节点到基站的最远距离、最近距离, 以及候选簇首节点到基站距离有关。候选簇首根据节点的剩余能量高低竞争选出最终的簇首。相比于HEED协议, UCR协议有效的延长了网络的生存时间。

(12) 事件触发的分簇路由协议。文献[22]中提出了基于事件触发的分簇路由协议, ESDC协议, 即在事件触发区域的节点参与簇型结构的构建与数据的融合传输, 没有事件触发区域的节点处于休眠状态, 从而减少整个网络的能耗, 在事件触发区域, 节点成为簇首的概率主要与四个因素有关, 与节点到基站的距离成反比, 与节点到事件触发区域的中心成反比, 所谓的事件触发区域中心指该区域中所有节点坐标的平均坐标位置, 与节点的剩余能量成正比, 与节点周围处于事件触发状态的节点个数成正比。当成员节点同时在几个簇首节点的通信范围内时, 选择与基站通信距离最小的簇首并加入该簇。ESDC协议通过避开没有事件触发区域的节点参与簇型的构造与数据的处理, 减少了能耗与数据传输的碰撞等。实验表明, 相比与LEACH协议, ESDC算法在节点的生存时间较好, 数据传输延迟较小。

2.2 分簇路由协议的数据传输与融合

无线传感器网络中布置着大量的传感器网络, 通过这些节点采集到用户所需要的数据, 如果不对这些数据进行处理而直接传输到基站, 就会造成数据传输过程中的碰撞、冲突, 造成大量数据的冗余等, 因此节点必须对这些数据进行融合处理, 所谓数据融合, 是指将大量的数据或者信息进行处理, 去除其中的冗余信息, 只将少量的有意义的处理结果传输给汇聚节点, 得到一些更高效、更可靠、更符合用户需求的数据的过程。本文主要讨论的是基于簇型结构的数据聚合方式, 通常的簇型路由协议采用的是集中式的数据融合机制, 即整个网络分成簇型结构, 簇首节点收集完所有的簇内节点传输过来的数据后, 簇首对这些数据融合处理后传输给基站[23,24,25]。

LEACH, 文献[4], SEP, CHEF, EEHC, DEEC等协议数据传输方式采用两级的结构, 即簇内节点将采集到的数据传输给相应的簇首节点, 簇首节点收集完所有对应的簇内节点数据后, 经过融合处理后传输给基站。然而该类协议并没有提出具体的融合方式。Manjeshwar A等人提出了TEEN算法[26], TEEN算法与LEACH算法较大的不同点是, 在数据传输过程中, 该协议设置了两个阈值, 分别为硬阈值、软阈值两个参数, 硬阈值是被检测数据不能超过的数值, 而且软阈值决定了被测数据的波动范围, 只有当被监测数据超过硬阈值且被监测数据的变化幅度大于软阈值时, 节点才会传送最新的监测数据, 并设置为新的硬阈值。相对于LEACH算法, TEEN算法能够较大的减少节点之间数据传送的次数, 从而有效的减少了整个网络的功耗, 延长整个网络的寿命。APTEEN算法[27]则结合了LEACH与TEEN两种算法, 是一种主动型与响应型混合的数据传输模式, 当网络中有突发事件时, 数据传输模式将会采用与TEEN相同的模式 (响应型模式) , 只不过APTEEN算法多了一个计数器, 节点每传送一次数据, 对应的计数器将清零, 当计数器的时间到达的时候, 将采取主动型发送这个数据, 不再判断软、硬门限值。在LEACH算法中, 整个网络最大跳距为两跳, 这样就会导致远离基站的簇首节点, 能量消耗太大而过早的死亡, 影响到整个网络的性能, SIVA D.MURUGA-NATHAN等人提出了BCDCP多跳分簇算法[28], 簇首节点的选择由基站来控制, 基站首先将每个节点的当前能量取平均, 只有大于平均值的节点才有机会成为簇首节点, 这样就避开了低能量节点成为簇首节点的可能, 当簇首节点与基站的距离超过一定时, 不直接与基站通信, 而是借助其他簇首节点转发到基站, 选择其他簇首节点采用的是最小生成树算法, 这样就减轻了远离基站簇首节点的负担, 也扩展了整个网络的规模。在一些报警事件中, 用户只需要及时、准确的知道预警结果, 而不是传感节点采集的原始数据信息, 文献[29]中提出了TEKWEM协议, 定义两类节点, 一类传感节点, 一类网关节点, 网关节点拥有更大的能量以及通信能力, 每一层拥有网关节点, 下一层节点采集的数据通过上一层的网关节点转发, 网关将融合处理后的预警结果传输给用户, 减少数据传输的延迟。目的在于传输延迟最小化, 网络生存最大化, 算法包括事件监测模型与报警传输模型, 在事件监测中, 传感节点综合考虑自身采集的数据值是否超过阈值, 只有超过的情况下才将数据传输给对应的网关节点, 在传感区域中包括4类节点, 根据不同类别来决定其作用, 目的是为了实现报警的最小延迟, 报警传输选择的路径尽量做到传输延迟最小化, 网络生存最大化。EEPA协议在多跳传输数据阶段, 源节点向基站泛洪路由请求消息, 路径节点统计源节点到该节点的路径消耗, 最后基站统计每条路径的能量消耗, 并选择多条路径作为候选路径, 如果路径中的节点能量低于最低设置的阈值时, 该节点所在的候选路径将被移除。通过这样选择从源节点到基站能量消耗较低, 路径节点剩余能量较高的路径。Hausdorff协议簇首节点收集簇内节点采集的数据、融合后采用Dijkstra最短路由优先算法将数据传输给基站, 如果存在多条路径的话, 采用节点剩余能量较多的路径传输。UCR协议在数据传输阶段, 如果簇首节点到基站的距离小于指定的阈值, 则直接与基站通信, 如果超过阈值, 则该簇首节点需借助网络通信开销最小, 簇首剩余能量最多的节点做为上一级节点来转发数据。ESDC协议在数据通信阶段, 在有事件监测区域内簇首收集成员节点数据, 传输给基站或借助其他节点传输给基站, 在多跳的过程中, 主要借助于基站的最小通信距离节点作为转发节点, 判断节点是否能够成为转发节点的依据为, 假设两个簇首节点1与2, 簇首2是簇首1的下一级簇首, 在两个簇首节点的通信范围内有共同节点C, 且C到基站的距离大于簇首1到基站的距离, 则节点C就可以成为两个簇的转发节点。

3 比较与分析

由于无线传感器网络节点能量的限制, 拓扑结构的不稳定性等, 传统的路由协议无法直接运用于无线传感器网络中, 必须对其进行专门的研究, 而分簇路由协议拓扑结构更易管理, 拓展性能好, 非常适合于无线传感器网络中, 经过十多年的发展, 目前国内外已有较多的分簇路由协议, 不同的协议可能针对的场景不同, 解决的问题不同, 如LEACH等协议针对的是同构的网络环境, 而SEP等针对的是异构的环境, TABR-RCC重点解决事件监测区域节点的覆盖问题与网络的连通性问题, KOCA重点解决多个簇重叠式问题, ESDC考虑的事件触发区域节点与无事件触发区域节点的问题, UCR协议则考虑了簇首节点的能耗均衡问题, TEEN, APTEEN侧重于数据的传输与融合方式。因此很难直截了当的判断某种算法的优劣程度, 下面我们从几种主要性能指标来比较各种算法的性能。表一中, A代表节点的构造, 可以分为同构与异构, 通常的异构指节点的计算能力异构, 链路通信异构, 电源能量异构, 传输频率异构等, 加入部分异构节点可以延长整个网络的生存时间, 减少数据量的传输, 提高数据传输的可靠性[11,12,13,30,31], 当然同样也增加了一定的成本。B代表该协议的理论前提与实验仿真条件, C代表节点选择成为簇首的几率, D代表簇首节点与基站的通信跳数, E代表节点是否需要测量距离, 即节点是否需要GPS定位设备支持, 或定位算法估算坐标与距离。F代表簇规模的均匀性, G代表是否构造簇型结构, H代表是否提起数据的传输方式, I代表算法的复杂度, J代表簇头的选举速度, K代表参与簇首竞选或数据传输的节点分布。表一中横线代表文中未提, 或是无法判断, 从表一中可以看出大部分协议的仿真场景都是静态的, 都需要测量节点的距离, 进而估算出能耗。

4 总结与展望

进几年, 无线传感器网络备受各个国家的高度重视, 对无线传感器网络基础协议的研究成了各个国家关于无线传感器网络研究的重点也是难点, 而路由协议则是无线传感器网络其它协议研究的前提条件, 也是其核心技术之一, 采用分簇的路由结构成了目前关于无线传感器网络路由协议研究的重点, 本文分析了近几年关于无线传感器网络经典的分簇路由协议, 并对这些协议进行了比对与分析, 从总体上看, 无线传感器网络分簇路由协议的核心在于簇型结构的形成, 以及数据的传输与融合两个阶段, 从以上对各种经典协议的分析中, 我们可以看出, 对簇首节点的选择不能只简单的依据某个因素, 如节点剩余能量, 与其他节点的距离等, 而必须综合考虑各个因素, 合理的簇首比例与簇首分布位置都对均衡整个网络的能耗起到至关重要的作用, 应该尽量减少簇型结构形成过程中所需的能耗, 使节点剩余更多的能耗来处理数据的传输与融合, 在数据传输阶段, 应选择合理的传输路径, 减少数据传输的延迟, 提高融合的精度。随着传感节点硬件的不断发展, 关于路由协议的研究也必须考虑节点传输语音、图像等多媒体数据流的问题[32]。

参考文献

【分簇方法】推荐阅读：

(化学学习方法)高中化学学习方法10-16

铜钱草的养殖方法和水培的方法10-25