【摘要】 本发明公开了一种基于跨层设计的分布式认知无线电网络路由方法，属于认知无线网络技术领域，主要包括：根据节点感知得到的可用频谱信息建立着色多重图模型；调用跨层设计路由算法寻找源节点和目的节点之间的路由并同时选择邻居节点间的通信信道；更新着色多重图的拓扑以及节点的接口数。本发明将网络层的路由选择和MAC层的信道分配进行跨层设计，在较低的时间复杂度下，对路由跳数和邻跳干扰进行具体的优化。本发明适用于认知无线电网路以及下一代异构网络等应用场合。 【专利类型】发明授权 【申请人】北京科技大学 【申请人类型】学校 【申请人地址】100083 北京市海淀区学院路30号 【申请人地区】中国 【申请人城市】北京市 【申请人区县】海淀区 【申请号】CN200810241018.5 【申请日】2008-12-24 【申请年份】2008 【公开公告号】CN101437273B 【公开公告日】2010-10-27 【公开公告年份】2010 【授权公告号】CN101437273B 【授权公告日】2010-10-27 【授权公告年份】2010.0 【IPC分类号】H04W40/02; H04W40/16; H04B17/00; H04W24/02 【发明人】周贤伟; 王建萍; 刘涛; 林琳; 王超; 杨裕亮 【主权项内容】1.一种基于跨层设计的分布式认知无线电网络路由方法，其特征在于：方法分为着色多重图模型的建立、路由的跨层设计、着色多重图和节点接口数的更新三个步骤； (a)着色多重图模型的建立：给每个信道一个唯一的颜色标识，当两个节点彼此在对方的发射范围之内，当前又有公共的可用信道，则它们互为潜在的邻居节点，构造着色多重图是在每对潜在的邻居节点之间连边，并用它们的公共信道对应的颜色来对边着色，得到了反映网络拓扑和当前可用信道的着色多重图G＝(V，E)，其中V表示顶点集，对应于网络中的节点集，E表示边集，对应于网络中的链路集；定义权函数μ：E(G)→R+以及颜色标号函数k：E(G)→{Ch1，Ch2，…，ChN}，其中权函数是定义在图G的边集上的函数，值域为正实数集，权函数将图G上的每一条边对应于一个正实数，颜色标号函数也是定义在边集上的函数，值域为信道集，颜色标号函数将图G上的每一条边与一种颜色对应； (b)路由的跨层设计：在认知无线电网络中，用频谱的不确定性要将网络层和MAC层进行跨层设计，充分利用网络节点的无线电接口，在选择路由的同时，选择邻居节点间的通信信道；跨层设计路由要满足可行性和保证路径最短；另外还要局部优化路径上相邻链路之间的干扰，路径上相邻链路之间的干扰称为邻跳干扰，采用路径上最大连续同色边数对邻跳干扰进行量化；对邻跳干扰的局部优化，是指在选择下一跳节点时，在优化跳数的前提下，选择当前的最大连续同色边数最小的路径； 通过算法可以得到源节点s和目的节点t之间最短的可行路径p，同时局部优化p上的邻跳干扰，算法的具体步骤如下： Step1：对算法的参数进行初始化，用l(x)表示算法选择的从s到x的最短路径的跳数，则l(s)＝0，对G中除s之外的其它节点y，令l(y)＝∞，用E(x)和c(x)分别表示算法选择的从s到x的最短路径上的最后一条边和从s到x的最短路径上的连续同色边数，则对G中的任意节点x，在初始化阶段有 c(x)＝0，对G中的任意一条边e，将其权值赋为1，得到μ(e)＝1，初始化阶段 其中R是一个动态变化的节点集合，当确定了源节点s到某节点的最优路径，把该点加入到R中； Step2：对于所有在V(G)但不在R中的节点，选择一个节点v，使得该节点v对应的l(v)值最小，当有多于一个节点，根据下标的降序选择具有最小c(v)的第一个节点； Step3：令R＝R∪{v}，当节点v只有一个接口，则对于关联于v的但颜色标号不等于k(E(v))的边，将其权重变为∞； Step4：当t∈R，则算法结束，输出从s到t的反向最优路径：t→p(t)→p(p(t))→…→s，其中p(v)表示算法选择的从s到v的最短路径上节点v前面的邻居节点；否则，对任意在V(G)但不在R中的节点w，检查是否要将节点w前面的邻节点p(w)更新为v，记v与w之间权重为1的边分别为e1，e2，…，em； 当l(w)＜l(v)+1， 或者l(w)＝l(v)+1且k(E(p(w)))≠k(E(w))， 或者l(w)＝l(v)+1且k(E(p(w)))＝k(E(w))且c(p(w))＜c(v)， 则说明将p(w)更新为v既不能减小源节点s到节点w的跳数，也不能在跳数相同的情况下减小节点w前的连续同色边数，直接转Step2； 否则，当以上条件均不成立，则说明将p(w)更新为v或者能减小源节点s到节点w的跳数，或者是在跳数相同的情况下减小了节点w前的连续同色边数，则将w之前的节点更新 为v，得到p(w)＝v，同时更新l(w)＝l(v)+1，对于e1，e2，…，em，按照下标的降序检查这m条边，选择满足k(ei)≠k(E(v))的具有最小下标的ei，并将ei作为v与w之间的连边，得到E(w)＝ei，当m＝1且k(ei)＝k(E(v))，选择e1作为v与w之间的连边，得到E(w)＝e1，同时更新c(w)＝c(v)+1，转Step2； (c)着色多重图和节点接口数的更新：由于节点接口数的限制以及可用频谱的动态性，在可用频谱发生变化以及每个节点对的传输任务开始和结束时，着色多重图的拓扑以及节点接口数都要进行更新，具体的更新规则如下： (c1)节点接口数的更新规则： 对于所选的从s到t的最短的可行路径p，p上每个节点v的接口数减去v所关联的边的颜色数，对于v＝s和v＝t，v所关联的边的颜色数为1，则IN(v)＝IN(v)-1，其中IN(v)表示节点v的接口数；对于p上任意一个中间节点v，当v前后的边是同色边时，v所关联的边的颜色数为1，当v前后的边颜色不相同时，v所关联的边的颜色数为2，因此有 其中v1是p上v之后的邻居节点； 当s到t的路径p上的传输结束时，p上每个节点v的接口数要加上v所关联的边的颜色数，对于v＝s和v＝t，IN(v)＝IN(v)+1，对于p上任意一个中间节点v， 其中v1是p上v之后的邻居节点； (c2)着色多重图的更新规则： 用G1和G2表示当前图和更新后的图，p是算法选择的最短的可行路径，Ep表示p的边集，令E+和E-分别表示那些最新可用和最新不可用的边的集合；注意到E+和E-中的边被它的端点以及颜色所唯一确定，选定路径p后，G1应当按照下面的公式被更新为G2： G2＝G1+E+-E--Ep。 【当前权利人】北京科技大学 【当前专利权人地址】北京市海淀区学院路30号 【统一社会信用代码】121000004000022245 【家族被引证次数】27
