一种适用于无线传感器网络的动态自组织分层次路由方法

摘要

本发明涉及一种动态自组织分层次路由方法。该方法适用于无线传感器网络树形拓扑结构中，节点移动或失效导致路径失效数据无法传送的问题，能实现网络拓扑结构的动态调整。本发明采用基于多叉树状的拓扑结构建立网络，每个节点都维护一个层次路由表，并记录着以该节点为根的子树拓扑结构。路由表通过在节点接入申请时插入序号来对路由表进行有效的更新，解决了上层节点的路由表中出现节点编号重复的问题。为了兼顾能量和计算开销以及数据传输的实时性，路由表只在数据出现无法传输的时候，才重新组织拓扑结构，及时维护网络中的拓扑结构，在保证数据的可靠传输的同时，减少开销，发挥主被动路由协议的优势。

说明书

技术领域

本发明涉及一种适用于无线传感器网络的动态自组织分层次路由方法。该方法能克服无线传感器网络中节点失效对数据传输造成的影响，实现网络拓扑结构的动态调整。本发明属于无线传感器网络技术领域。

背景技术

无线传感器网络（Wireless Sensor Network）是一种无中心节点的全分布系统。大量传感器节点被密集部署于监控区域。这些传感器节点集成有传感器、数据处理单元和通信模块，它们通过无线信道相连，自组织地构成网络系统。微型传感器技术和节点间的无线通信能力为无线传感器网络赋予了广阔的应用前景。作为一种无处不在的感知技术，无线传感器网络广泛应用于军事、环境、医疗、家庭和其他商用、工业领域；在空间探索和反恐、救灾等特殊的领域，它也有着得天独厚的技术优势。

无线传感器网络工作在一定的物理环境中，受到无线信道间的互相干扰、无线通信链路时断时续、突发事件导致的网络任务负载变化、设备故障、地形和天气等综合因素的影响，传感器节点间通过无线信道形成的网络拓扑随时可能发生变化，而且变化的方式和速度都难以预测。这些变化往往会严重影响系统的功能，这就要求传感器节点能够随着环境的变化而适时地调整自身的通信工作状态。

无线传感器网络所广泛采用的树形拓扑协议在遇到节点移动或失效时无法有效解决上述变化问题，直接导致路径失效，数据无法传送的情况，而且会造成部分节点能耗过大，影响系统的使用寿命等问题。对网络整体而言，网络监测信息的准确性、完整性和时效性都将受到很大影响。

以数据为中心的无线传感器网络，将能源的高效使用作为首要设计目标，专注于从外界获取有效信息。本发明的网络拓扑结构的动态调整功能，能有效降低无线传感器网络中节点失效对数据传输造成的影响。

申请号为200710172037.2，申请日为2007年12月6日的国内发明专利公开了一种用于监控系统的无线自组网形成树形路由方法。该路由方法可以在无线多跳网络环境中为移动节点通信提供快速的路由建立和动态维护的路由协议。该专利采用集中式路由表管理及存储，不适用于单节点能力受限的传感网，而本发明采用分布式路由表维护机制使本路由在大规模传感网上的应用成为可能。相比该专利，本发明在父节点选择时，摒弃简单的路数最小优先算法，而选用基于QoS网络多指标组合优先算法，可以提高网络通信质量。另外，我们采用了不同于传统主动式路由方法根据设定间隔采用查询方式更新路由表，也不同于传统被动式路由经常需要进行路由发现的方法，即只在某一传输链路中出现错误时才重新建立路径，而且为了尽量减小开销，只是在出现数据无法传输的环节，才重新建立链路，使得数据能够继续得以正常的传输。并且上述专利只阐述路由建立的算法，并未阐述数据在路由传输时的解决方案。

申请号为201010265626.7，申请日为2010年8月27日的国内发明专利申请公开了一种适用于无线传感网路的多路径路由协议。该路由协议是采用基于树状的多路径路由协议缓解传感器网络协议时延大、网络可靠性差等问题，采用网状树形拓扑结构，提高了网络的鲁棒性。该方法所描述的过程通过备用多路径来修复路由表，不适用于单节点能力受限的传感网，本发明选用基于QoS网络多指标组合优先算法，可进一步提高网络通信质量。

申请号为201110033643.2，申请日为2011年1月31日的国内发明专利申请公开了一种基于树形无线传感器网络的路由方法和装置及传感器设备。该路由方法是预先根据各个传感器节点在树形网络中所处的层次以及层内位置，为传感器节点分配短地址，以此提高传感器节点进行报文转发过程中的路由传输效率。不同于本发明，该方法所描述的过程需要通过预设的树形路由表进行数据转发，并未涉及路由表的修复功能。

发明内容

本发明要解决的技术问题是，在无线传感器网络中节点移动或失效而导致路径失效数据无法传送的情况时，为网络提供一套重新组织拓扑结构的方法，有效降低上述在无线传感器网络中常见的，使系统数据传输受到影响的问题，实现网络拓扑结构的动态调整。

为了解决上述问题，本发明所采取的技术方案如下：

本发明所建立的网络是一种基于多叉树状的拓扑结构。在网络建立之初，整个区域内的所有节点都没有任何邻近节点的信息。此时某一个指定节点，在传感器网络中可认为是汇聚节点，将发起建立网络的广播。接收到此广播的邻近节点将发出此广播的节点作为潜在的父节点，并向父节点发送成为其子节点的请求，在接收到父节点表示加入成功的反馈后，将继续向下一层发出建网广播，搜寻下一层节点，以此类推，直到区域中的所有节点均被覆盖。

整个网络中的每个节点i都维护一个路由表，路由表记录着以节点i为根的子树的拓扑结构，并将树形结构的拓扑按照多叉树的先序遍历映射为一维线性列表，以便于在计算和存储能力有限的节点中进行管理和维护。每个新加入网络的节点在收到父节点确认其接入网络后，将通过单播一层层向上汇报新接入节点的信息，收到此消息的节点将根据此节点接入点的位置更新以其为根的整个树形子网。从而建立层次路由表。

在实际的网络中，存在节点间通讯距离不对等和外界干扰等因素，可能导致网络中出现一些问题，比如，父节点能够收到新的子节点的接入网络申请，但子节点无法收到父节点发出的接入成功信号。在这种情况下，为了保证数据的双向有效传输，子节点将通过接受其他节点的广播或是主动发出寻求接入网络的信息来与其他的节点建立父子关系。这种情况下，会产生两种可能，如子节点向父节点发送申请却没有收到接收确认ACK，转而向其他的节点发送请求接入网络的申请，而事实上父节点接收到了申请请求；再如子节点向父节点递交接入网络申请后，父节点回馈确认信息Response并认为子节点已经收到，而实际上子节点并未接收到确认消息Response，而认为申请不成功，转而寻求其他接入点。在以上两种情况中，父节点都会将此子节点作为申请成功处理，而向上层节点汇报更新上层的路由表。而事实上此节点通过了其他节点来接入网络，这样就造成了上层节点的路由表中出现节点编号重复的问题，而导致无法正确的选择合适的路径来传递数据。

我们通过在节点的接入申请中插入序号来对路由表进行有效的更新。每个节点只要发出一次接入的申请，其内部的序号就会累加。当接上层节点接收到更新路由表的信息后，将判断需要更新的节点的序号是否比原路由表中的更新。如果是新的路径则删除原路由表中以该节点为首的子树，按照更新的信息来刷新路由表。

同时，本发明建立拓扑结构动态组织机制解决，在实际的无线网络运行过程中，因为各种原因导致数据传输失败的问题，比如下一跳的节点移动后超出传输范围，节点异常而导致重启或是因为能量耗尽而导致失效。为了保证数据的可靠传输，拓扑结构需要重新组织。为了兼顾能量和计算开销以及数据传输的实时性，本发明采用不同于传统主动式路由方法根据设定间隔采用查询方式更新路由表，也不同于传统被动式路由经常需要进行路由发现的方法，本发明只在某一传输链路中出现错误时才重新建立路径，而且为了尽量减小开销，只是在出现数据无法传输的环节，才重新建立链路，使得数据能够继续得以正常的传输。

当数据无法传输时，拓扑重组分为两种情况，一种是上行传输，一种是下行传输。

上行数据传输的情况包括采集的数据向汇聚节点（一般认为为整棵树的根节点）传输，以及在网络中两点间传递数据时，目的节点不在以此节点为根的子树中，而将信息发送给其父节点等。在上行数据传输中，出现的传输失败有两种。第一种是下一跳节点（也就是父节点）移出传输范围或是失效，从而导致数据无法传输。此时，如果传输失败次数超过了设定的阈值，则通过广播寻找新的父节点，重新接入网络。第二种是下一跳节点由于重启或其他原因丢失了路由信息，而无法进行数据传递。在接收到数据需要进行转发时则会向上一跳节点反馈Error信息。此时，接收到Error信息的上一跳节点也将会通过广播找寻新的父节点。如果上行传输线路中的各个节点都未在其维护的路由表中发现到达目的节点的路径，则最终转发的数据包将会抵达汇聚节点，并产生异常信息。

下行数据传输的情况包括汇聚节点向网络中的其他节点发送控制信息，以及在网络中两点间传输数据时，目的节点位于以此节点为根的子树中，信息将发送给对应的子节点。在下行数据传输中同样会出现两种传输失败的情况。第一种是数据无法让下一跳节点（此节点的某一子节点）接收。此时，只要传输失败的次数超过设定的阈值，则此节点将发起广播进行寻找，只要储存有到达目的节点路径的节点将进行回应，此节点将选择层次相距最近的节点作为子节点，从而修复起已经失效的路径。如果下一跳节点就是目的节点，而此时目的节点丢失，无法传输数据，则将异常信息发回汇聚节点。第二种同样是下一跳节点（非目的节点）出现异常而丢失了路径信息。则此时将反馈Error信息，则此节点接收到Error信息以后将通过广播来寻找下一跳节点，修复下行路径。

新节点接入网络。在一个动态组织的网络中，不仅出现原本网络中的节点失效退出的情况也会有新节点补充进来的情况。对于一个欲向汇聚节点发送传感数据而又尚未加入网络，不存在任何路由信息的节点。首先，该节点将通过广播来搜寻邻近节点作为网络的接入点。在得到邻近节点的回复后，选择某一节点作为接入点，并建立父子关系。有新子节点接入的父节点将向上层汇报新的子节点的信息并且依次向上更新。

本发明利用无线传感器网络的动态自组织分层次路由方法，能达到的有益效果如下：

本路由方法主要针对目前无线传感器网络的路由协议所广泛采用的树形拓扑中出现的，节点移动或失效而导致路径失效数据无法传送的情况提供了一套重新组织拓扑结构的方法。此路由方法不仅保证了数据能够更加可靠地从传感器节点发回汇聚节点，还实现了类似无线自组织网络（Ad-Hoc Networks）中任意节点间的相互通讯，而不需要都经过汇聚节点进行转发，从而缓解了汇聚节点附近的能量热点消耗过快的问题。同时，由于对网络中路由表的有效维护，使得此路由方法能够充分发挥主动路由协议（Proactive Protocol）传输延迟短，突发数据传输率高的优势，并能够通过对拓扑结构进行动态组织在一定程度上发挥被动路由协议（Reactive Protocol）动态性强，不易受路由节点失效影响的优势。

 

附图说明

下面结合附图和实施例对本发明进一步说明。

图1为建网广播示意图；

图2为建网时节点接入网络示意图；

图3为节点成功接入网络示意图；

图4为子树内成员间的相互通信示意图；

图5为路由选择混乱示意图；

图6为路由表维护示意图；

图7为上行传输失败之情况一示意图；

图8为上行传输失败之情况二示意图；

图9为下行传输失败之情况一示意图；

图10为下行传输失败之情况二示意图；

图11为新节点接入网络时路由表的更新示意图。

 

具体实施方式

以下结合附图，利用具体实施的例子做进一步说明。

建立分层次的网络拓扑结构并建立起路由表的具体流程如下：

步骤 1：首先由设定的根节点Node 1（通常认为是汇聚节点）发起建网广播BroadForNet，见图1。广播包中主要包括根节点的ID，以及层数level。

步骤 2：接收到BroadForNet消息的并且尚未加入网络的节点将把发送此信息的节点ID作为潜在的父节点，并向其发送JoinIn消息，请求成为其子节点以加入网络。若此方法应用于无线传感器网络，考虑到传感器节点受能量制约，处理能力相当有限，在较短的一段时隙中处理多个子节点的加入申请比较困难，尤其是在节点密度较大的情况下。在此，每个节点在接收到BroadForNet后将在设定的一段时间范围内随机延时一段时间，再发送JoinIn请求，以避免多个节点密集接入的情况。

步骤 3：接收到子节点申请JoinIn消息的父节点将发回ReJoinIn的反馈消息，告知提出申请的子节点申请是否成功。在此可以加入一些判断，比如是否已经超过父节点能够支持的子节点的数目，为保证QoS，建议此子节点接入其他的父节点；或是接收到的lqi质量太差，低于某一阈值等，这些都可以作为是否建立链路的选择条件。通过这种父子节点双方之间的信息发送可以避免实际情况下的双方通讯距离不对等的情况，保证了只要父子关系能够建立，双方就能相互收发信息。如果子节点申请成功，则此父节点将向上层节点发送NodeReport的节点汇报消息，接收到此信息的上层节点将根据NodeReport消息中所包含的新加入节点的ID，对应的层数level，以及其父节点的ID（parentID）来更新自身所维护的路由子表，直到最上层的根节点完成路由表的更新。如图2中所示，节点5就接收到了节点3发回的申请成功的消息，接入了网络。节点3在发送ReJoinIn消息后，将更新自身的路由表，并向其父节点（节点1）发送NodeReport消息。随后节点1根据此消息在路由表中的节点3那条后面插入了新接入的节点5的信息。

步骤 4：子节点发出JoinIn消息后便进入等待父节点回应的阶段。如果接收到父节点的申请成功的反馈信息，同时说明了连接是双向可靠的，并且加入成功，那么节点将此潜在父节点作为上行路径中的父节点并将转发BroadForNet广播以搜索附近的其他节点。如果接收不到潜在父节点的反馈（或是收到了加入失败的信息），则节点返回步骤 2，继续进入等待接入网络的状态。从图2中可以看到节点6发送的JoinIn消息无法让节点3收到，因此节点6将回到等待接入的状态，并在接收到节点4的BroadForNet广播后成功地接入了网络，见图3。

从图4中可以看到，每个节点中记录了以其为根节点的子树的所有成员和拓扑信息，可以实现子树内所有成员间的相互通信。下层节点维护的路由表是上层节点维护的表的子集。例如，节点5要实现与节点7之间的通讯，则节点5首先将搜索自身所维护的路由子树，并未发现节点7，则向其父节点发送包含有目的节点ID的数据包，此时即进行上行传输，直到到达节点1，目的节点7出现在了节点1维护的路由树中，则开始进行下行传输，向距离下一level中的子树中包含目的节点的节点4转发数据，最终数据包通过节点4发送到目的节点7。

节点重新接入的情况下路由表的维护：

在实际建网过程中，可能出现图5所示情况，即由于一些不确定因素，如外部环境或是有多个节点同时在发送数据，导致数据包碰撞，降低了传输范围等的影响，导致节点3收到了节点6加入网络的消息，而节点6却无法收到节点3的返回消息ReJoinIn。此时节点6将继续等待其他节点的广播以接入网络，而节点3却认为节点6已经收到并成功加入了网络，这说明TinyOs中提供的Ack并不可靠。随后节点3将向上层网络发送NodeReport消息汇报新节点的加入情况。而事实上，当节点4发出BroadForNet广播后，正在等待中的节点6又成功地通过节点4接入了网络，并且节点4向上层节点汇报子节点的情况。此时节点1中将出现重复的节点6，这样会导致路由选择时出现混乱。

通过引入Seq机制可以很好地避免实际情况中这种问题的发生。如图6所示，节点6在尝试将节点3作为其父节点失败后，内部的Seq将增加，并在与节点4建立父子关系时汇报了其Seq，并且节点4将新加入的节点6的Seq也同时汇报。这样在节点1的路由表中出现了重复节点ID的情况时，节点将根据Seq的大小来更新路由表，在表中删除以原来的节点6为根节点的整棵路由子树，在新的位置插入节点6。此例中只有节点6一条记录需要删除。接着向旧节点6上行路径上的所有上层节点（此例中只有节点3）发出NodeDelete的消息（为了避免多个上层节点重复发送NodeDelete消息，只有子树中同时包括重复节点6的节点中的最下层的那个节点才向下发送此消息。在本例中即为节点1。若节点1上层还有其他节点，虽然这些节点中也将同时包含重复的节点6，但它们将只更新自身的路由表，而不会向下发送NodeDelete消息。NodeDelete消息将一直向下发送，每个接收到此消息的节点删除对应的节点的路由记录，并向下转发直至送达节点6的父节点），更新删除其路由表中节点6的记录。因为网络中的传输延迟和人为延时以避免消息碰撞等情况，上层节点按照接收到NodeReport的时间先后顺序来判断路径的新旧程度并不可靠，即节点6通过节点3向节点1发送的NodeReport消息可能比通过节点4向节点1发送的NodeReport消息达到时间更迟，因此，引入Seq机制保证了在节点重新接入的情况下路由表的有效维护。

传输失败的情况下拓扑结构的动态组织以及路由表的更新：

上行传输：

如图7（a）所示，节点8要传输数据到节点1，在数据的上行传输中出现了传输失败的情况（重传次数超过设定阈值），则节点6认为节点4可能已经超出了传输范围或是已经失效。此时节点6将发起BroadForParent的广播，查找新的接入点。从图中可以看到此广播范围覆盖了3，4，5，7，8五个节点，其中节点4可能已经失效而无法通讯，不做考虑。BroadForParent广播包中将带有节点的ID，其父节点的ID以及节点的Level等信息。节点7由于发现节点6与其有共同的图节点，因此不发出ReBroadForPa的回应。而节点8发现节点6为其父节点，因此也不作出回应。可以看到节点4之外的另一颗子树上的节点满足要求，并作出了反馈。对于节点6来说，它将在一段时隙内接收来自各节点的反馈，优先选择Level数较小的节点，以减小到达汇聚节点的跳数。同时节点6还将判断此申请接入节点是否处于自己的子树中，以免出现数据循环发送的错误。在此例中可以看到节点6收到了节点3和节点5的反馈，并率先尝试从节点3处重新接入网络，但是节点3无法收到其发出的申请消息。接着节点6再尝试接入节点5，并申请成功。此时对于节点5来说，它需要判断自身是否还有足够的存储空间来容纳节点6的子树，如果条件允许，则反馈申请成功的消息，并向上层发送NodeReport的消息更新上层节点的路由表，加入到节点6的路径。而与此同时，节点6将向一起为根的子树内发送NodeUpdate的消息，以更新节点8的Level信息。可以看到此时节点8的Level从原来的Level 3变为了Level 4。此外，节点6还将向其父节点（节点5）发送NodeReport的消息，以告之其维护的子树的拓扑信息，并通过节点5向更上层节点依次更新。当节点1收到节点6重新接入的NodeReport消息后，此时将对原来路由表中的以节点6为首的子树的信息进行删除和更新，最后通过NodeDelete消息告之节点6原来的父节点（节点4）删除已经过期的路由信息。由此，完成了上行路径传输中节点拓扑重组的过程。重组后的拓扑结构如图7（b）所示。

如图8（a）所示，若节点8同样想实现到节点1的上行数据传输，但由于节点4的出现意外，丢失了所有的路由信息（此时节点4根本未加入网络，不知道其父节点和所有的子节点的信息），而无法传递数据。这时节点4将向发送数据过来的节点6返回RouteTableError的错误信息。此时节点6将与图7中的例子中所描述的发出BroadForParent广播，以便重新连入网络。同样节点6收到了来自节点3和节点5的反馈信息，并成功接入了节点3（因为相比起节点5 Level更小）。由于节点6重新接入以后Level不变，所以也不需要发送NodeUpdate的信息，对其Level信息进行更新。重组后的拓扑结构如图8（b）所示。可以预见，由于节点4丢失了路径信息，所以当其剩余的子节点，如节点7需要传输数据时，将也会收到节点4的RouteTableError的反馈信息，从而通过其他节点重新接入网络。

下行传输：

如图9（a）所示，节点5要向节点8传输数据，但在节点1向节点4的传输过程中出现了传输失败。此时，节点1认为节点4已经无法进行通讯，并删除以节点4为根的子树，并发出BroadForChild的广播，寻找其他可能知道到达节点8路径的节点，此例中即节点6（节点6可能会因为位置变动而进入了节点1的Radio传输范围内）。此时，每个节点收到该广播的节点都将搜索其维护的路由表，其路由表中包含节点6的信息才会发送SubtreeJoinIn的消息进行回复。并且由于此时是下行传播，只有Level大于节点1的节点才有可能相应，若节点1还存在父节点，这个父节点将不会做出SubtreeJoinIn的回应。节点1在接收到节点6的请求将以其为首的整棵子树加入的消息后将发出一个ReSubJoinIn的确认消息。节点6在收到这个确认消息以后才改变其父节点的ID（即将节点1作为其父节点）并向其发送NodeReport消息，更新上层节点的路由表。随后将向其子节点发送NodeUpdate的消息，更新其Level信息。这样，随着节点6的重新接入，修复了原本因节点4出现问题而断开的从节点5到节点8的数据传递路径，新的网络拓扑结构如图9（b）所示。

如果出现节点4因意外情况而丢失了路有信息的情况。节点4将在接收到Data传输请求后返回一个RouteTableError信息。此时节点1将如前面提到的情况一样，发出BroadForChild广播，修复下行路径。见图10。

新节点接入网络时路由表的更新：

新节点加入网络的情况与上行传输中出现问题后的处理机制类似。如图11所示，新节点9有需要传输的数据触发下需要接入网络。此时节点9将发起BroadForParent的广播以寻找附近的接入点。若有多个节点响应，则选取Level较低的节点进行接入，此例中选择了Level为2的节点7，并发出JoinIn消息，请求接入。在收到节点7的ReJoinIn消息后，正式加入网络，并开始传输数据。上层节点在接收到NodeReport消息后，在其路由表中添加了新节点9的路由信息。