论文部分内容阅读
摘要：传统的无线传感器网络（WSN）节点受到供电资源的束缚，能耗问题是网络中考虑的关键问题，而面向电能监测的无线传感器网络侧重于网络的稳定性和健壮性。无线传感器网络路由机制的好坏决定了传输路径的优劣，直接影响到整个网络的能量消耗和通信效率。文章分析了2种典型的分簇路由协议，详细阐述了PEGASIS协议的原理，分析了PEGASIS算法的优缺点，指出该算法存在的主要问题：延时问题和单链对网络的影响。针对该问题提出了PEGASIS的改进算法PEGASIS-I，介绍了该算法的原理和实现过程，并对改进算法进行仿真实验，得出的结论在时延和单链问题上得到了很大的改善。
关键词：WSN；电能监测；路由协议；PEGASIS-I
传统的移动Ad hoc网是以节点为中心的网络，而WSN是以数据为中心的网络。WSN并不需要维护网络中任何2个节点之间的路由，它仅仅需要维护传感器节点与汇聚节点（Sink）之间的路由。传感器节点的资源受到电源和计算能力的限制，节点数量较多，采集信息的冗余度较大使得移动自组网（MANET）的许多路由协议标准无法直接应用到WSN中。在无线传感器自组织网络中，传感器节点以多跳的方式传输到Sink点，此过程需要对网络的路由机制进行选择，而路由机制的好坏决定了传输路径的优劣，直接影响到整个网络的能量消耗和通信效率。
路由协议的设计要综合考虑多种性能指标。无论是平面路由还是分簇路由，多数路由协议通常只考虑能量约束。传统的无线传感器网络采用电池供电，节能是无线传感器网络的一个关键问题，本系统采用电源供电虽然不存在能量有限的问题，但随着应用范围的扩大节点的数量剧增也应考虑尽可能地降低能耗。不同的传感数据的紧急性不同，例如发生火灾时温度数据更加紧急，对传送的服务质量要求则更高。当网络规模较大和节点数量众多时，节点的加入和退出使得WSN网络拓扑结构频繁变化，因此鲁棒性和可扩展性也是评价路由协议好坏的重要指标。
1.WSN中几种典型的分簇路由协议
对于已有的路由协议的研究成果，按照网络的拓扑结构可以将WSN路由协议分为平面路由协议和分簇路由协议。典型的平面路由算法有DD，SAR，SPIN，Romor等。平面路由的优点是简单，易扩展，无需进行结构维护，具有良好的健壮性，而缺点则是网络中无管理节点，信息传输量大导致占用通信资源较大，以至于网络动态反应不灵敏。分簇路由协议就是将传感节点分簇，簇内通信由簇头节点进行数据融合来减少传输信息量，最后将簇内所有节点的数据传送给汇聚节点。分簇路由协议将节点分簇使得拓扑管理方便，簇内节点只发送数据给簇头使得能量利用高效、数据融合节约了通信资源，这些优点使得分簇路由成为当前研究的重点。
1.1LEACH协议
LEACH协议（Low Energy Adaptive Clustering Hierarchy）的实现分为成簇阶段和数据传输阶段。每轮中，相邻的节点动态地形成簇，随机的选择簇头节点；然后簇内节点把数据发给簇头，经数据融合后发送给基站节点。簇内节点按照时多分址TDMA向簇头发送数据；各簇间簇头采用码多分址CDMA竞用通道，竞用通道成功的簇头将融合后的数据发送给基站节点。随机选举的簇头使得节点能耗均衡，采用一跳通信传输时延较小，数据聚合减少了通信量。缺点在于离Sink较远的节点采用大功率通信耗费能量。
1.2PEGASIS协议
与其他树形结构路由协议不同，PEGASIs（Power Efficient Gathering in Sensor Information System）采用链状结构连接，解决了LEACH协议中产生重叠区域的问题。在一轮中，采用贪心算法，每个传感器节点只需和距离自己最近的邻居节点进行通信，链中节点在每轮通信中轮流作链首节点（chain head），链首发送数据传输指令给链尾，链尾再通过邻居节点传输数据给链首，链首将接收的信息进行数据融合，当所有节点与链首通信后链首将数据传送给sink，再进行新一轮的通信。采用链结构的好处是不需要维护簇的结构和记录簇成员数量，只需要知道上下级就可以了，而且在功耗方面PEGASIS比LEACH省近3倍左右。PEGASIS算法仅选择一个节点与Sink通信，利用数据融合，延长了网络的生命期。但链中远距离的节点数据传输到基站节点的时间延迟会很大，而且单一的链首可能会成为整个网络的瓶颈。
2.PEGASIS算法的具体描述
2.1PEGASIS网络模型
（1）基站节点位置不变并应具有足够的能量。（2）网络中所有的节点都是静止的。（3）网络中所有节点能够彼此通信，且都有足够的能量能与基站直接通信，同时需要知道其他节点的位置。（4）网络中所有节点都具有相同的性质和功能，都可以进行压缩、去冗余等数据融合并且能量有限。
2.2成链阶段
在成链过程中，采用贪心算法的原理。贪心算法是从初始解向目标逼近的过程，每一次逼近都尽可能求出最优的解，总是作出当前最好的选择。首先选择距离基站节点最远的节点作为链尾，然后链尾比较网络中离自己最近的节点加入到链中，节点依次加入直到加入链首，链首即为“首领节点”通过轮流担当的方式，最终链首将融合后的数据发送给基站，至此完成一轮的成链过程（见图1）。
2.3数据传输阶段
一轮中，通过贪婪算法成链选举出“首领节点”后，首领节点与基站进行通信的过程就是数据传输阶段。数据传输过程可以使用令牌（Token）和时隙2种传输方式。假设网络中只有5个节点，编号分别设为IJl，L2，L3，L4，L5，在本轮中选定L3为“首领节点”，令牌传输过程是首领节点L3向链中发送令牌，让它通过L2传播到端点L1，数据的传播方向与令牌相反，当L3接收到融合后的返回数据，再向另一端L5发送令牌，当两端的数据都到达后，首领节点将数据发送给基站节点，则本轮结束。时隙传输方式与令牌传输令牌不同，要求链上所有节点都保持同步传输。 3.PEGASIS算法存在的问题
PEGASIS算法与LEACH算法相比缩短了节点之间的通信距离，并且邻近节点进行数据融合减小了业务流量，使得传输数据的能耗很小；限制了仅需通过一个“首领节点”直接向基站发送数据，“首领节点”通过轮流当选的方式平衡了网络中的能量消耗，并且增强了网络对于随机节点死亡的抗干扰能力。PEGASIS算法虽然在能耗上有其优势，但仍存在一些问题：（1）单一的链传输数据。当网络规模变大时，网络中的链将会变得很长，每轮的传输传输时间会延迟，甚至可能因为节点的死亡而使整个网络反复成链而增加延时。（2）在成链过程中，如果链的方式选取不合理，将会导致网络中个别节点负担高于其他节点，造成节点能耗不均衡。（3）在单链式算法中，单一的链首向基站节点传输数据也会使其产生瓶颈。
4.改进的算法PEGASIS-I
本应用中，要求监测系统具有很大的实时性，而PEGASIS算法会造成很大的时延使得实时性不够完善，同时只有一个链首节点会成为通信瓶颈导致网络中断，因此对PEGASIS算法进行改进，提出的改进算法PEGASIS-I如下：（1）将整个区域所有节点沿着链的顺序分成N个子链，子链的个数可以根据节点部署的环境情况而定，每个子链中节点采用并行传输的办法让邻近节点相互发送数据，这样节点只需要知道子链内的位置信息，节约了节点位置信息的开销。（2）每个子链内成链规则采用并行传输的方法：第一步将邻近节点分为2组，一组向另一组发送数据；第二步在链中发送数据的节点不需要再被访问，而接收到数据的节点继续寻找其邻近节点发送它们融合后的数据；然后重复第一、二步，直到0（1gm）步之后，单独发送融合后的数据到达该子链的首领节点。实际上，链已经被一个树覆盖了，当首领节点运动时，树状结构也不得不随之运动。（3）每个子链的子链首可以直接与汇聚节点通信，也可以按照贪心算法依次成链将数据传输给总链首，然后发送数据到汇聚节点。
在应用中，随着节点数量的增加，可能进行多次并行传输，为演示改进算法的原理，采用少量节点进行说明，图2给出了改进算法PEGASIS-I的路由体系结构。
5.PEGASIS-I算法仿真分析
在PEGASIS算法中，链上数据的传输是按顺序执行的，而链首只有接收到所有数据才能发送给汇聚节点，当节点的数量较多会造成很大的时延甚至可能造成传输中断。改进的PEGASIS-I算法采取并行传输，节点之间可以同时进行传输，这将大大减少传输时延。如图3所示，PEGASIS算法每轮的传输时延在0.05s左右，而PEGASIS-I算法每轮的传输时延在0.02s左右，相比之下，改进算法PEGASIS-I在传输时延上有很大的改善，增强了系统的实时性和健壮性。
关键词：WSN；电能监测；路由协议；PEGASIS-I
传统的移动Ad hoc网是以节点为中心的网络，而WSN是以数据为中心的网络。WSN并不需要维护网络中任何2个节点之间的路由，它仅仅需要维护传感器节点与汇聚节点（Sink）之间的路由。传感器节点的资源受到电源和计算能力的限制，节点数量较多，采集信息的冗余度较大使得移动自组网（MANET）的许多路由协议标准无法直接应用到WSN中。在无线传感器自组织网络中，传感器节点以多跳的方式传输到Sink点，此过程需要对网络的路由机制进行选择，而路由机制的好坏决定了传输路径的优劣，直接影响到整个网络的能量消耗和通信效率。
路由协议的设计要综合考虑多种性能指标。无论是平面路由还是分簇路由，多数路由协议通常只考虑能量约束。传统的无线传感器网络采用电池供电，节能是无线传感器网络的一个关键问题，本系统采用电源供电虽然不存在能量有限的问题，但随着应用范围的扩大节点的数量剧增也应考虑尽可能地降低能耗。不同的传感数据的紧急性不同，例如发生火灾时温度数据更加紧急，对传送的服务质量要求则更高。当网络规模较大和节点数量众多时，节点的加入和退出使得WSN网络拓扑结构频繁变化，因此鲁棒性和可扩展性也是评价路由协议好坏的重要指标。
1.WSN中几种典型的分簇路由协议
对于已有的路由协议的研究成果，按照网络的拓扑结构可以将WSN路由协议分为平面路由协议和分簇路由协议。典型的平面路由算法有DD，SAR，SPIN，Romor等。平面路由的优点是简单，易扩展，无需进行结构维护，具有良好的健壮性，而缺点则是网络中无管理节点，信息传输量大导致占用通信资源较大，以至于网络动态反应不灵敏。分簇路由协议就是将传感节点分簇，簇内通信由簇头节点进行数据融合来减少传输信息量，最后将簇内所有节点的数据传送给汇聚节点。分簇路由协议将节点分簇使得拓扑管理方便，簇内节点只发送数据给簇头使得能量利用高效、数据融合节约了通信资源，这些优点使得分簇路由成为当前研究的重点。
1.1LEACH协议
LEACH协议（Low Energy Adaptive Clustering Hierarchy）的实现分为成簇阶段和数据传输阶段。每轮中，相邻的节点动态地形成簇，随机的选择簇头节点；然后簇内节点把数据发给簇头，经数据融合后发送给基站节点。簇内节点按照时多分址TDMA向簇头发送数据；各簇间簇头采用码多分址CDMA竞用通道，竞用通道成功的簇头将融合后的数据发送给基站节点。随机选举的簇头使得节点能耗均衡，采用一跳通信传输时延较小，数据聚合减少了通信量。缺点在于离Sink较远的节点采用大功率通信耗费能量。
1.2PEGASIS协议
与其他树形结构路由协议不同，PEGASIs（Power Efficient Gathering in Sensor Information System）采用链状结构连接，解决了LEACH协议中产生重叠区域的问题。在一轮中，采用贪心算法，每个传感器节点只需和距离自己最近的邻居节点进行通信，链中节点在每轮通信中轮流作链首节点（chain head），链首发送数据传输指令给链尾，链尾再通过邻居节点传输数据给链首，链首将接收的信息进行数据融合，当所有节点与链首通信后链首将数据传送给sink，再进行新一轮的通信。采用链结构的好处是不需要维护簇的结构和记录簇成员数量，只需要知道上下级就可以了，而且在功耗方面PEGASIS比LEACH省近3倍左右。PEGASIS算法仅选择一个节点与Sink通信，利用数据融合，延长了网络的生命期。但链中远距离的节点数据传输到基站节点的时间延迟会很大，而且单一的链首可能会成为整个网络的瓶颈。
2.PEGASIS算法的具体描述
2.1PEGASIS网络模型
（1）基站节点位置不变并应具有足够的能量。（2）网络中所有的节点都是静止的。（3）网络中所有节点能够彼此通信，且都有足够的能量能与基站直接通信，同时需要知道其他节点的位置。（4）网络中所有节点都具有相同的性质和功能，都可以进行压缩、去冗余等数据融合并且能量有限。
2.2成链阶段
在成链过程中，采用贪心算法的原理。贪心算法是从初始解向目标逼近的过程，每一次逼近都尽可能求出最优的解，总是作出当前最好的选择。首先选择距离基站节点最远的节点作为链尾，然后链尾比较网络中离自己最近的节点加入到链中，节点依次加入直到加入链首，链首即为“首领节点”通过轮流担当的方式，最终链首将融合后的数据发送给基站，至此完成一轮的成链过程（见图1）。
2.3数据传输阶段
一轮中，通过贪婪算法成链选举出“首领节点”后，首领节点与基站进行通信的过程就是数据传输阶段。数据传输过程可以使用令牌（Token）和时隙2种传输方式。假设网络中只有5个节点，编号分别设为IJl，L2，L3，L4，L5，在本轮中选定L3为“首领节点”，令牌传输过程是首领节点L3向链中发送令牌，让它通过L2传播到端点L1，数据的传播方向与令牌相反，当L3接收到融合后的返回数据，再向另一端L5发送令牌，当两端的数据都到达后，首领节点将数据发送给基站节点，则本轮结束。时隙传输方式与令牌传输令牌不同，要求链上所有节点都保持同步传输。 3.PEGASIS算法存在的问题
PEGASIS算法与LEACH算法相比缩短了节点之间的通信距离，并且邻近节点进行数据融合减小了业务流量，使得传输数据的能耗很小；限制了仅需通过一个“首领节点”直接向基站发送数据，“首领节点”通过轮流当选的方式平衡了网络中的能量消耗，并且增强了网络对于随机节点死亡的抗干扰能力。PEGASIS算法虽然在能耗上有其优势，但仍存在一些问题：（1）单一的链传输数据。当网络规模变大时，网络中的链将会变得很长，每轮的传输传输时间会延迟，甚至可能因为节点的死亡而使整个网络反复成链而增加延时。（2）在成链过程中，如果链的方式选取不合理，将会导致网络中个别节点负担高于其他节点，造成节点能耗不均衡。（3）在单链式算法中，单一的链首向基站节点传输数据也会使其产生瓶颈。
4.改进的算法PEGASIS-I
本应用中，要求监测系统具有很大的实时性，而PEGASIS算法会造成很大的时延使得实时性不够完善，同时只有一个链首节点会成为通信瓶颈导致网络中断，因此对PEGASIS算法进行改进，提出的改进算法PEGASIS-I如下：（1）将整个区域所有节点沿着链的顺序分成N个子链，子链的个数可以根据节点部署的环境情况而定，每个子链中节点采用并行传输的办法让邻近节点相互发送数据，这样节点只需要知道子链内的位置信息，节约了节点位置信息的开销。（2）每个子链内成链规则采用并行传输的方法：第一步将邻近节点分为2组，一组向另一组发送数据；第二步在链中发送数据的节点不需要再被访问，而接收到数据的节点继续寻找其邻近节点发送它们融合后的数据；然后重复第一、二步，直到0（1gm）步之后，单独发送融合后的数据到达该子链的首领节点。实际上，链已经被一个树覆盖了，当首领节点运动时，树状结构也不得不随之运动。（3）每个子链的子链首可以直接与汇聚节点通信，也可以按照贪心算法依次成链将数据传输给总链首，然后发送数据到汇聚节点。
在应用中，随着节点数量的增加，可能进行多次并行传输，为演示改进算法的原理，采用少量节点进行说明，图2给出了改进算法PEGASIS-I的路由体系结构。
5.PEGASIS-I算法仿真分析
在PEGASIS算法中，链上数据的传输是按顺序执行的，而链首只有接收到所有数据才能发送给汇聚节点，当节点的数量较多会造成很大的时延甚至可能造成传输中断。改进的PEGASIS-I算法采取并行传输，节点之间可以同时进行传输，这将大大减少传输时延。如图3所示，PEGASIS算法每轮的传输时延在0.05s左右，而PEGASIS-I算法每轮的传输时延在0.02s左右，相比之下，改进算法PEGASIS-I在传输时延上有很大的改善，增强了系统的实时性和健壮性。