无线网络中寻找非干扰不相交路径的拟人算法  

Quasi-human Algorithm for Finding Non-interfering Disjoint Paths in Wireless Networks

作　　者：董高秀 凌珊[1] 陈卫东[1] 

机构地区：[1]华南师范大学计算机学院,广州510631

出　　处：《计算机科学》2014年第8期70-74,共5页Computer Science

基　　金：国家自然科学基金(61370003);教育部留学回国人员科研启动基金资助

摘　　要：针对无线网络中寻找从源点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.

关 键 词：无线网络 不相交路径 非干扰不相交路径 NP难度 拟人算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]