一种改进的分布式最大权独立集算法
王向阳 张源*
东南大学移动通信国家重点实验室 南京 210096
An Improved Distributed Algorithm for Maximum Weight Independent Set (MWIS) Problem
Wang Xiang-yang Zhang Yuan
National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China
摘要 能快速准确寻找给定图中的最大权独立集的分布式算法，对于解决无线网络中的资源调配、无线骨干网构建等问题具有非常重要的指导意义。该文以基于最大乘信用传播的分布式算法为框架，假设所有节点了解自己邻居节点之间的局部拓扑信息，启发式地提出一种新的相邻节点间交换消息的计算方法以及相应的分布式最大权独立集算法。仿真结果表明，所提算法摆脱了文献中已有算法对图结构必须是树或者二分图的要求，且权和性能优于已有的分布式算法。
关键词 ：
无线网络 ,
分布式算法 ,
最大权独立集
Abstract ：Distributed algorithms which can find the Maximum Weight Independent Set (MWIS) of graphs are very important for the design of wireless networks. Based on the max-product belief propagation framework, a new distributed MWIS algorithm is proposed. In this algorithm, each node is assumed knowing the local connection information among its neighbors. Helped by this local information, the proposed algorithm outperforms existing algorithms which requirs that the graph must be tree or bipartite, which is verified by simulation results.
Key words ：
Wireless networks
Distributed algorithm
Maximum Weight Independent Set (MWIS)
收稿日期: 2011-07-18
基金资助: 国家自然科学基金(61001103)和江苏省自然科学基金(BK2011019)资助课题
通讯作者:
张源
E-mail: y.zhang@seu.edu.cn
[1]
马彬,张文静,谢显中. 面向终端个性化服务的模糊垂直切换算法
[2]
俞鹤伟,梁根,秦勇. 异构无线网络多链路接入动态资源分配算法
[3]
王练, 梁申虎,彭代渊. 多源多中继无线网络中基于随机线性网络编码的调度方案
[4]
郑飞,李文璟,喻鹏,丰雷,孟洛明. 基于Benders分解的无线网络协作节能机制
[5]
杨静,赵妍妍,王汝言,龚玲玲, 谢毅,谢金凤. 带有黑洞节点探测的间断连接无线网络数据转发机制
[6]
郁滨,黄美根,黄一才,孔志印. ZigBee网络抵御Sybil攻击的自适应链路指纹认证方案
[7]
吴大鹏,冯誉,王汝言,刘乔寿. 恶意节点容忍的间断连接无线网络消息转发策略
[8]
马彬, 谢显中, 廖晓峰. 车辆异构网络中预测垂直切换算法
[9]
吴大鹏, 白娜, 王汝言. 带有节点状态估计的间断连接无线网络缓存管理策略
[10]
丰雷, 李文璟, 邱雪松. 面向无线网络容量和覆盖优化的分组调度算法
[11]
金顺福, 代羽. 带有接入阈值和超时隙的认知无线网络频谱分配策略
[12]
朱艺华, 李丽, 池凯凯, 李燕君. 6LoWPAN中优化多路径路由吞吐率的数据包分片方案
[13]
费新伟, 王满喜, 白铂, 陈巍, 曹志刚. 认知无线网络中一种基于匹配和干扰量化的LTE-A上行资源共享机制
[14]
葛青, 白光伟, 沈航, 张芃. 无线网络面向视频传输优化的机会网络编码机制
[15]
栾红志, 李鸥. 一种高效的协作频谱感知架构
2012, Vol. 34 
