一种基于能量和距离的无线传感器网络分簇路由协议
时间：2009-11-30 11:11:33
手机看文章
扫描二维码
随时随地手机看文章
[导读]通过对无线传感器网络中典型分簇路由协议、LEACH协议和EECS协议进行的研究和分析，提出了一种改进的分簇方案ADEECS。利用延迟发送竞争消息的方法和新的通信代价公式很好地解决了EECS协议存在的问题，实现了簇头的均匀分布，有效地延长了网络寿命。但是不只是没有对参数权值w和通信半径R进行研究，这将是作者下一步的工作重心。另外，基于多跳的ADEECS也是下一步的研究方向。
1 引言
无线传感器网络(Wireless Sensor Network，WSN)是由大量具有特定功能的传感器节点通过自组织的无线通信方式，相互传递信息，协同地完成特定功能的智能专用网络。它综合了传感器、嵌入式计算、通信、分布式信息处理、计算机技术、微电子制造技术，能实时监测、感知和采集所监控区域内的各种信息，并对收集到的信息进行处理后传送给终端用户，在军事、灾难现场、环境监测和医疗救护等领域有广阔的应用前景。传感器网络一般投放在条件恶劣的环境或者难以涉足的地域中，节点电池的更换或能量的补充几乎是不可能的，所以节能路由协议的设计，对无线传感器网络来说意义十分重大。目前，提出的WSN路由协议主要有平面路由协议和层次路由协议两类，其中基于簇结构的层次路由协议是当前国内外研究的热点口。
1相关研究
WSN分簇路由协议设计的首要目标是通过高效的分簇算法形成合理的网络结构，通过主动的能量管理阻止网络连通性下降，延长网络的生命周期。最典型的无线传感器网络分簇路由协议是LEACH协议，人们在LEACH协议的基础上也研究出很多改进的分簇路由协议，EECS(Energy Efficient Clustering Scheme)协议就是其中一种经典的改进算法。
1.1LEACH协议
LEACH是分布式成簇协议的代表。每个节点产生一个0～1的随机数，如果这个数小于阈值，则该节点向整个网络广播它是簇头。阈值的计算公式为：
式中：p是簇头占所有节点的百分比，即节点当选为簇头的初始概率，实际的簇头概率以p为中心上下浮动；r是目前循环进行的轮；G是在最近1／p轮中没有当选过簇头的节点集合。可以看出，当选过簇头的节点在接下来的1轮中将不能成为簇头，而其他节点，因节点产生小于T(n)随机数的概率随之增大，所以节点当选为簇头的概率也增大。竞争成功的簇头节点广播当选的消息后，其他节点根据簇头广播信号的强弱决定加入哪个簇。由于簇头是随机挑选的，因此LEACH协议不能保证簇头在网络中分布均匀，而且节点根据自身通信代价最小原则选择加入哪个簇的成簇算法，但不能保证簇的负载均衡。
1.2 EECS协议
如前所述，LEACH等算法中，节点根据自身通信代价最小原则选择加入哪个簇，不能保证簇的负载平衡，而且没有考虑距基站较远的簇头能量耗费过快等问题。针对这些问题，EECS提出一个新的通信代价公式(2)来决定节点加入哪个簇：
式中：cost(j，i)是节点Pj加入簇头i的代价；d(Pj，CHi)是节点到簇头的距离。式(3)中f子函数保证最小化节点与簇头之间的通信代价；d(CHi，BS)是簇头i到基站的距离，式(3)中g子函数保证最小化簇头i到基站的通信代价；权值w的设置则根据具体应用，在成员节点能量与簇头能量消耗之间折衷，目标是最大化网络生命周期。节点Pj选择cost(j，i)最小的簇头i加入，从而保证每个簇头负载均衡。实验结果显示，EECS协议的网络生命周期较LEACH协议提高了30％以上。
2问题的描述
EECS算法的实质是在簇头选择阶段，总是让剩余能量最大的节点当选为簇头；在成簇阶段，联合考虑普通节点与簇头的距离，以及簇头与基站的距离。其创新之处在于：只有小部分节点参加簇头的竞选；在局部范围内广播消息，选举过程没有迭代；以节点的剩余能量为竞选参数；设计了簇头之间负载均衡的策略。
EECS协议存在的问题：
(1)EECS算法在成簇阶段让候选节点同时广播竞选消息COMPETE_HEAD，容易造成簇头分布漏洞问题。如图1所示，节点C在B的竞选半径内；节点B在A的竞选半径内，且剩余能量方面A>B>C。在这种情况下，C收到B的竞选消息退出竞选的同时，B收到A的竞选消息退出竞选，这就会造成局部簇头分布漏洞的情况。
(2)EECS算法在成簇阶段的通信代价只考虑了普通节点与簇头的距离，以及簇头与基站的距离，没有考虑簇头的剩余能量。这样就会造成部分剩余能量相对较少簇头节点的早死现象。
针对EECS协议存在的问题提出了ADEECS(Advanced EECS)协议，该算法在簇头选举阶段使用了竞争延迟的方法，在成簇阶段设计了新的通信代价计算公式。
3 ADEECS路由协议
方案中，假设已知发送节点的发射功率，接收节点可以根据接收信号的强度，计算二者之间距离的近似值；发射功率可控，即节点可以根据自身需要调整发射功率。采用与文献[5]相同的无线传输能量消耗模型。ADEECS协议按轮执行，每一轮分为网络部署，簇头选举，成簇，数据传输这4个阶段。
具体实现过程如下：
阶段1：网络部署阶段在网络部署阶段，让基站以一定的功率向网络内广播一个消息HELLO_MSG。传感器节点根据接收信号的强度计算出自己到基站的近似距离，在与基站通信时，依据这个距离选择适当的发射功率。在成簇阶段，还将利用这个信息来均衡簇头的负载。
阶段2：簇头选举阶段全局范围内预先设定一个0～1之间的阈值T，用来控制参加簇头竞选的节点比例。每一个节点生成一个0～1之间的随机数，记为u。若u
式中：T为最大约定的最大延迟时间；Eresidual为节点剩余能量；Eini是节点原始能量。
阶段3：成簇阶段簇头向网络所有节点广播自己成为簇头的消息HEAD_AD，内容为簇头节点的标识及该节点与基站的距离。普通节点接收到此消息后选择一个通信代价cost(CH)最小的聚类加入，并发送消息JOIN_REQ。通信代价表达式为：
式(5)中参数与式(2)和式(4)表示的意义相同。从式(5)可以看出，该通信代价综合考虑了节点与簇头的距离、簇头与基站的距离及簇头的剩余能量。从而实现了由聚类成员节点选择剩余能量较大，与自己距离较近，与基站距离较小的簇头形成簇，达到能量均衡的目的。
阶段4：数据传输阶段簇头向所有成员节点广播TDMA通信时隙调度信息TDMA_SCHEDULE。成员节点按分配好的TDMA时隙在某个时刻将自己检测到的数据发送给簇头。簇头在接收聚类成员发送数据的过程中进行数据融合，并将融合后的数据直接传输给基站，该过程采用单跳的通信方式。
4 ADEECS协议仿真与分析
仿真中，使用Matlab作为仿真平台，采用与文献[3]相同的能量消耗模型。仿真参数如表1所示。
文中将ADEECS与EECS和LEACH协议性能进行仿真对比。
4.1簇头分布的仿真对比
LEACH簇头个数取最优值。在仿真中，LEACH簇头个数为6；取T=0.15，R=26，w=0.8。由3种协议的簇头分布图(图2～图4)可以看出，LEACH协议簇头随机分布；EECS协议簇头分布比较均匀，但存在簇头漏洞问题；ADEECS协议簇头真正实现了均匀分布。所以，提出的延迟发送竞选消息的方法很好地解决了LEACH和EECS协议在簇头选举过程中存在的问题。
4.2网络寿命的仿真对比
定义第一个节点的死亡时间为无线传感器网络的网络寿命，用工作轮数表示网络的工作时间。如果剩余节点过少，那么整个网络的存在就毫无意义。仿真中为了更好地对比仿真结果，仿真曲线只选取剩余节点数大于50的情况。仿真结果如图5所示。
由图5可以看出，在成簇阶段，ADEECS协议综合考虑了簇头剩余能量、簇头与基站的距离以及簇成员节点与簇头的距离。这种通信代价计算方式很好地提高了网络性能，有效地延长了网络生命周期，达到了协议目的。
5结语
通过对无线传感器网络中典型分簇路由协议、LEACH协议和EECS协议进行的研究和分析，提出了一种改进的分簇方案ADEECS。利用延迟发送竞争消息的方法和新的通信代价公式很好地解决了EECS协议存在的问题，实现了簇头的均匀分布，有效地延长了网络寿命。但是不只是没有对参数权值w和通信半径R进行研究，这将是作者下一步的工作重心。另外，基于多跳的ADEECS也是下一步的研究方向。
无线传感器网络(Wireless Sensor Network，WSN)是由大量具有特定功能的传感器节点通过自组织的无线通信方式，相互传递信息，协同地完成特定功能的智能专用网络。它综合了传感器、嵌入式计算、通信、分布式信息处理、计算机技术、微电子制造技术，能实时监测、感知和采集所监控区域内的各种信息，并对收集到的信息进行处理后传送给终端用户，在军事、灾难现场、环境监测和医疗救护等领域有广阔的应用前景。传感器网络一般投放在条件恶劣的环境或者难以涉足的地域中，节点电池的更换或能量的补充几乎是不可能的，所以节能路由协议的设计，对无线传感器网络来说意义十分重大。目前，提出的WSN路由协议主要有平面路由协议和层次路由协议两类，其中基于簇结构的层次路由协议是当前国内外研究的热点口。
1相关研究
WSN分簇路由协议设计的首要目标是通过高效的分簇算法形成合理的网络结构，通过主动的能量管理阻止网络连通性下降，延长网络的生命周期。最典型的无线传感器网络分簇路由协议是LEACH协议，人们在LEACH协议的基础上也研究出很多改进的分簇路由协议，EECS(Energy Efficient Clustering Scheme)协议就是其中一种经典的改进算法。
1.1LEACH协议
LEACH是分布式成簇协议的代表。每个节点产生一个0～1的随机数，如果这个数小于阈值，则该节点向整个网络广播它是簇头。阈值的计算公式为：
式中：p是簇头占所有节点的百分比，即节点当选为簇头的初始概率，实际的簇头概率以p为中心上下浮动；r是目前循环进行的轮；G是在最近1／p轮中没有当选过簇头的节点集合。可以看出，当选过簇头的节点在接下来的1轮中将不能成为簇头，而其他节点，因节点产生小于T(n)随机数的概率随之增大，所以节点当选为簇头的概率也增大。竞争成功的簇头节点广播当选的消息后，其他节点根据簇头广播信号的强弱决定加入哪个簇。由于簇头是随机挑选的，因此LEACH协议不能保证簇头在网络中分布均匀，而且节点根据自身通信代价最小原则选择加入哪个簇的成簇算法，但不能保证簇的负载均衡。
1.2 EECS协议
如前所述，LEACH等算法中，节点根据自身通信代价最小原则选择加入哪个簇，不能保证簇的负载平衡，而且没有考虑距基站较远的簇头能量耗费过快等问题。针对这些问题，EECS提出一个新的通信代价公式(2)来决定节点加入哪个簇：
式中：cost(j，i)是节点Pj加入簇头i的代价；d(Pj，CHi)是节点到簇头的距离。式(3)中f子函数保证最小化节点与簇头之间的通信代价；d(CHi，BS)是簇头i到基站的距离，式(3)中g子函数保证最小化簇头i到基站的通信代价；权值w的设置则根据具体应用，在成员节点能量与簇头能量消耗之间折衷，目标是最大化网络生命周期。节点Pj选择cost(j，i)最小的簇头i加入，从而保证每个簇头负载均衡。实验结果显示，EECS协议的网络生命周期较LEACH协议提高了30％以上。
2问题的描述
EECS算法的实质是在簇头选择阶段，总是让剩余能量最大的节点当选为簇头；在成簇阶段，联合考虑普通节点与簇头的距离，以及簇头与基站的距离。其创新之处在于：只有小部分节点参加簇头的竞选；在局部范围内广播消息，选举过程没有迭代；以节点的剩余能量为竞选参数；设计了簇头之间负载均衡的策略。
EECS协议存在的问题：
(1)EECS算法在成簇阶段让候选节点同时广播竞选消息COMPETE_HEAD，容易造成簇头分布漏洞问题。如图1所示，节点C在B的竞选半径内；节点B在A的竞选半径内，且剩余能量方面A>B>C。在这种情况下，C收到B的竞选消息退出竞选的同时，B收到A的竞选消息退出竞选，这就会造成局部簇头分布漏洞的情况。
(2)EECS算法在成簇阶段的通信代价只考虑了普通节点与簇头的距离，以及簇头与基站的距离，没有考虑簇头的剩余能量。这样就会造成部分剩余能量相对较少簇头节点的早死现象。
针对EECS协议存在的问题提出了ADEECS(Advanced EECS)协议，该算法在簇头选举阶段使用了竞争延迟的方法，在成簇阶段设计了新的通信代价计算公式。
3 ADEECS路由协议
方案中，假设已知发送节点的发射功率，接收节点可以根据接收信号的强度，计算二者之间距离的近似值；发射功率可控，即节点可以根据自身需要调整发射功率。采用与文献[5]相同的无线传输能量消耗模型。ADEECS协议按轮执行，每一轮分为网络部署，簇头选举，成簇，数据传输这4个阶段。
具体实现过程如下：
阶段1：网络部署阶段在网络部署阶段，让基站以一定的功率向网络内广播一个消息HELLO_MSG。传感器节点根据接收信号的强度计算出自己到基站的近似距离，在与基站通信时，依据这个距离选择适当的发射功率。在成簇阶段，还将利用这个信息来均衡簇头的负载。
阶段2：簇头选举阶段全局范围内预先设定一个0～1之间的阈值T，用来控制参加簇头竞选的节点比例。每一个节点生成一个0～1之间的随机数，记为u。若u
式中：T为最大约定的最大延迟时间；Eresidual为节点剩余能量；Eini是节点原始能量。
阶段3：成簇阶段簇头向网络所有节点广播自己成为簇头的消息HEAD_AD，内容为簇头节点的标识及该节点与基站的距离。普通节点接收到此消息后选择一个通信代价cost(CH)最小的聚类加入，并发送消息JOIN_REQ。通信代价表达式为：
式(5)中参数与式(2)和式(4)表示的意义相同。从式(5)可以看出，该通信代价综合考虑了节点与簇头的距离、簇头与基站的距离及簇头的剩余能量。从而实现了由聚类成员节点选择剩余能量较大，与自己距离较近，与基站距离较小的簇头形成簇，达到能量均衡的目的。
阶段4：数据传输阶段簇头向所有成员节点广播TDMA通信时隙调度信息TDMA_SCHEDULE。成员节点按分配好的TDMA时隙在某个时刻将自己检测到的数据发送给簇头。簇头在接收聚类成员发送数据的过程中进行数据融合，并将融合后的数据直接传输给基站，该过程采用单跳的通信方式。
4 ADEECS协议仿真与分析
仿真中，使用Matlab作为仿真平台，采用与文献[3]相同的能量消耗模型。仿真参数如表1所示。
文中将ADEECS与EECS和LEACH协议性能进行仿真对比。
4.1簇头分布的仿真对比
LEACH簇头个数取最优值。在仿真中，LEACH簇头个数为6；取T=0.15，R=26，w=0.8。由3种协议的簇头分布图(图2～图4)可以看出，LEACH协议簇头随机分布；EECS协议簇头分布比较均匀，但存在簇头漏洞问题；ADEECS协议簇头真正实现了均匀分布。所以，提出的延迟发送竞选消息的方法很好地解决了LEACH和EECS协议在簇头选举过程中存在的问题。
4.2网络寿命的仿真对比
定义第一个节点的死亡时间为无线传感器网络的网络寿命，用工作轮数表示网络的工作时间。如果剩余节点过少，那么整个网络的存在就毫无意义。仿真中为了更好地对比仿真结果，仿真曲线只选取剩余节点数大于50的情况。仿真结果如图5所示。
由图5可以看出，在成簇阶段，ADEECS协议综合考虑了簇头剩余能量、簇头与基站的距离以及簇成员节点与簇头的距离。这种通信代价计算方式很好地提高了网络性能，有效地延长了网络生命周期，达到了协议目的。
5结语
通过对无线传感器网络中典型分簇路由协议、LEACH协议和EECS协议进行的研究和分析，提出了一种改进的分簇方案ADEECS。利用延迟发送竞争消息的方法和新的通信代价公式很好地解决了EECS协议存在的问题，实现了簇头的均匀分布，有效地延长了网络寿命。但是不只是没有对参数权值w和通信半径R进行研究，这将是作者下一步的工作重心。另外，基于多跳的ADEECS也是下一步的研究方向。
下载文档
