无线自组织网络中基于节点的度的路由搜寻和维护方法

摘要

无线自组织网络中基于节点的度的路由搜寻和维护方法属于无线通信网络技术，其特征在于：它从节点的度的统计特性出发，提出了一种考虑了节点竞争和拥塞状况的选路准则，以便使节点选择那些流经节点时竞争节点少的路由作为数据包的传送路由，从而在不增加网络开销的前提下，在相同的节点移动速率时数据包具有更高的投递率，更短的延时。在具体采用何种路由选择参数时，要考虑上层业务特性的要求。此外，它还可以很容易地嵌入至现有的路由算法中。采用本发明提出的选路准则的路由方法具有简单、高效、节点能量消耗公平的优点。

主权项

1、无线自组织网络中基于节点的度的路由搜寻和维护方法，其特征在于，它是在无线收发设备，即节点，也称路由器，构成的无线自组织，即Ad Hoc，通信网络内各移动设备中依次按以下步骤实现的：初始化设定：数据包的类型及其内含的数据项，并存入各节点存贮器中：1)路由请求数据包，即RREQ，内含以下数据项：数据包类型，用“Type”表示；源节点地址，用“Src_Addr”表示；目的节点地址，用“Dest_Addr”表示；节点发送的RREQ数据包的序号，用“Seq_Num”表示；用跳数表示的数据包的寿命，用“TTL”表示，根据网络规模预设最大寿命为MaxM+1，其中MaxM是一条路由中可能包含的最多的中间节点数目；从源节点到当前节点的路由长度，用“Cur_Len”表示；源节点的N跳度用“Src_Degree”表示，N跳度是指N倍于节点的发射和接收半径的范围内的节点数，在实际中，由于节点无法获知静止节点，即不活动节点，的存在，因此它也等同于上述范围内的活动节点数，即有数据包需要发送的节点的数目，一般N选择1或2；目的节点的N跳度，用“Dest_Degree”表示，其中，N跳度的定义如上所述；RREQ流经的中间节点的节点地址，用“Addr_1～Addr_MaxM”表示，其中MaxM表示一条路由中可能的最多的中间节点数目；RREQ流经的各种中间节点的N跳度，用“Degree_1～Degree_MaxM”表示，同样，MaxM表示一条路由中可能的最多的中间节点数目；2)路由应答数据包，即RREP，内含以下数据项：Type、Src_Addr、Dest_Addr、Seq_Num、Cur_Len、Src_Degree、Dest_Degree、Addr_1～Addr_X以及Degree_1～Degree_X，其中由Addr_1～Addr_X来构成一条完整的路由，Degree_1～Degree_X表示对应于Addr_1～Addr_X的节点的N跳度信息，其余各数据项的定义如前所述，其中X表示RREP中包含的路由的中间节点数目为X，X不大于MaxM；3)路由失败数据包，即RERR，内含以下数据项：Type、Src_Addr、Dest_Addr、Cur_Len、Src_Degree、Dest_Degree、Addr_1～Addr_X、Degree_1～Degree_X、Error_Up_Addr以及Error_Down_Addr，其中Type、Src_Addr、Dest_Addr、Src_Degree、Dest_Degree、Addr_1～Addr_X及Degree_1～Degree_X的含义如前所述，而Cur_Len表示从发生错误的节点到目前节点的跳数；Error_Up_Addr表示发现下一跳节点无法到达的节点地址；Error_Down_Addr表示无法到达的下一跳节点的节点地址；4)业务数据包内含以下数据项：Type、Src_Addr、Dest_Addr、Cur_Len、Src_Degree、Dest_Degree、Addr_1～Addr_X、Degree_1～Degree_X、Traffic_Data以及Alpha，其中Type、Src_Addr、Dest_Addr、Cur_Len、Src_Degree、Dest_Degree、Addr_1～Addr_X、Degree_1～Degree_X的含义如前所述，Traffic_Data表示业务数据包的上层业务数据；Alpha表示用户对于业务数据包的延时、丢包率、带宽的要求参量；设定以下参数及其有关的中间变量，分别存入个节点中的存贮器内：路径寿命的超时时间阈值，它表示：若在这段时间内，节点没有监测到任何沿该路径的业务流数据包，则节点认为该路径已经失效，从而将该路径，即路由，从路由缓冲区中删除；路由缓冲区，它指各节点的存贮器中保存路由的存贮空间；数据包缓冲区，它指各节点的存贮器中保存上层业务数据包的存贮空间；网络预先设定的业务数据包的最大允许发送次数；网络预先设定的一条路由中含有的最大允许节点数；设计计算一条路由的路由选择参数RSM的下述三种算法程序，计算三种路由参数RSM1，RSM2及RSM3，把它连同路由选择准则的计算程序一起存入各节点的存贮器中，所述的路由选择准则是指：当α值取值较小时，RSM值取RSM3，在路由缓冲区中选择一跳具有最小的RSM3值的到达目的节点的路由；当α取值较大时，RSM值从RSM1或RSM2中选取一个，一般保险起见，取RSM1，在路由缓冲区中选择一条具有最小的RSM1值的到达目的节点的路由；所述的RSM1、RSM2及RSM3的计算方法如下：${\mathrm{RSM}}_1=\underset{i=1}{\overset{M}{\Sigma }}{D}_i,$ ${\mathrm{RSM}}_2=(H+1)\sqrt{\frac{1}{M-1}\underset{i=1}{\overset{M}{\Sigma }}{(D_i-\bar{D})}^2},$ 其中$\bar{D}=\frac{1}{M}\underset{i=}{\overset{M}{\Sigma }}{D}_i,$ ${\mathrm{RSM}}_3=(H+1)[\frac{1}{M}\underset{i=1}{\overset{M}{\Sigma }}{D}_i+\alpha \sqrt{\frac{1}{M-1}\underset{i=1}{\overset{M}{\Sigma }}{(D_i-\bar{D})}^2}],(0<\alpha <1)$ 其中，M为一条路由中包含的节点数；H为一条路由中包含的跳数，H＝M+1；Di为路由流经的第i个节点的N跳度；D为路由流经的M个节点的平均N跳度；α是用户在业务数据包中指定的，它是用户根据数据包的延时、丢包率、带宽而设定的一个参量，同时，该参量表明了上层业务特性对路由的总竞争节点数和各节点的竞争节点数的标准方差的侧重程度，0＜α＜1，当对标准方差侧重程度较小时，α取值要小些，反之，则α值较大；所述的路由搜寻方法依次含有以下各步骤：(1)当某节点产生一个上层业务数据包时，该节点便成为源节点，它首先判断是否有数据包正在发送，若有，则将该业务数据包插入数据包缓冲区中，等待该数据包发送完毕后再发送当前数据包；若没有数据包正在发送，则它根据上述RSM选路准则从自己的路由缓冲区中选择一条到达目的节点的有效路由；(2)若该节点的路由缓冲区中不存在从该节点出发的有效路由，便发起路由搜寻过程，即该节点把自身地址和N跳度填充入RREQ中并广播发送；若存在，便转入路由维护过程；(3)中间节点在收到RREQ后，便检查是否首次接收到本RREQ，若为非首次接收到，便丢弃本RREQ，搜寻过程结束；若为首次收到本RREQ，中间节点便把自身地址和N跳度填充入RREQ中并转发；(4)目的节点收到RREQ后，根据存贮器中预先确定的选路准则和路由缓冲区的各条路径的各个RSM值，选择最佳路由，所选的各条路径也包括目的节点从RREQ中提取相应的节点地址和N跳度来形成的一条到达源节点的路径；(5)目的节点把包括各节点地址和N跳度在内的最佳路由信息填充入RREP中并向源节点发送；(6)最佳路由的中间节点接收到RREP后，便根据自己节点的N跳度去更新RREP中与自己对应的节点的N跳度信息，并转发至RREP中所包含路由的上行节点；(7)源节点接收到RREP后，便获得一条从源节点到目的节点的有效路由，并存入自己的路由缓冲器中，路由搜寻过程结束；所述的路由维护方法依次含有以下各步骤：(1)源节点可以根据上述步骤(7)得到的一条从源节点到目的节点的有效路由，也可以根据上述步骤(2)中在上层业务数据包产生后直接从路由缓冲区中得到的有效路由，把节点地址和相应的N跳度信息填充入当前要发送的业务数据包中，并把该业务数据包发送出去；(2)源节点若发现其下行链路无法正常通信，即下一跳节点无法到达，便更新路由缓冲区中的路由信息，并计数当前业务数据包的发送次数，转步骤(11)；源节点若发现其下行链路可以正常通信，则步骤(3)；(3)中间节点根据自己节点的N跳度去更新业务数据包中与自己对应的节点的N跳度信息，并根据业务数据包中的路由信息转发该业务数据包；(4)中间节点若发现其下行链路无法维持正常通信，即下一跳节点无法到达，便更新自己节点的路由信息，并使本业务数据包的发送次数加1，然后转步骤(5)；若所有中间节点均可以维持正常通信，则目的节点可以接收到业务数据包，路由维护过程结束；(5)中间节点检查当前业务数据包的重发次数是否达到网络预先设置的发送次数，若达到，则丢弃该数据包，然后向源节点发送路由失败数据包，即RERR，转步骤(7)；若没有达到，则判断路由缓冲区中是否存在其他有效路由；(6)若路由缓冲区中存在其他有效路由，则沿新路由发送当前业务数据包，路由维护过程结束；若不存在，则丢弃当前业务数据包，然后向源节点发送RERR；(7)接收到RERR的中间节点，更新本地路由缓冲区中相应的路由信息，并用本地节点的N跳度信息更新RERR中相应的N跳度信息，然后把RERR转发至该RERR中包含路由的上行节点；(8)源节点接收到RERR后，更新本地路由缓冲区中的路由信息；(9)源节点检查数据缓冲区中是否仍有业务数据包等待发送，若有，则检查路由缓冲区中是否存在其他有效路由，转步骤(10)；若数据缓冲区中没有业务数据包等待发送，则路由维护过程结束；(10)若源节点发现路由缓冲区中没有有效路由，则重新发起路由搜寻过程，路由维护结束；若发现路由缓冲区中存在有效路由，则业务数据包沿新路由发送，路由维护过程结束；(11)源节点判断当前业务数据包的发送次数是否达到网络预定的发送次数，若达到，则丢弃该数据包，转步骤(9)；若没有达到，则判断路由缓冲区中是否存在其他有效路由，转步骤(10)。