一种无线传感网缓解网络拥塞发生的控制方法

摘要

本发明的无线传感网缓解网络拥塞发生的控制方法，其特征在于，包括：a.部署和建立多层无线传感器网络；b.节点判断是否有拥塞趋势，如有，则广播拥塞趋势信息；c.对拥塞趋势节点是否在数据流将要流经的下一跳路径上进行判断；d.选择不含具有拥塞趋势节点的下一跳路径进行传输。对层间分流不可用的情况，可采用同一网络覆盖层内降速的方案，对数据传输速率进行等分降速。本发明有效地缓解了拥塞现象的发生，降低了数据拥塞和丢失的概率。还公开了通过建立一跳网络邻居列表、建立具有远近标示的多个网络邻居列表的来建立多层网络覆盖的方法；引入缓冲队列占空比

说明书

技术领域

本发明涉及一种无线传感网缓解网络拥塞发生的控制方法，更具体地说，尤其涉及一种采用布设多层覆盖的树状拓扑无线传感器网络、并通过检测网络拥塞发生的趋势结合采用事前层间分流和调整网络数据流量的无线传感网缓解网络拥塞发生的控制方法。

背景技术

无线传感器网络是通过把具有感知能力的节点采用分布式方式部署在需要进行感知和监控的场所，由传感器采集到的物理量通过无线自组织网络采用无线和多跳的方式汇集到中心节点，从而实现对环境无线感知和无线监测目的的短距离无线通信技术。

无线传感器网络是以被动的方式传送数据的，即网络节点平时是处于休眠状态的，只有在中心节点需要数据时才向感知节点发送数据请求命令，感知到或者监测到的数据采用零散的、短小的数据包向中心节点发送回采集到的数据。所以，在无线传感器网络中拥塞现象一般不太容易发生，但是当在某个局部范围内加入网络的节点数量很多时这种现象就会很容易发生。

在无线传感器网络目前还很少有与此相关的研究成果报道，而在其他种类的网络中，一般是采用事后的方式进行流量的调节，即当有网络拥塞发生后再调节通过上游节点的网络流量，这种解决网络拥塞的方法最大的缺点就是需要的调节时间较长，对需要较低网络延时的应用场景很难采用；在其他类型的网络中还有采用数据分流的方法解决网络拥塞问题的报道，这种方法适用的前提条件是网络中有其他的空闲路由可以利用，但是对能量敏感、低成本的无线传感器网络不是很好的选择，因为这种分流是在mesh网络拓扑结构的同一网络覆盖层内进行，而且有多条路由交叉，解决起来十分困难，即使研究出解决的办法也是非常复杂的，很难在无线传感网内使用。

发明内容

本发明为了克服上述技术问题的缺点，提供了一种采用布设多层覆盖的树状拓扑无线传感器网络、并通过检测网络拥塞发生的趋势结合采用事前层间分流和层内调整网络数据流量的无线传感网缓解网络拥塞发生的控制方法。

本发明定义了在这里我们所研究的无线传感器网络中发生的拥塞现象，这里所研究的网络拥塞是指网络中某个局部范围内包括的一个或多个网络节点的缓冲队列已满，这样如果继续通过这个或这些节点传送数据，很可能会发生数据包丢失的危险，同时也会造成由于疏通网络拥塞而引起的正常数据传输速率的下降。

本发明的无线传感网缓解网络拥塞发生的控制方法，其特别之处在于，包括以下步骤：a.网络部署和建立，布设和建立两层或两层以上的树状拓扑结构的无线传感器网络；b.拥塞趋势的判断，网络中的节点判断其自身是否具有拥塞发生的趋势，如果有拥塞发生趋势，则向网络中广播拥塞趋势信息；c.处理与否的判断，激活路由所包含的节点在接收到拥塞趋势信息后，对具有拥塞趋势的节点是否为数据流将要流经的下一跳节点进行判断，如果不是，无需进行处理；如果是，则执行步骤d；d.层间分流，根据具有拥塞趋势的节点的上一跳路径所处的网络覆盖层，选择不包含该具有拥塞趋势节点的其他网络覆盖层的路径对数据进行传输，以实现缓解网络拥塞发生的目的。本发明中的缓解网络拥塞发生的控制方法是以两层或两层以上网络覆盖的无线传感器网络为基础的，实现网络分层覆盖的目的是使得网络数据分流比较容易得到实现；网络中的每个节点均实时地对自己进行拥塞趋势判断，具有拥塞趋势的节点广播出拥塞趋势信息后，只有处于激活状态的节点才可接收到，并对具有拥塞趋势的节点所在的位置进行判断。如果具有拥塞趋势的节点在数据流将要流经的下一跳路径上，则优先采用层间分流的方法进行数据流流向的调节。

本发明的无线传感网缓解网络拥塞发生的控制方法，步骤a所述的两层或两层以上的树状拓扑结构的无线传感器网络部署和建立包括以下步骤：a-1.部署第一层网络，通过布设传感器节点、路由节点和中心节点，组建树状拓扑结构的第一层网络覆盖；a-2.部署n层网络，根据需要部署的层数n，通过在第一层的相邻节点之间插入n-1个节点，来建立n层网络覆盖的无线传感器网络；其中n≥2；a-3.建立网络一跳邻居列表，网络中的各节点通过广播HELLO信息，建立各自的一跳邻居列表；a-4.修改当前邻居列表和创建新的邻居列表，网络中的各节点根据接收到的邻居节点的邻居列表信息，再结合自身的邻居列表信息，来建立具有远近标示的多个网络邻居列表；以实现与部署的n层覆盖网络相对应。步骤a-1为布设第一层网络覆盖，步骤a-2为根据需要布设建立n层网络覆盖需要的节点；步骤a-3为网络中的节点建立一跳邻居列表信息，步骤a-4为节点通过对邻居列表的修改和建立，并根据部署网络层数n，形成具有远近标示的多个网络邻居列表。

本发明的无线传感网缓解网络拥塞发生的控制方法，步骤b中所述网络中节点的拥塞趋势的判断采用节点中缓冲队列是否将充满为依据，其判断如下：

设                                                为在时刻t时节点的缓冲队列的占空比，将其定义为：

其中，为节点缓冲队列所包含的总的位数，为常量；为节点在时刻t在缓冲队列中实际容纳的排队信息所占的位数，为变量；并引入一个拥塞预测因子λ，它的取值范围介于0和1之间（0<λ<1）；当网络节点实际检测到的缓冲队列占空比达到或者超过预先设定的拥塞预测因子λ时，即判断该节点有拥塞发生的趋势，从该节点开始向网络广播拥塞趋势信息，这个信息以广播帧的形式发送，这个帧包括该节点的网络地址和有拥塞趋势发生的标志信息。网络中的每个节点均设置有用于数据接收和处理的缓冲队列区域，以实现对待处理数据的存储，通过检测该区域是否有充满的趋势，即可反应出该节点是否具有拥塞发生趋势。其中的拥塞预测因子λ，可以根据网络实际运行情况进行选取，例如在0.8～0.9之间进行取值。

本发明的无线传感网缓解网络拥塞发生的控制方法，还包括以下步骤：e.层内等分降速，在采用步骤d层间分流无法缓解网络拥塞趋势的情况下，采用层内等分降速的方案，即保持当前的路径不变，在当前的路径上降低数据流的传输速率，设降速前的数据传输速率是R，将其分成M等分，每次调节都降低，即第一次降速后传输速率降为,第二次降速后传输速率降为，以此类推；降速节点每次降速后都监听是否还有来自具有拥塞趋势节点的拥塞趋势信息广播，如果没有，则降速调节完成；如果还能继续接收到来自该节点的拥塞趋势广播信息，则继续进行降速，直至监听不到拥塞趋势广播信息为止；其中，数据传输速率R的单位为bit/s，M为大于等于1的正整数。上述的步骤d为采用层间分流，但如果采用层间分流的路径不可用，就无法实现“绕过”具有拥塞趋势节点进行传输的目的；而步骤e中公开的层内等分降速方案可以较好地解决这一问题。

本发明的无线传感网缓解网络拥塞发生的控制方法，所述步骤c处理与否的判断中，对具有拥塞趋势的节点是否为数据流将要流经的下一跳节点的判断方法为：执行判断的节点根据收到的拥塞趋势信息，判断当前路由的下一跳网络节点的地址是否与具有拥塞趋势节点的网络地址相同，如果不相同，则具有拥塞趋势的节点不在数据流将要流经的下一跳节点上；如果相同，则表明具有拥塞趋势的节点在数据流将要流经的下一跳节点上，需要执行相应的层间分流或层内等分降速处理。执行判断的节点在判断的过程中，是通过对接收到的拥塞趋势信息中所包含的拥塞趋势节点地址与当前路由的下一跳网络节点的地址是否为同一地址来实现。

本发明的无线传感网缓解网络拥塞发生的控制方法，所述步骤d的层间分流中，选择不包含该具有拥塞趋势节点的路径的方法为：执行判断的节点通过判断其路由表中是否有除具有拥塞趋势的节点之外的其他下一跳网络节点地址存在，如果有，选择一条进行分流传输；如果没有，则认为不能通过层间分流方法来缓解拥塞发生的趋势。

本发明的有益效果是：本发明的无线传感网缓解网络拥塞发生的控制方法，通过建立多层覆盖的树状拓扑结构的无线传感器网络以及通过检测网络拥塞发生的趋势，并采用网络不同覆盖层间分流和相同网络覆盖层内降速的方法来调节数据传输的流向和流速，有效地缓解了网络中某个节点或某个区域拥塞现象的发生。本发明还公开了一种通过建立一跳邻居列表、对已建立以来的邻居列表进行修改和建立新的网络邻居列表的方法，实现了具有n层网络结构的树状拓扑无线传感器网络的建立；在节点判断是否具有拥塞趋势时，引入了缓冲队列的占空比的概念和计算公式，使得拥塞趋势的判断更加容易和准确。本发明的控制方法，具有事先判断、事先调节的特点，实现了在拥塞真正发生前就进行防拥塞调节，从而较好地缓解了数据传输中拥塞现象的真正发生。

附图说明

图1是本发明中实施例的网络拓扑结构示意图；

图2是本发明实施例中的方法流程图。

具体实施方式

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

其中，图1和图2分别给出了本发明中实施例的网络拓扑结构示意图和方法流程图。图1中黑色实心的节点表示整个无线传感器网络的中心节点，其他的节点为路由节点和传感器终端节点，其中用虚线表示的节点为处于休眠状态的节点，用实线表示的节点为激活节点，用点划线表示的节点为检测到的具有拥塞趋势的节点。

本发明实施例提供了一种在无线传感器网络中通过布设和建立多层覆盖的树状拓扑网络，然后利用在不同网络覆盖层之间数据流分流和层内调节数据流降低数据流的流速相结合来缓解网络拥塞现象发生的控制方法。通过对有拥塞发生趋势的节点或局部的节点群预先预测、拥塞信息预先广播，再结合层间数据流分流或者层内调节数据流的流向和降低数据流的流速可以较好地缓解无线传感器网络局部数据流拥塞现象的发生。

下面结合附图1详细说明本发明的实施过程。

这里以二层网络覆盖为例，在网络部署阶段，先部署节点g（中心节点）、节点a、c、e和节点i、k、m，这些节点组成第一层网络覆盖；然后，在第一层网络的相邻节点间分别再插入一个节点部署，这样节点a、b、…、l和m组成第二层覆盖网络，如果部署n层覆盖网络，就在第一层的相邻节点间插入n-1个节点。

在网络建立阶段，节点f和h向周围广播HELLO信息，中心节点g接收到这两个节点发送的HELLO信息后，给这两个节点分配网络地址，也将这两个节点的网络地址写入它的网络邻居列表，中心节点g也向周围广播HELLO信息，节点f和h接收到这个信息后，也将中心节点g的网络地址写入到它们各自的网络邻居列表中；节点e和i也向周围广播HELLO信息，当中心节点g接收到这些信息后，也给节点e和i分配网络地址，并将这两个节点的网络地址加入到自己的网络邻居列表，当这两个节点接收到中心节点g的HELLO广播信息后，也将中心节点g的网络地址写入到它们各自的网络邻居列表；网络中的其他节点d,j,k,c,b,l,m,a也采用相同的方法建立它们各自的网络一跳邻居列表。

接下来，网络节点进入邻居列表修改阶段和新的邻居列表建立阶段，网络中的每个节点向网络中广播自己的网络邻居列表信息，当中心节点g接收到节点f和h发送的网络邻居列表信息后，知道节点i是节点h的网络邻居，节点e是节点f的网络邻居，再结合中心节点g自身的网络邻居列表信息，中心节点g就知道自己的邻居节点i和e以及h和f应当位于不同的网络覆盖层，这样中心节点g就再建立一个网络邻居列表，把节点i和e或者节点h和f的网络地址写进去，然后把写到新的网络邻居列表中的节点网络地址从原来的网络邻居列表中删除；

当节点h和f接收到中心节点g的网络邻居列表信息后，结合自己的网络邻居列表，保持中心节点g在它们各自的网络邻居列表不变，当节点h接收到节点i广播的网络邻居列表信息后，再结合存储在节点h的网络邻居列表，节点h就知道节点i和j应该处在不同的网络覆盖层，再结合中心节点g广播的网络邻居列表，节点h知道节点i是中心节点g的一跳邻居，而节点j不是，这样节点h判断节点i应该是距离自己较近的一跳网络邻居，而节点j是距离自己较远的一跳网络邻居，这样在节点h中再建立一个远端网络邻居列表，将节点j的网络地址写进去，而将节点j从节点h原来的网络邻居列表中删除，同时把原来的邻居列表标记为近端网络邻居列表，节点f也采用同样的方法和步骤将节点d的网络地址加入到自己的远端网络邻居列表，同时将节点d从原来的网络邻居列表中删除，将原来的邻居列表标记为近端网络邻居列表，当节点h和f再将各自的近端邻居列表和远端邻居列表信息广播后，中心节点g再结合自己的网络邻居列表信息将原来有节点h和f网络地址的邻居列表标记为近端网络邻居列表，而将原来有节点e和i的网络地址存在的邻居列表标记为远端邻居列表，网络中的其他节点a、b、c、d、e和节点i、j、k、l、m也采用同样的过程和方法在各自的节点中建立一个近端网络邻居列表和一个远端网络邻居列表；

假定当前从节点a到中心节点g的多条位于不同的网络覆盖层的传输路由已经建立，其中一条是当前选择的最佳路由，其他各条路由均为备选路由，这些路由信息都存储在了从节点a到中心节点g的各个路由节点的路由表中，其中中心节点g存储的是选中的各条路由包括的所有节点的网络地址，而其他节点的路由表中存储的是选中的各条路由中的下一跳节点的网络地址；

对于网络中有无拥塞趋势的检测，根据前面对网络拥塞的定义应该采用判断节点中缓冲队列是否将充满为依据，这里需要引入一个拥塞预测因子λ，它的取值范围介于0和1之间（0<λ<1），实际使用时将这个预测因子预存在每个网络节点中，用户根据网络的实际运行情况对这个预测因子可以进行调节，判断节点有无拥塞趋势时，在节点中动态计算缓冲队列的占空比，将其定义为：

分母N表示在节点中实际设计的缓冲队列包含的总的位数（常量），分子表示网络实际运行中在某个时刻t在节点的缓冲队列中实际容纳的排队信息所占的位数（变量），当网络节点实际检测到的缓冲队列占空比达到或者超过预先设定的拥塞预测因子λ时，即判断该节点有拥塞发生的趋势，从该节点开始向网络广播拥塞趋势信息，这个信息以广播帧的形式发送，这个帧包括该节点的网络地址和有拥塞趋势发生的标志信息；

假定在建立起来的树状拓扑传感器网络中在时刻t在节点d检测到缓冲队列的占空比已经达到预先设定的拥塞预测因子λ，则从节点d向全网广播拥塞帧，假定当前从节点a到中心节点g的路由是激活路由，而从节点m到中心节点g的路由处于休眠状态，因此该广播帧只能沿着当前从节点a到中心节点g的激活路由传播，经过逐跳转发，从节点a到中心节点g的路由中包括的所有节点都知道了当前在节点d将要发生拥塞；

接下来，从节点a到中心节点g的激活路由中包括的所有节点（中心节点g除外）都检查节点d是否位于自己下一跳数据流将要流经的路径上，这个过程通过各个激活节点分别检查各自的路由表中对应的当前路由的下一跳网络节点的地址是否与节点d的网络地址相同来实现，如果中心节点g所要的数据已经传输到节点a、节点e或者f，则它们当前的路由的下一跳节点的网络地址与节点d的网络地址不相同，此时节点a、e或者f就不需要对当前的数据流进行分流或者降速。但是如果中心节点g所要的数据只传输到了节点b，如果节点b的数据是通过路径8来传输时，节点b就判断出当前路由的下一跳网络节点的地址与拥塞趋势信息中的节点地址相同，就根据路径8所在的网络覆盖层，来选取处于不同网络覆盖层的路径2进行数据传输；如果当前节点b是通过路径2来进行传输数据的，则判断出拥塞趋势信息中的节点地址与当前路由的下一跳网络节点的地址不同，就无需进行层间分流和层内降速处理。同样地，如果中心节点所要的数据传输到了节点c，在节点c通过路径9进行传输数据时，无需进行分流和降速处理；在节点c通过路径3进行传输数据时，则选取与路径3位于不同网络覆盖层的路径9进行传输数据，在路径9不可用的情况下，再采用层内等分降速处理。

我们对不同网络覆盖层之间的分流和同一网络覆盖层内的降速两种方法分别赋以不同的响应优先级，首先检查当前数据流将要流经的下一跳多条位于不同的网络覆盖层的路径中是否有空闲的激活路径可以越过将要发生拥塞的节点d，这个过程通过检查当前数据流所处的节点的路由表中存储的多条路由的下一跳网络节点的地址来实现，如果检查到有不包含网络节点d的下一跳网络节点地址存在，就从这样的路径分流传输的数据流；如果没有，再采取在同一网络覆盖层内降速的方法，这里的同一网络覆盖层是指保持下一跳路径所在的网络覆盖层不变，不用将下一跳传输路径切换到其他的网络覆盖层，假设当前的数据流位于节点b，当前路由的下一跳网络节点的地址是d，即当前路由包括的下一跳路径是图1中所示的路径8，当节点b接收到来自节点d的拥塞广播帧后，通过检查自己的路由表中的当前路由的下一跳路径的网络地址，知道具有拥塞趋势的节点d位于下一跳将要经过的路径8上，然后检查其他路由包括的下一跳网络地址是否有不包括节点d的网络地址存在，由于下一跳路径2对应的网络节点地址是c而不是d，因此选择路径2对当前的数据流进行分流。如果当前的数据流位于节点c，则采用相同的方法用路径9对当前的数据流进行分流；如果经过节点c的路径9由于某种原因失效而无法得到利用，这时只能继续利用原来的路径3来传输数据，这样就要考虑采用在原来网络覆盖层内的路径来降低将要传输的数据流的流速的方法，设降速前的数据传输速率是R个bit/s，将[0,R]这个速率区间平均划分成M等分，每次调节都将速率降低个bit/s，即第一次降速后传输速率降为个bit/s,第二次降速后传输速率降为个bit/s，…，以此类推，在节点c将原始数据流第一次降速后，数据流沿着路径3向节点d传送，同时节点c继续监听是否还有来自节点d的拥塞帧继续广播，如果没有了，降速调节就结束，如果还能继续接收到来自节点d的拥塞广播帧，则对数据流做第二次降速，然后再监听是否还有来自节点d的拥塞广播帧，…，如此反复，直到监听不到来自节点d的拥塞广播帧为止。

如图2所示，给出了本发明实施例的程序流程图，其包括的步骤如下：

（1）首先进行多层覆盖的树状拓扑结构无线传感器网络的布设和建立，为实施缓解网络拥塞发生控制方法奠定基础；

（2）然后，网络中的每个节点均进行是否有拥塞趋势发生的判断，如果没有，就结束拥塞趋势的判断；如果判断出有拥塞发生的趋势，则该具有拥塞趋势的节点向周围广播拥塞趋势信息；

（3）网络中处于激活状态的节点接收到拥塞趋势信息后，首先对具有拥塞趋势的节点是否处于数据流将要流经的下一跳路径上进行判断，如果不在，则无需进行处理；如果在数据将要流经的下一跳路径上，则执行步骤（4）；

（4）根据在其他的网络覆盖层是否有空闲的备选路径可以利用来判断能否通过层间分流的方法绕过具有拥塞趋势的节点进行数据传输；如果能进行层间分流，就优先采用层间分流的方法避开拥塞趋势节点，结束程序；如果不能进行层间分流，转为执行步骤（5）；

（5）对目前的数据传输速率进行等量降速，每次降速后均监听是否还有拥塞趋势信息继续广播，如果有，继续等量降速，直至监听不到拥塞趋势广播信息为止。