无线网络中一种简单的弱连通支配集构造策略

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (20): 81-84.

无线网络中一种简单的弱连通支配集构造策略

王康，禹继国

曲阜师范大学计算机科学学院，　山东日照 276826

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-07-11 发布日期:2011-07-11

Simple construction strategy for weakly connected dominating set in wireless networks

WANG Kang，YU Jiguo

Department of Computer Science，Qufu Normal University，Rizhao，Shandong 276826，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-07-11 Published:2011-07-11

摘要/Abstract

摘要： 通过构造边支配集，提出了求解无线网络中弱连通支配集的集中式构造算法，该算法的时间复杂度为O（|N|+|E|）。同时在保证支配集的支配性和弱连通性不变的情况下，给出了两种修剪策略，以减小所求弱连通支配集的规模。从理论上证明了本算法的正确性，并通过仿真验证了算法的有效性。与已有结果相比，该算法可以产生规模更小的弱连通支配集。

关键词: 无线网络, 弱连通支配集, 边支配集

Abstract:

This paper proposes a central construction algorithm of weakly connected dominating sets in wireless networks by constructing edge dominating sets，simultaneously gives two pruning strategies to reduce the size of the produced set.The time complexity of the algorithm is O（|N|+|E|）.It proves the correctness of the algorithm and shows the effectiveness of the algorithm.Compared to existed results，the algorithm proposed produces weakly dominating sets with smaller size.

Key words: wireless networks, weakly connected dominating set, edge dominating set

王康，禹继国. 无线网络中一种简单的弱连通支配集构造策略[J]. 计算机工程与应用, 2011, 47(20): 81-84.

WANG Kang，YU Jiguo. Simple construction strategy for weakly connected dominating set in wireless networks[J]. Computer Engineering and Applications, 2011, 47(20): 81-84.

[1]	王浩炎，王玉玫. 两类认知用户及信道聚合的认知无线网络研究[J]. 计算机工程与应用, 2020, 56(22): 100-108.
[2]	王亚铭，唐俊勇，雷聚超. 面向噪声丢包感知的无线网络拥塞算法[J]. 计算机工程与应用, 2020, 56(14): 93-97.
[3]	高鹏，胡晓东，李家兴，唐伦. 5G-C-RAN中最大化效用服务功能链部署算法[J]. 计算机工程与应用, 2019, 55(7): 108-114.
[4]	周林腾，刘明. 考虑内容异构5G无线网络云对边混合缓存策略[J]. 计算机工程与应用, 2019, 55(6): 94-100.
[5]	丁青锋，王丽姚. 高速场景下基于位置信息的切换优化算法[J]. 计算机工程与应用, 2019, 55(16): 64-69.
[6]	随楠楠1，王聪1，张冬梅1，周欣2，徐友云1，3. CMT-SC：异构无线环境下CMT丢包类型识别机制[J]. 计算机工程与应用, 2018, 54(3): 94-99.
[7]	郭静，王学成，袁春萍. MAC层速率控制机制研究综述[J]. 计算机工程与应用, 2017, 53(6): 7-13.
[8]	杨健1，赵杭生2，陈曦3. 认知无线网络中频谱预测的协作策略设计[J]. 计算机工程与应用, 2017, 53(15): 111-116.
[9]	杜奕航，王可人，齐全. 动态主用户流量模型的跨层优化设计[J]. 计算机工程与应用, 2017, 53(13): 113-118.
[10]	汪淑娟，闫春婷，毛志远. 无线网络非理想反馈下有序数据的渐进式传输[J]. 计算机工程与应用, 2016, 52(8): 97-101.
[11]	王勇锋，李鸥. 基于双门限的多天线分级融合协作频谱感知[J]. 计算机工程与应用, 2015, 51(17): 76-81.
[12]	唐日照1，2，房曙光3，4. 无线链路保障QoS垂直映射技术[J]. 计算机工程与应用, 2015, 51(1): 92-96.
[13]	赵宇，孙挺. 粒子群优化支持向量机的室内无线定位方法[J]. 计算机工程与应用, 2014, 50(19): 95-98.
[14]	何明1，陈国华1，2，杨飞1，梁文辉1，王秋阳3. 三维环境中新的MAWN可靠性评估方法[J]. 计算机工程与应用, 2013, 49(23): 67-70.
[15]	朱铨1，2，蒋新华1，2，邹复民2. 交通干线无线宽带覆盖网络传输性能研究[J]. 计算机工程与应用, 2012, 48(9): 15-17.