摘要
针对无线网络中寻找从源点s到汇点t的两条非干扰不相交路径这一NP难问题,提出了一种拟人算法。该算法首先基于网络流方法得到两条点不相交的s-t路径,然后通过一种拟人化的策略逐步调整这两条路径,力图使得它们变为两条非干扰不相交的s-t路径。模拟实验表明,与现有的算法相比,拟人算法可以快速地以更高的概率找到两条长度较短的非干扰不相交路径。
For the NP-hard problem of finding two non-interfering disjoint paths between two nodes s and t in a wireless network, a quasi-human algorithm was proposed. Starting with two node-disjoint paths from node s to node t obtained by using the flow technique, this algorithm tries to change these two paths into two non-interfering disjoint paths from s to t by adjusting them gradually through a quasi-human strategy. Experimental results show that compared with the existing algorithms,the quasi-humart algorithm can quickly find two shorter non-interfering disjoint paths from s to t with a higher probability.
出处
《计算机科学》
CSCD
北大核心
2014年第8期70-74,共5页
Computer Science
基金
国家自然科学基金(61370003)
教育部留学回国人员科研启动基金资助
关键词
无线网络
不相交路径
非干扰不相交路径
NP难度
拟人算法
Wireless networks, Disjoint paths, Non-interfering disjoint paths, NP-hard, Quasi-human algorithm
