一种基于蚂蚁算法的自组织QoS路由方法

摘要

本发明涉及一种基于蚂蚁算法的自组织QoS路由方法，该方法按如下步骤：A、接收到邻居路由器发送的数据报文；B、根据数据报文的目的地址判断报文类型是否为单播报文；C、进入单播QoS路由方法；D、初始化路由器寄存器；E、考查路径评价值Jpath，找到符合用户请求的路径；F、转到步骤K；G、进入组播QoS路由方法；H、初始化路由器寄存器，构建组播树；I、组播树费用分摊；J、计算组播树评价值JT，找出当前可行组播树；K、根据计算出的当前可行组播树将数据报文转发到下一跳路由器。本发明的优点为可以有效的基于QoS请求对数据进行路由和转发，提高路由成功率，比传统网络模型优越性大，该设计的路由方法具有良好的性能和实用性。

主权项

1.一种基于蚂蚁算法的自组织QoS路由方法，按如下步骤：步骤A：接收到邻居路由器发送的数据报文；步骤B：根据数据报文的目的地址是否为单播地址判断报文类型是否为单播报文；其特征在于：根据步骤B是单播报文，则执行步骤C，否则执行步骤G；步骤C：进入单播建模QoS路由方法；步骤D：初始化路由器寄存器，发送前向蚂蚁agent寻路，调用蚂蚁算法，其中agent负责收集记录当前网络状态信息；步骤E：考查路径评价值J_path，找到符合用户请求的路径；步骤F：转到步骤K；步骤G：进入组播建模QoS路由方法，给定组播请求：R(v_s，v_d，Δ_bw^d，Δ_dl^d，Δ_jl^d，Δ_ls^d，p^d)，为其构造一棵组播树，其中v_s代表源节点，v_d代表目的节点，Δ_bw^d代表带宽需求约束区间，Δ_dl^d代表延迟需求约束区间，Δ_jt^d代表延迟抖动需求约束区间，Δ_ls^d代表出错率需求区间，p^d代表用户愿付费用上限；步骤H：初始化路由器寄存器，构建组播树；步骤I：组播树费用分摊；在形成组播树以后，由于所选边是选用用户共用的，所以资费也理所应当由选用用户共同分担，分摊的原则是：用户独自占用该条路径所需付的费用越高则用户在组播树付费中分摊的部分越大；设定源节点到每一个组成员的路径所需付费的集合为：W_p＝{pay₁，Pay₂，...，pay_n-1,pay_n}式中pay_n为每一个组成员的路径所需付费，n＝1，2，…，N，N属于自然数，则第i个组成员v_i所需分摊的组播树费用比例为：${\mathrm{per}}_d=\frac{{\mathrm{pay}}_i}{\underset{k\in \{\mathrm{1,2},...n\}}{\Sigma }{\mathrm{pay}}_k}$式中i，k∈{1，2，...n}；步骤J：计算组播树评价值J_T找出当前可行组播树；步骤K：根据计算出的当前可行组播树将数据报文转发到下一跳路由器；所述的步骤D中调用蚂蚁算法包括：步骤D1：初始化路由器寄存器，设置最多迭代次数TIN，已迭代次数IN＝0，初始化每次迭代发送的蚂蚁agent数量AN，已发送的agent数an＝0，路径评价值J_path＝∞，可行路径为空；步骤D2：IN←IN+1，源节点以间隔Δ_t发送AN个前向蚂蚁agent寻路，每发送一个agent就an←an+1，初始化每一个前向agent，其中：蚂蚁agent序号seq＝an；步骤D3：前向agent记录路径，将经历过的节点保存起来，同时记录有关的网络状态信息，前向蚂蚁agent在源节点被发出后，在网络中的每一个经过的节点按下面步骤执行行为；步骤D31：判断当前蚂蚁agent跳数是否超限，如果是，则蚂蚁agent死亡；步骤D32：如果当前节点的直接下一跳节点有本次路由目的节点，则考察与该节点之间的边是否满足用户请求约束，如满足，则蚂蚁agent跳转到目的节点，转到步骤D35；步骤D33：在当前节点实现小世界边；步骤D34：在当前节点进行下一跳选择；步骤D341：在当前节点，将路由总次数计数器增加1；步骤D342：实现小世界行为；步骤D343：如果下一跳选择成功返回，则蚂蚁agent前行至该节点；步骤D344：如果下一跳选择失败，蚂蚁agent死亡；步骤D35：前向蚂蚁agent任务完成；步骤D4：当前向agent到达目的节点时，触发产生一个继承前向agent相关信息的后向agent，后向agent沿着原路径的信息，从目的节点反向到达源节点，同时更新路由表中的信息；步骤D41：在目的节点，根据前向蚂蚁agent信息，根据公式计算路径评价值J_p，式中UU_p为路径或组播树上的用户效用，UN_p则为网络提供商效用，并赋予生成的后向agent；其中α_up，α_np是对用户的倾斜权值，0＜α_up，α_np＜1，α_up+α_np＝1，将前向蚂蚁agent找到的路径赋予后向蚂蚁agent；步骤D42：后向agent按保存的路径信息，反向跳到上游节点，然后更新信息素表；在当前节点，蚂蚁将路由成功次数计数器增加1，如果蚂蚁agent在当前节点引入了小世界边，则更新小世界边表；步骤D43：判断后向蚂蚁agent是否到达源节点，如果未到达，则跳转至步骤D42；步骤D44：将后向蚂蚁agent携带路径的评价值和当前路径评价值进行比较，如果agent携带路径的评价值小于当前路径评价值，则将新路径保存为当前可行路径；步骤D45：后向agent任务完成，调用蚂蚁算法结束；所述的步骤H初始化路由器寄存器，构建组播树包括：步骤H1：初始化路由器寄存器，设置迭代次数CN，已迭代次数cn＝0，组播树评价值J_tree＝∞，当前可行组播树为空；步骤H2：将所有组成员按带宽请求由大到小排列，设定待处理组成员集合W＝{v₁，v₂，...，v_n-1，v_n}，v_n为待处理组成员，n＝1，2，…，N，N属于自然数，已处理组成员集合A＝Φ，可行路径集合P＝Φ，其中Φ为空集合；步骤H3：取v_d∈W，利用所述的单播建模QoS路由方法，由v_s向v_d寻找一条满足成员v_d请求约束的可行路径P_d，如果未找到，则此次构建组播树失败，跳转到步骤J3；步骤H4：将节点v_d从W删除，并加入A；步骤H5：检查可行路径P_d是否含有位于W中的组成员，如果没有，则跳转到步骤H7；步骤H6：如果P_d上含有位于W中的组成员，判断这些组成员的请求约束能否在P_d得到满足，将能被满足的节点从W删除，并加入A；步骤H7：将可行路径P_d加入集合P；步骤H8：若集合W不为空，则跳转到步骤H1；步骤H9：将可行路径中P中的路径拼成一棵组播树，在成树的过程中，每个组成员的请求约束都要被满足，并且不能出现环，否则，此次构建组播树失败，跳转至步骤J3；所述的步骤J计算组播树评价值J_T，找出当前可行组播树包括：步骤J1：根据公式计算组播树评价值J_T；步骤J2：如果J_T＜J_tree，J_tree为当前可行组播树的评价值，则用计算得到的组播树代替当前可行组播树，J_tree＝J_T；步骤J 3：cn←cn+1，若cn＜CN，跳转到步骤H；步骤J4：判断J_tree＜∞是否成立，如果成立，则算法成功，否则算法失败。