基于路由关联度的多径路由方法

具体实施方式

现在参考附图描述本发明的实施例，附图中类似的元件标号代表类似的元件。

本实施例基于关联度的多径路由方法能在不明显增加多径路由协议路由开销的条件下，准确地计算出多径路由两两之间的关联度，并根据关联度分配数据分组到多径路由中，避免关联度大的多条路由同时发送数据分组。在阐述本实施例基于关联度的多径路由方法之前，先说明本方法中涉及的几个概念：

累积路径(Path Accumlation)：为RREQ在路由发现过程中用来记录当前RREQ经过的路由节点的列表。当RREQ消息到达目的节点时，累积路径字段记录了源节点到目的节点的完整路由。

活动邻居节点：为当前节点的所有邻居节点中属于某一条活动路由的邻居节点的集合。

路由i中节点n相对于路由j的关联度：为路由i中节点n的活动邻居节点中属于路由j的数目。

路由i相对于路由j的关联度η_ij：为路由i中所有节点相对于路由j的关联度的总和。

现详细说明本实施例基于关联度的多径路由方法。参考图1至图4d，本方法包括如下步骤：

步骤S1，当源节点S需要发送数据到目的节点D并且没有到达目的节点的路由时，如图3a，源节点S发送RREQ消息，发起路由寻找过程，所述RREQ消息包含累积路径字段和一跳邻居列表，其中累积路径字段为源节点S的地址，一跳邻居为空；

步骤S2，判断目的节点D是否收到RREQ消息，如果否，继续下一步，如果是，转步骤S9；

步骤S3，中间节点收到RREQ消息后，根据RREQ消息的一跳邻居列表计算自身的一跳邻居(为与该节点直接通信的其他节点，例如中间节点a收到RREQ消息后，见图3a，节点a计算其一跳邻居为源节点S)集合和两跳邻居(为与该节点通过另一个节点间接通信的其他节点，节点a计算其二跳邻居为空)集合(可以选择一跳邻居集合和两跳邻居集合的并集或者仅选择一跳邻居集合为节点的活动邻居节点集合，中间节点将根据此活动邻居节点集合和RREP消息的旧路由计算旧路由与新路由的关联度)，计算RREQ消息中累积路径字段的跳数，判断所述RREQ消息是否为重复的RREQ消息，如果是，继续下一步，如果否，转步骤S5；

步骤S4，中间节点判断RREQ消息的累积路径字段的跳数是否小于节点的最短反向路由跳数(如图2b中，节点a的最短反向路由为S-a，累计路径为S，其跳数1，S-c-a为节点a的一条路由路径，其累计路径为S-c，其跳数为2，所以节点a的累计路径的跳数大于节点的最短反向路由跳数)如果是，继续下一步，如果否，转步骤S7；

步骤S5，中间节点将节点的最短反向路由跳数更新为所述累积路径字段的跳数(后续接收到重复的跳数更大的RREQ分组会被丢弃，以降低RREQ消息广播导致的路由开销，并且发现路由长度更短的新路由)；

步骤S6，中间节点判断是否存在路由环路，如果是，继续下一步，如果否，转步骤S8；

步骤S7，中间节点丢弃该RREQ消息，结束；

步骤S8，中间节点将自身的地址添加到所述RREQ消息的累积路径字段中(此时，见图3b，RREQ消息的累积路径由S变为S-a)，将所述RREQ消息的一跳邻居列表替换为自身的一跳邻居列表(此时，见图3b，RREQ消息的一跳邻居由空变为S)从而对所述RREQ消息进行更新，然后广播更新的RREQ消息(只有当RREQ消息的累积路径跳数小时，才会更新最短反向路由跳数，并继续广播RREQ消息，目的是为了降低RREQ消息广播导致的路由开销)，转步骤S2；

步骤S9，目的节点D收到RREQ消息后，根据RREQ消息的一跳邻居列表计算自身的一跳邻居集合({f，g，h})和两跳邻居集合({d，c，e})(与步骤S3相同)，将RREQ消息的累积路径(S-a-d-g-D)作为新路由，根据该新路由和已经建立的路由(即旧路由，源节点S发起RREQ消息时，如图2b建立3条路由，其中S-c-f-D，S-b-e-h-D为旧路由)判断所述新路由是否为新的节点不相关路由，如果否，继续下一步，如果是，转步骤S11；

步骤S10，目的节点D丢弃该RREQ消息，结束；

步骤S11，目的节点D广播Hello消息(TTL(Time to Live)＝1，发送RREP消息之前发送Hello消息可以帮助新路由的上游节点更准确地计算活动邻居节点及集合，从而更加准确的计算路由的关联度)，所述Hello消息包含所述目的节点的一跳邻居节点列表，同时，目的节点D单播RREP消息，所述RREP消息携带新路由的完整路径(如图2b，路由S-a-d-g-D)和旧路由的完整路径(如图2b，路由S-c-f-D、路由S-b-e-h-D)(本发明最多发现三条节点不相关路由)；

步骤S12，判断源节点S是否收到Hello消息和RREP消息，如果否，继续下一步，如果是，转步骤S15；

步骤S13，中间节点收到Hello消息和RREP消息后，根据Hello消息的一跳邻居列表计算自身的一跳邻居集合和两跳邻居集合(与步骤S3相同)，根据RREP消息中旧路由的完整路径(如图2b中，S-c-F-D，S-b-e-h-D)和新路由中间节点的活动邻居节点(如果仅选择一跳邻居为活动邻居，则图2b中节点g的活动邻居节点为节点d，节点f，节点D)计算中间节点与每条旧路由的关联度η_j(n)(中间节点g与路由S-c-F-D的关联度为1，与路由S-b-e-h-D的关联度为0)，并且将该中间节点与每条旧路由的关联度η_j(n)累加到该新路由与每条旧路由的关联度中(该新路由与每条旧路由的关联度的初始值为0)，在所述RREP消息中添加累加关联度字段以更新所述RREP消息，所述累加关联度字段包含该新路由与每条旧路由的关联度信息；

步骤S14，中间节点根据新路由建立前向路由和反向路由(见图2a，节点d到目的节点D的前向路由下一跳为g，节点d到源节点S的反向路由下一跳为a)，中间节点首先广播一条Hello消息，然后单播更新的RREP消息，转步骤S12；

步骤S15，源节点S接收到Hello消息和RREP消息后，根据RREP消息中的累加关联度字段确定新路由与每条旧路由的关联度(当RREP到达源节点时，关联度累加值就是该新路由与每条旧路由的关联度，如图2，新路由A为S-a-d-g-D，旧路由B为S-c-F-D，旧路由C为S-b-e-h-D，可以确定路由B与路由A和路由C的关联度为都为6，路由A与路由C的关联度为2，考虑源节点和目的节点，最小关联度为2)；

步骤S16，源节点S根据多径路由中每条路由的路径长度和对应路由与其他路由的关联度利用下列公式计算每条路由的相关因子(步骤S15中路由A的相关因子γ_B＝(6+6)×3＝36)，根据计算的相关因子计算每条路由的权值，根据权值大小分配分组数据到对应的路由中，以实现负载平衡(即使路由B的跳数最小，由于路由B与路由A和路由C的关联度大，γ_B也比γ_A和γ_C大，计算得到的路由权值W_B反而小，因此分配到路由B的数据分组比例小，减少了与路由A和路由C竞争共享无线信道的概率，从而达到改善多径路由方法的负载平衡能力)，结束。

路由的相关因子定义为：

${\gamma }_i=\underset{j}{\overset{j\ne i}{\Sigma }}{\eta }_{\mathrm{ij}}\times L_i$

其中，i为路由，γ_i为路由i的相关因子，η_ij为路由i相对于节点独立路由j的关联度，L_j为路由i的路径长度。

路由的权值定义为：

$W_i=\mathrm{Min}\left(\right[\frac{\underset{i}{\Sigma }{\gamma }_i}{{\gamma }_i}],U)\times R$

其中，i为路由，W_i为路由i的权值，U为常量，用来确保W_i不至于太大，R为切换因子，用来控制发送在多条路径之间的数据分组切换的频率，为源、目的节点之间多径路由的相关因子之和(如步骤15中，三条路由相关因子的和为24+24+36＝84)。

其中，步骤S1至步骤S8为基于RREQ消息的活动邻居发现过程(如图3a-3d)；步骤S13为RREP触发的基于Hello消息的活动邻居发现过程(图4a-4d)。

由上可知，本实施例基于路由关联度的多径路由方法中，源节点发现节点不相关多径路由时，需要计算多径路由两两之间的关联度，然后在节点独立的多条路由上依据多径路由两两之间的关联度和路由长度计算多径路由发送数据分组的权值，有效地避免关联度大的多条路由同时发送数据分组，尽量选择关联度小的多条路由发送数据分组，从而尽量减少多条路由发送数据分组之间竞争无线信道，从而达到改善数据分组端到端延时和降低数据分组局部拥塞的可能，最终达到改善网络数据分组发送的性能。

以上结合最佳实施例对本发明进行了描述，但本发明并不局限于以上揭示的实施例，而应当涵盖各种根据本发明的本质进行的修改、等效组合。