论文部分内容阅读
摘要：本文提出了一种基于分布式动态分簇的协同算法，该算法首先将网络分成一个个的簇，然后在簇内构造任务协同策略，从而实现优化任务的分配尽量减少节点间的通信量，降低能耗，并进行仿真实验分析。
关键词：无线传感器网络；分簇；节点调度；任务协同；任务分配
【中图分类号】 G642 【文献标识码】 B 【文章编号】 1671-1297（2013）01-0027-01
一 引言
无线传感器网络在为人类社会带来方便的同时，也提出了新的技术挑战。规模超大、资源严格受限及网络拓扑动态变化等特点给网络的通信、组网、基础设施建设、管理和协同信息处理带来了新的问题。无线传感器网络协同的基本内容有：资源协同、任务协同以及信号与信息的协同[1]。任务协同主要指的是任务的描述、分解、分配、调度与执行，包括冲突监测与消除等，是无线传感器网络协同的主要内容，其中，任务描述与任务分配是任务协同最主要的部分也是本文讨论的重点，主要目的是通过优化任务的分配尽量减少节点间的通信量，降低能耗，从而延长网络生命期。
二 分布式的动态分簇算法
本文对当前技术进行研究的基础上提出了一种分布式的动态分簇算法。本算法基于以下假设：
1）每个节点都有一个唯一的id号。
2）所有节点都有同样的通讯半径和初始能量。
3）网络是对称的（即如果节点A能接收到来自节点B的消息则B也能接收到A的消息。
4）在通讯半径内的节点可以无障碍的相互通信。
本算法分为三个阶段：
1）邻居发现阶段，所有节点广播一个非常短的包含了本地节点id的初始化。
接收到该消息的节点将消息中包含的节点id添加到自己的邻居表中，并统计自己的邻居数目。所有节点都周期性的广播用以刷新邻居表，如果超过一定周期当前节点没有收到某邻居的广播消息则认为改节点已经死亡，并将其从本地邻居表中删除。
2）簇头选择阶段，簇头的选举遵循以下两个规则：
规则A：每个节点都按概率T成为簇头，T跟节点剩余能量和节点密度相关，表达式如公式1所示：
T=a×nn-current Nn-max+（1-a）×[En-current En-max+r×（1-En-current En-max）]
公式1
其中a∈（0，1），nn-current是当前节点的邻居数，即当前节点的度， Nn-max是根据网络规模和节点通讯半径、节点部署密度而得出的邻居数的经验数据。En-current是当前节点的能量，En-max是节点的初始能量。r是当前节点未当选簇头节点的轮数，当选簇头后置零。
规则B：节点在等待一段时间后如果没有接收到任何簇头发来的声明消息则自动发起成为簇头并通知周围的节点，形成一个簇。
图1 节点归属示图
3）成簇阶段，节点成为簇头并随机等待一段时间（为了防止节点的状态同步）之后便广播一个自己当选簇头的DEC MSG消息，声明自己为簇头的角色，消息中攜带了本地节点ID和跳数信息hop。消息结构如下：
typedef sruct
Int8_t sign； //消息标志位
Int8_t ID； //源节点id
Int8_t hop； ///消息跳数
ClusteringPacket；
周围节点接收到簇头广播的消息后根据消息中携带的跳数信息来加入距离自己最近的簇头发起的簇，如图1示，节点C和D距离簇头A两跳，距离簇头B三跳，所以节点c，D属于簇头A决定的簇，节点E则属于簇头B决定的簇。节点C，D的确认消息沿C（D）一F-A返回到簇头A，其中节点F和G距离簇头A同为一跳。
分簇完毕后，在数据传输阶段，当簇头节点的能量降阶达到某门限值后主动在本簇内发起广播消息，重新选举簇头，并将自己一定跳数范围内的节点纳入自己发起的新簇。这种簇头轮换的方法可以防止某些节点因长期担任簇头角色而过早死亡，通过将能量消耗平均分布到整个网络以延长网络的生命周期。
本算法的优点在于完全分布式的簇头选举方法，只根据自身剩余能量和邻居个数就可以决定自己是否能够成为簇头，基本不需要与其他节点进行协商，更不需要全局信息，大大节省了通讯的能量开销；度数越大的节点越容易成为簇头，从而降低了通信代价同时可以提高数据融合的效果。
参考文献
[1] J Liu.J Reich，F Zhao.Collaborative In-Network Processing for Target Tmcking[J].J on Applied Signal Processing（EURASIP），20o3；23（4）：378-391
关键词：无线传感器网络；分簇；节点调度；任务协同；任务分配
【中图分类号】 G642 【文献标识码】 B 【文章编号】 1671-1297（2013）01-0027-01
一 引言
无线传感器网络在为人类社会带来方便的同时，也提出了新的技术挑战。规模超大、资源严格受限及网络拓扑动态变化等特点给网络的通信、组网、基础设施建设、管理和协同信息处理带来了新的问题。无线传感器网络协同的基本内容有：资源协同、任务协同以及信号与信息的协同[1]。任务协同主要指的是任务的描述、分解、分配、调度与执行，包括冲突监测与消除等，是无线传感器网络协同的主要内容，其中，任务描述与任务分配是任务协同最主要的部分也是本文讨论的重点，主要目的是通过优化任务的分配尽量减少节点间的通信量，降低能耗，从而延长网络生命期。
二 分布式的动态分簇算法
本文对当前技术进行研究的基础上提出了一种分布式的动态分簇算法。本算法基于以下假设：
1）每个节点都有一个唯一的id号。
2）所有节点都有同样的通讯半径和初始能量。
3）网络是对称的（即如果节点A能接收到来自节点B的消息则B也能接收到A的消息。
4）在通讯半径内的节点可以无障碍的相互通信。
本算法分为三个阶段：
1）邻居发现阶段，所有节点广播一个非常短的包含了本地节点id的初始化。
接收到该消息的节点将消息中包含的节点id添加到自己的邻居表中，并统计自己的邻居数目。所有节点都周期性的广播用以刷新邻居表，如果超过一定周期当前节点没有收到某邻居的广播消息则认为改节点已经死亡，并将其从本地邻居表中删除。
2）簇头选择阶段，簇头的选举遵循以下两个规则：
规则A：每个节点都按概率T成为簇头，T跟节点剩余能量和节点密度相关，表达式如公式1所示：
T=a×nn-current Nn-max+（1-a）×[En-current En-max+r×（1-En-current En-max）]
公式1
其中a∈（0，1），nn-current是当前节点的邻居数，即当前节点的度， Nn-max是根据网络规模和节点通讯半径、节点部署密度而得出的邻居数的经验数据。En-current是当前节点的能量，En-max是节点的初始能量。r是当前节点未当选簇头节点的轮数，当选簇头后置零。
规则B：节点在等待一段时间后如果没有接收到任何簇头发来的声明消息则自动发起成为簇头并通知周围的节点，形成一个簇。
图1 节点归属示图
3）成簇阶段，节点成为簇头并随机等待一段时间（为了防止节点的状态同步）之后便广播一个自己当选簇头的DEC MSG消息，声明自己为簇头的角色，消息中攜带了本地节点ID和跳数信息hop。消息结构如下：
typedef sruct
Int8_t sign； //消息标志位
Int8_t ID； //源节点id
Int8_t hop； ///消息跳数
ClusteringPacket；
周围节点接收到簇头广播的消息后根据消息中携带的跳数信息来加入距离自己最近的簇头发起的簇，如图1示，节点C和D距离簇头A两跳，距离簇头B三跳，所以节点c，D属于簇头A决定的簇，节点E则属于簇头B决定的簇。节点C，D的确认消息沿C（D）一F-A返回到簇头A，其中节点F和G距离簇头A同为一跳。
分簇完毕后，在数据传输阶段，当簇头节点的能量降阶达到某门限值后主动在本簇内发起广播消息，重新选举簇头，并将自己一定跳数范围内的节点纳入自己发起的新簇。这种簇头轮换的方法可以防止某些节点因长期担任簇头角色而过早死亡，通过将能量消耗平均分布到整个网络以延长网络的生命周期。
本算法的优点在于完全分布式的簇头选举方法，只根据自身剩余能量和邻居个数就可以决定自己是否能够成为簇头，基本不需要与其他节点进行协商，更不需要全局信息，大大节省了通讯的能量开销；度数越大的节点越容易成为簇头，从而降低了通信代价同时可以提高数据融合的效果。
参考文献
[1] J Liu.J Reich，F Zhao.Collaborative In-Network Processing for Target Tmcking[J].J on Applied Signal Processing（EURASIP），20o3；23（4）：378-391