采用启发式算法的无线自组网网络编码方法  

Network Coding Method Using Heuristic Algorithms for Wireless Ad Hoc Networks

作　　者：焦贤龙[1] 王晓东[1] 周兴铭[1] 

机构地区：[1]国防科学技术大学计算机学院并行与分布处理国家重点实验室,湖南长沙410073

出　　处：《软件学报》2010年第11期2892-2905,共14页Journal of Software

基　　金：国家重点基础研究发展计划(973)No.2006CB303000~~

摘　　要：首先证明了与应用网络编码相关的最优化问题是NP完全的,然后提出了一种采用启发式算法的网络编码方法COMP.该网络编码方法利用贪婪集合配置启发式算法和贪婪集合覆盖启发式算法的基本思想来尽可能多地挖掘网络编码机会.NS-2仿真结果表明,该网络编码方法在应用到节点数比较多、最大传输范围比较小以及会话数比较多的场景中时,有效地减轻了并发会话的影响,提高了现有广播算法的性能,而且其性能提高超过了现有的网络编码方法.This paper first proves that the optimizing problems concerning network coding are NP-complete,and then puts forward a network coding method called COMP,using heuristic algorithms.This network coding method adopts the basic ideas of the set packing heuristic algorithm and the set cover heuristic algorithm with the aim of digging up as many network coding opportunities as many as possible.The results of the simulation carried out by the NS-2 simulator show that in scenarios where there are a large number of nodes,a small maximum transmission range,and a large number of sessions,this network coding method effectively alleviates the impact of session concurrency,improves the performance of the existing broadcast algorithm,and its performance improvement is greater than that of the existing network coding method.

关 键 词：无线自组网 网络编码 贪婪集合配置 贪婪集合覆盖 广播 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]