基于D-S算法的延长无线传感器网络生命周期的方法转让专利
申请号 : CN200710052464.7
文献号 : CN101094138B
文献日 : 2010-10-06
发明人 : 李德识 , 陈健 , 孙涛 , 王星磊 , 张茂林
申请人 : 武汉大学
摘要 :
本发明公开了一种基于D-S算法的延长无线传感器网络生命周期的方法，涉及无线通信技术领域中的无线传感器网络。本发明使用数据融合技术，是为了通过节点本身状态的测量数据，使用数据融合来判别该节点能否担任簇头的节点；通过合理的配置，从而延长网络的生命周期。本发明由于结合分簇路由技术，使用信念函数D-S算法来选择节点来担任簇头方案，同时在具体实施中对其进行了改进，因此能够对可扩展大规模传感器网络多尺度路由进行修正，并且实用性强，应用广泛。
权利要求 :
1.一种基于信念函数D-S算法的延长无线传感器网络生命周期的方法，应用于无线传感器网络，其拓扑结构包括检测区域(100)、基站(200)和服务终端(300)；
所述的检测区域(100)包括：
分别和第1簇头节点(110)无线连通的第1～N普通节点(111～11N)，分别和第2簇头节点(120)无线连通的第1～N普通节点(121～12N)，……
分别和第N簇头节点(1N0)无线连通的第1～N普通节点(1N1～1NN)；
第1、2……N簇头节点(110、120……1N0)分别与基站(200)无线连通，基站(200)与服务终端(300)有线连通；
首先由各个检测区域(100)内的普通结点收集环境信息，然后各个检测区域(100)内的普通节点将环境信息无线传输给此区域内的簇头节点，最后由各个检测区域(100)内的簇头节点将信息通过无线传输给基站(200)，基站(200)再通过有线传输将收集的各个普通节点的信息传输给服务终端(300)；
其特征在于是一种应用于无线传感器网络的信念函数D-S簇头继位算法，包括下列步骤：第0、开始；
第1、检测簇头当前状态值；
第2、未测到簇头节点收发器电流值时，返回第1步骤重新检测；测到簇头节点收发器电流值时，继续；
第3、将电流大小与信任度先验知识的平台数据库中数据相比较，取得电流事实前提的信任度；
第4、未测到簇头节点收发器信号强度值时，返回第1步骤重新检测；测到簇头节点收发器信号强度值时，继续；
第5、将信号强度大小与信任度先验知识的平台数据库中数据相比较，取得信号强度事实前提的信任度；
第6、令i＝0，j＝4；
第7、判断i与j的大小，当i≤j为真时，按照信任度先验知识的平台数据库中的规则信任度，计算第i+1轮的组合概率赋值和信任区间；
第8、根据信念函数D-S簇头继位算法得到第i+1轮的继位决策和身份报告，令i＝i+1，重复第7、第8步骤；
第9、当i≤j为假时，将第1轮至第5轮的身份报告与信任度先验知识的平台数据库中的数据相比较，获得簇头节点继位决策；
第10、结束。
说明书 :
技术领域
本发明涉及无线通信技术领域中的无线传感器网络，尤其涉及一种基于D-S(Dempster-Shafer，信念函数)算法的延长无线传感器网络生命周期的方法。
背景技术
无线传感器网络与传统的无线网络(如蜂窝移动电话网络)有着不同的设计目标：传统的无线网络的首要设计目标是提供高服务质量和高效带宽利用，其次才考虑节约能源；而无线传感器网络的首要设计目标是能源的高效使用，这也是无线传感器网络和传统的无线网络最重要的区别之一。
无线传感器网络是集成了监测、控制以及无线通信的网络系统，节点数目更为庞大(上千甚至上万)，节点分布更为密集。由于环境影响和能量耗尽，节点更容易出现故障。环境干扰和节点故障易造成网络拓扑结构的变化；而且传感器节点具有的能量、处理能力、存储能力和通信能力都十分有限。在无线传感器网络中，除了少数节点需要移动以外，大部分节点都是静止的。因为它们通常运行在人无法接近的恶劣甚至危险的远程环境中，能源替代困难甚至是无法替代，因此设计有效的策略延长网络的生命周期已成为无线传感器网络的核心问题。当然，从理论上讲，太阳能电池能持久地补给能源，但工程实践中生产这种微型化的电池还有相当的难度。这些独特的要求和制约因素使得研究无线传感器网络中的数据融合技术变得十分重要。
在非异质多传感器数据融合系统中，目前数据融合有两个作用：
一是通过融合减少数据传输量，降低能量消耗，从而延长网络寿命。这种方法中，国内外使用较多的数据融合算法有中心点融合算法和DFuse(Dynamic Data Fusion，动态数据融合)算法。
二是通过融合实现无线传感器网络的最优覆盖。如果节点间数据有冗余，则采取相应的措施关闭一些冗余节点，或者移走这些节点，减少没有必要的能量消耗。
除了数据融合方法，还有一些传统的能量节省方法，比如LEACH(Low Energy Adaptive Clustering Hierarchy，低能量自适应分簇)算法作为一种自适应分簇拓扑算法，它能够保证各节点等概率地担任簇头，使网络中的节点相对均衡地消耗能量，从而延长了网络的生存时间。或者用节点冗余休眠机制的方法来实现能量节省，达到延长网络生命周期。
无线传感器网络是集成了监测、控制以及无线通信的网络系统，节点数目更为庞大(上千甚至上万)，节点分布更为密集。由于环境影响和能量耗尽，节点更容易出现故障。环境干扰和节点故障易造成网络拓扑结构的变化；而且传感器节点具有的能量、处理能力、存储能力和通信能力都十分有限。在无线传感器网络中，除了少数节点需要移动以外，大部分节点都是静止的。因为它们通常运行在人无法接近的恶劣甚至危险的远程环境中，能源替代困难甚至是无法替代，因此设计有效的策略延长网络的生命周期已成为无线传感器网络的核心问题。当然，从理论上讲，太阳能电池能持久地补给能源，但工程实践中生产这种微型化的电池还有相当的难度。这些独特的要求和制约因素使得研究无线传感器网络中的数据融合技术变得十分重要。
在非异质多传感器数据融合系统中，目前数据融合有两个作用：
一是通过融合减少数据传输量，降低能量消耗，从而延长网络寿命。这种方法中，国内外使用较多的数据融合算法有中心点融合算法和DFuse(Dynamic Data Fusion，动态数据融合)算法。
二是通过融合实现无线传感器网络的最优覆盖。如果节点间数据有冗余，则采取相应的措施关闭一些冗余节点，或者移走这些节点，减少没有必要的能量消耗。
除了数据融合方法，还有一些传统的能量节省方法，比如LEACH(Low Energy Adaptive Clustering Hierarchy，低能量自适应分簇)算法作为一种自适应分簇拓扑算法，它能够保证各节点等概率地担任簇头，使网络中的节点相对均衡地消耗能量，从而延长了网络的生存时间。或者用节点冗余休眠机制的方法来实现能量节省，达到延长网络生命周期。
发明内容
本发明的目的就在于克服现有技术存在的上述缺点和不足，提供一种基于D-S算法的延长无线传感器网络生命周期的方法。具体地说，一是针对无线传感器网络应用的能量均衡性、最大化网络生存期等特点，提供一种D-S数据融合的算法，达到均衡网络能量消耗，以延长无线传感器网络生命周期；二是提供该算法的运行机制。本方法适用于大规模分簇路由基础上的动态无线传感器网络。
本发明的目的是这样实现的：
使用数据融合技术，是为了通过节点本身状态的测量数据，使用数据融合来判别该节点能否担任簇头的节点。通过合理的配置，从而延长网络的生命周期。
1、D-S簇头继位算法的概念
图1是一种无线传感器网络拓扑结构图。
无线传感器网络中的节点一般可以划分为簇头节点和普通节点两类，簇头节点对周围的普通节点进行管辖。由于簇头节点需要协调普通节点的工作，负责数据的融合和转发，能量消耗相对较大，所以需要一种D-S簇头继位算法即采用周期性地选择簇头节点的做法以均衡网络中的节点能量消耗。所述的簇头继位是指簇头节点继续担当簇头节点的职务；或由普通节点当选为簇头节点，履行原簇头节点的职责。因此，所述簇头继位算法是指无线传感器网络节点根据某个原则被任命为簇头节点的过程。
2、D-S簇头继位算法的原理
图2是D-S簇头继位算法的原理框图。
簇头继位算法是一种基于D-S证据推理技术、集中式的数据融合算法。为了延长无线传感器网络的生命周期，需要对传感器网络节点的健康状况包括剩余能量、传感器部件的工作情况及通信部件的工作情况进行监测。通过监控传感器节点的工作状态，可以及时调整传感器节点的工作周期，重新分配任务，从而避免节点过早失效，延长整个网络的生命期。而节点尽可能长的生命期的充要条件是节点健康，并且能量充足。节点的健康状况包括剩余能量、传感器部件工作情况及通信部件工作情况三个方面的要求。通过检测到节点工作电流，确认节点的传感器部件处于正常工作状态；如果能够检测到节点收发器的信号强度，确认节点的通信部件处于正常工作状态；由此知道此节点就是健康的，在剩余能量充足的情况下，就能作为簇头节点。因此选择节点的电流与信号强度值作为簇头继位算法的事实前提和规则前提，应用D-S证据推理方法得到节点电压满足作为簇头节点的信任区间。
3、D-S簇头继位算法的实现方法
D-S簇头继位算法的实现方法包括：
①如果节点有工作电流，则节点电压大于阈值(r)小于等于阈值(s)；
②如果节点收发器有信号强度，则节点电压大于阈值(t)或小于等于阈值(u)；
本算法的事实前提是(括号中的字母表示事实前提对结论的支持程度)：
①节点收发器有电流(p)；
②节点收发器有信号强度(q)；
算法中需要用到的公式：
m1({a})＝规则前提事实可信度×规则结论可信度＝p×r；
m1({b})＝p×s；
m2({a})＝q×t；
m2({b})＝q×u；
将两个概率分配函数合并：K＝1/[1-m1({a})×m2({b})-m1({b})×m2({a})]；
m({a})＝K×[m1({a})×m2({a})]；
m({b})＝K×[m1({b})×m2({b})]；
由信任函数求信任度：Bel({a})＝m({a})；
Bel({b})＝m({b})；
由似然函数求似然度：Pl({a})＝1-m({b})；
Pl({b})＝1-m({a})。
于是得到，
a、“簇头节点电压大于1v”为真的信任度为Bel({a})，非假的信任度为Pl({a})；
b、“簇头节点电压小于等于1v”为真的信任度为Bel({b})，非假的信任度为Pl({b})。
由命题a和b的信任度得到最终簇头节点继位的策略报告。
本发明提供的方法涉及：大规模可扩展传感器网络分簇路由算法和能量平衡的路由修正；最优能量约束和故障节点的路由修正；先验知识不确定性度量。
本发明具有以下优点和积极效果：
1、由于无线传感器网络结构采用分簇方式，通过簇头的管理来实现网络的数据传输，更适用于动态传感器网络。
2、分层传感器网络簇头选择机制采用D-S算法，提供了一种更能延长网络生命周期的簇头担任机制。簇内的通信代价低，集中式的簇头数据融合代价比较小。
3、能够实现基于故障节点的路由自修复、自配置和自管理，并且节约能量和延长网络的生命周期。
4、在簇头选择的方法中本发明首先引入D-S证据理论，这种方法在传感器网络领域节点判别机制未曾有过相关报道；与经典的统计方法Bayesian(贝叶斯)方法不同，该方法的不确定性度量更客观。
总之，本发明由于结合分簇路由技术，使用D-S算法来选择节点来担任簇头方案，同时在具体实施中对其进行了改进，因此能够对可扩展大规模传感器网络多尺度路由进行修正，并且实用性强，应用广泛。
本发明的目的是这样实现的：
使用数据融合技术，是为了通过节点本身状态的测量数据，使用数据融合来判别该节点能否担任簇头的节点。通过合理的配置，从而延长网络的生命周期。
1、D-S簇头继位算法的概念
图1是一种无线传感器网络拓扑结构图。
无线传感器网络中的节点一般可以划分为簇头节点和普通节点两类，簇头节点对周围的普通节点进行管辖。由于簇头节点需要协调普通节点的工作，负责数据的融合和转发，能量消耗相对较大，所以需要一种D-S簇头继位算法即采用周期性地选择簇头节点的做法以均衡网络中的节点能量消耗。所述的簇头继位是指簇头节点继续担当簇头节点的职务；或由普通节点当选为簇头节点，履行原簇头节点的职责。因此，所述簇头继位算法是指无线传感器网络节点根据某个原则被任命为簇头节点的过程。
2、D-S簇头继位算法的原理
图2是D-S簇头继位算法的原理框图。
簇头继位算法是一种基于D-S证据推理技术、集中式的数据融合算法。为了延长无线传感器网络的生命周期，需要对传感器网络节点的健康状况包括剩余能量、传感器部件的工作情况及通信部件的工作情况进行监测。通过监控传感器节点的工作状态，可以及时调整传感器节点的工作周期，重新分配任务，从而避免节点过早失效，延长整个网络的生命期。而节点尽可能长的生命期的充要条件是节点健康，并且能量充足。节点的健康状况包括剩余能量、传感器部件工作情况及通信部件工作情况三个方面的要求。通过检测到节点工作电流，确认节点的传感器部件处于正常工作状态；如果能够检测到节点收发器的信号强度，确认节点的通信部件处于正常工作状态；由此知道此节点就是健康的，在剩余能量充足的情况下，就能作为簇头节点。因此选择节点的电流与信号强度值作为簇头继位算法的事实前提和规则前提，应用D-S证据推理方法得到节点电压满足作为簇头节点的信任区间。
3、D-S簇头继位算法的实现方法
D-S簇头继位算法的实现方法包括：
①如果节点有工作电流，则节点电压大于阈值(r)小于等于阈值(s)；
②如果节点收发器有信号强度，则节点电压大于阈值(t)或小于等于阈值(u)；
本算法的事实前提是(括号中的字母表示事实前提对结论的支持程度)：
①节点收发器有电流(p)；
②节点收发器有信号强度(q)；
算法中需要用到的公式：
m1({a})＝规则前提事实可信度×规则结论可信度＝p×r；
m1({b})＝p×s；
m2({a})＝q×t；
m2({b})＝q×u；
将两个概率分配函数合并：K＝1/[1-m1({a})×m2({b})-m1({b})×m2({a})]；
m({a})＝K×[m1({a})×m2({a})]；
m({b})＝K×[m1({b})×m2({b})]；
由信任函数求信任度：Bel({a})＝m({a})；
Bel({b})＝m({b})；
由似然函数求似然度：Pl({a})＝1-m({b})；
Pl({b})＝1-m({a})。
于是得到，
a、“簇头节点电压大于1v”为真的信任度为Bel({a})，非假的信任度为Pl({a})；
b、“簇头节点电压小于等于1v”为真的信任度为Bel({b})，非假的信任度为Pl({b})。
由命题a和b的信任度得到最终簇头节点继位的策略报告。
本发明提供的方法涉及：大规模可扩展传感器网络分簇路由算法和能量平衡的路由修正；最优能量约束和故障节点的路由修正；先验知识不确定性度量。
本发明具有以下优点和积极效果：
1、由于无线传感器网络结构采用分簇方式，通过簇头的管理来实现网络的数据传输，更适用于动态传感器网络。
2、分层传感器网络簇头选择机制采用D-S算法，提供了一种更能延长网络生命周期的簇头担任机制。簇内的通信代价低，集中式的簇头数据融合代价比较小。
3、能够实现基于故障节点的路由自修复、自配置和自管理，并且节约能量和延长网络的生命周期。
4、在簇头选择的方法中本发明首先引入D-S证据理论，这种方法在传感器网络领域节点判别机制未曾有过相关报道；与经典的统计方法Bayesian(贝叶斯)方法不同，该方法的不确定性度量更客观。
总之，本发明由于结合分簇路由技术，使用D-S算法来选择节点来担任簇头方案，同时在具体实施中对其进行了改进，因此能够对可扩展大规模传感器网络多尺度路由进行修正，并且实用性强，应用广泛。
附图说明
图1是一种无线传感器网络拓扑结构图；
图2是D-S簇头继位算法的原理框图；
图3是D-S簇头继位算法的流程图。
其中：
100-检测区域，
110-第1簇头节点，
111、112……11N-第1、2……N普通节点；
120-第2簇头节点，
121、122……12N-第1、2……N普通节点；
……
1N0-第N簇头节点，
1N1、1N2……1NN-第1、2……N普通节点。
200-基站。
300-服务终端。
图2是D-S簇头继位算法的原理框图；
图3是D-S簇头继位算法的流程图。
其中：
100-检测区域，
110-第1簇头节点，
111、112……11N-第1、2……N普通节点；
120-第2簇头节点，
121、122……12N-第1、2……N普通节点；
……
1N0-第N簇头节点，
1N1、1N2……1NN-第1、2……N普通节点。
200-基站。
300-服务终端。
具体实施方式
下面结合实施例及附图对本发明作进一步说明：
如图1所示，本无线传感器网络的拓扑结构包括检测区域(100)、基站(200)和服务终端(300)；
所述的检测区域(100)包括：
分别和第1簇头节点(110)无线连通的第1～N普通节点(111～11N)，
分别和第2簇头节点(120)无线连通的第1～N普通节点(121～12N)，
……
分别和第N簇头节点(1N0)无线连通的第1～N普通节点(1N1～1NN)；
第1、2……N簇头节点(110、120……1N0)分别与基站(200)无线连通，
基站(200)与服务终端(300)有线连通。
本无线传感器网络工作原理如下：
首先由各个检测区域(100)内的普通结点收集环境信息，然后各个检测区域(100)内的普通节点将环境信息无线传输给此区域内的簇头节点，最后由各个检测区域(100)内的簇头节点将信息通过无线传输给基站(200)，基站(200)再通过有线传输将收集的各个普通节点的信息传输给服务终端(300)。这样用户就可以通过服务终端(300)了解到各个检测区域(100)内的环境信息。
如图3所示，信念函数D-S簇头继位算法的流程包括下列步骤：
第0、开始；
第1、检测簇头当前状态值；
第2、测到簇头节点收发器电流值？否，返回第1步骤重新检测；是，继续。
第3、将电流大小与PDB(Platform Data Base，信任度先验知识的平台数据库)中数据相比较，取得电流事实前提的信任度；
第4、测到簇头节点收发器信号强度值吗？否，返回第1步骤重新检测；是，继续。
第5、将信号强度大小与信任度先验知识的平台数据库中数据相比较，取得信号强度事实前提的信任度；
第6、令i＝0，j＝4；
第7、判断i与j的大小，当i≤j为真时，按照信任度先验知识的平台数据库中的规则信任度，计算第i+1轮的组合概率赋值和信任区间；
第8、根据信念函数D-S簇头继位算法得到第i+1轮的继位决策和身份报告，令i＝i+1，重复第7、第8步骤；
第9、当i≤j为假时，将第1轮至第5轮的身份报告与信任度先验知识的平台数据库中的数据相比较，获得簇头节点继位决策；
第10、结束。
工程技术人员按照上述方法根据其无线传感器网络的具体硬件环境编写代码，然后将其输入到各个无线传感器网络节点之中。
如图1所示，本无线传感器网络的拓扑结构包括检测区域(100)、基站(200)和服务终端(300)；
所述的检测区域(100)包括：
分别和第1簇头节点(110)无线连通的第1～N普通节点(111～11N)，
分别和第2簇头节点(120)无线连通的第1～N普通节点(121～12N)，
……
分别和第N簇头节点(1N0)无线连通的第1～N普通节点(1N1～1NN)；
第1、2……N簇头节点(110、120……1N0)分别与基站(200)无线连通，
基站(200)与服务终端(300)有线连通。
本无线传感器网络工作原理如下：
首先由各个检测区域(100)内的普通结点收集环境信息，然后各个检测区域(100)内的普通节点将环境信息无线传输给此区域内的簇头节点，最后由各个检测区域(100)内的簇头节点将信息通过无线传输给基站(200)，基站(200)再通过有线传输将收集的各个普通节点的信息传输给服务终端(300)。这样用户就可以通过服务终端(300)了解到各个检测区域(100)内的环境信息。
如图3所示，信念函数D-S簇头继位算法的流程包括下列步骤：
第0、开始；
第1、检测簇头当前状态值；
第2、测到簇头节点收发器电流值？否，返回第1步骤重新检测；是，继续。
第3、将电流大小与PDB(Platform Data Base，信任度先验知识的平台数据库)中数据相比较，取得电流事实前提的信任度；
第4、测到簇头节点收发器信号强度值吗？否，返回第1步骤重新检测；是，继续。
第5、将信号强度大小与信任度先验知识的平台数据库中数据相比较，取得信号强度事实前提的信任度；
第6、令i＝0，j＝4；
第7、判断i与j的大小，当i≤j为真时，按照信任度先验知识的平台数据库中的规则信任度，计算第i+1轮的组合概率赋值和信任区间；
第8、根据信念函数D-S簇头继位算法得到第i+1轮的继位决策和身份报告，令i＝i+1，重复第7、第8步骤；
第9、当i≤j为假时，将第1轮至第5轮的身份报告与信任度先验知识的平台数据库中的数据相比较，获得簇头节点继位决策；
第10、结束。
工程技术人员按照上述方法根据其无线传感器网络的具体硬件环境编写代码，然后将其输入到各个无线传感器网络节点之中。