WSN最短链路调度问题的常数近似算法

doi:10.3969/j.issn.1000-3428.2013.07.025

计算机工程 ›› 2013, Vol. 39 ›› Issue (7): 110-114. doi: 10.3969/j.issn.1000-3428.2013.07.025

WSN最短链路调度问题的常数近似算法

吕玉华，禹继国，王晨曦

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

收稿日期:2012-07-10 出版日期:2013-07-15 发布日期:2013-07-12
作者简介:吕玉华(1985－)，男，硕士研究生，主研方向：无线网络；禹继国，教授、博士；王晨曦，硕士研究生
基金资助:
国家自然科学基金资助项目(11101243, 60373012)；山东省自然科学基金资助项目(ZR2012FM023, ZR2009GM009, ZR2009 AM013)；山东省高校科技计划基金资助项目(J10LG09)

Constant Approximation Algorithm for Shortest Link Scheduling Problem in Wireless Sensor Network

LV Yu-hua, YU Ji-guo, WANG Chen-xi

(School of Computer Science, Qufu Normal University, Rizhao 276826, China)

Received:2012-07-10 Online:2013-07-15 Published:2013-07-12

摘要/Abstract

摘要： 针对无线传感器网络中的最短链路调度问题，在有界线性功率分配方式下，提出一种基于物理干扰模型的常数近似算法。采用网格划分方法，使每个时间段所对应链路集合中的链路都满足SINR阈值约束，并对算法的有效性和近似比进行理论论证。仿真结果表明，与TONOYAN算法相比，在多数情况下该算法具有更小的时间延迟。

关键词: 无线传感器网络, 链路调度, 最大独立集, 物理干扰模型, 线性功率分配, NP完全

Abstract: Link scheduling is an important issue in Wireless Sensor Network(WSN). For the problem of Shortest Link Scheduling(SLS), this paper gives a constant approximation algorithm with linear power assignment under the physical interference model. All links of each link set in corresponding time slot meet the SINR threshold constraint with grid partition. The effectiveness of the algorithm and the approximate ratio are discussed through theoretical analysis. Simulation experimental results show that the algorithm has less time delay than TONOYAN algorithm.

Key words: Wireless Sensor Network(WSN), link scheduling, maximum independent set, physical interference model, linear power assignment, NP-complete problem

中图分类号:

TP393.03

吕玉华, 禹继国, 王晨曦. WSN最短链路调度问题的常数近似算法[J]. 计算机工程, 2013, 39(7): 110-114.

LV Yu-Hua, YU Ji-Guo, WANG Chen-Xi. Constant Approximation Algorithm for Shortest Link Scheduling Problem in Wireless Sensor Network[J]. Computer Engineering, 2013, 39(7): 110-114.

http://www.ecice06.com/CN/Y2013/V39/I7/110

参考文献

[1] Wan Pengjun, Xu Xiaohua, Frieder O. Shortest Link Sch- eduling with Power Control Under Physical Interference Model[C]//Proc. of the 6th International Conference on Mobile Ad-hoc and Sensor Networks. Chicago, USA: [s. n.], 2010.
[2] Wan Pengjun, Jia Xiaohua, Yao F. Maximum Independent Set of Links Under Physical Interference Model[C]//Proc. of the 4th International Conference on Wireless Algorithms, Systems, and Applications. Chicago, USA: [s. n.], 2009.
[3] Gupta P, Kumar P R. The Capacity of Wireless Networks[J]. IEEE Trans. on Information Theory, 2000, 46(2): 388-404.
[4] 蹇强, 桂春梅, 龚正虎, 等. 一种无线传感器网络链路调度模型算法[J]. 计算机工程, 2009, 35(7): 1-4.
[5] 孙懋珩, 郑煜, 周轩. 基于混合干扰模型的多信道Mesh网络调度算法[J]. 计算机工程与应用, 2010, 46(35): 90-94.
[6] 陈剑, 贾杰, 闻英友, 等. 基于TDMA方式WMN中一种链路调度机制研究[J]. 控制与决策, 2010, 25(9): 1349- 1353.
[7] Goussevskaia O, Oswald Y A, Wattenhofer R. Coplexity in Geometric SINR[C]//Proc. of the 8th ACM International Symposium on Mobile Ad hoc Networking and Computing, New York, USA: [s. n.], 2007.
[8] Blough M, Resta G, Santi P. Approximation Algorithms for Wireless Link Scheduling with SINR-based Interference[J]. IEEE/ACM Trans. on Networking, 2010, 18(6): 1701- 1712.
[9] Wan Pengjun, Frieder O, Jia Xiaohua, et al. Wireless Link Scheduling Under Physical Interference Model[C]//Proc. of INFOCOM’11. Chicago, USA: IEEE Press, 2011.
[10] Goussevskaia O, Halldorsson M M, Wattenhofer R. Algorithms for Wireless Capacity[EB/OL]. [2012-07-11]. http://arxiv.org/ abs/1203.0536.
[11] Tonoyan T. On the Problem of Wireless Scheduling with Linear Power Levels[EB/OL]. [2012-07-11]. http://arxiv.org/abs/1107. 4981.
编辑金胡考

[1]	杨敏, 张玲华. WSN中基于区域感知的改进AODV路由协议[J]. 计算机工程, 2023, 49(8): 130-136.
[2]	区展华, 李翠然, 杨茜. 基于ANN的能量采集无线传感器网络中继选择策略[J]. 计算机工程, 2023, 49(5): 215-222,230.
[3]	周文康, 王行甫. 一种基于AHP和FIS的WSN路由算法[J]. 计算机工程, 2022, 48(3): 131-138,161.
[4]	张清国, 张勇, 张伟, 席瑞洁. 基于蜂窝结构的改进混合无线传感器网络覆盖优化算法[J]. 计算机工程, 2022, 48(12): 172-179.
[5]	王海浪, 张玲华. 基于PEGASIS的无线传感器网络路由协议改进[J]. 计算机工程, 2022, 48(12): 165-171,179.
[6]	陈辉, 高岩. 基于双簇头的WSNs非均匀分簇路由算法[J]. 计算机工程, 2022, 48(10): 184-192.
[7]	缪祎晟, 赵春江, 吴华瑞. 基于改进粒子群的农田WSN路由优化方法[J]. 计算机工程, 2022, 48(10): 218-223.
[8]	韩优佳, 胡黄水, 姚美琴. 基于信任感知的无线传感器网络安全路由协议[J]. 计算机工程, 2021, 47(9): 145-152.
[9]	于吉喆, 白乐强, 曹科研. 基于垂线的WSN基站位置隐私保护算法[J]. 计算机工程, 2021, 47(8): 170-176,182.
[10]	蒋宝庆, 陈宏滨. 基于Q学习的无人机辅助WSN数据采集轨迹规划[J]. 计算机工程, 2021, 47(4): 127-134,165.
[11]	胡乔木, 邓昀. 基于压缩HMAC算法的传感器网络范围查询方法[J]. 计算机工程, 2021, 47(12): 200-208.
[12]	李翠然, 李昂. 太阳能补给的线型WSN能量高效路由算法[J]. 计算机工程, 2020, 46(9): 178-185.
[13]	柳亚男, 张正, 邱硕, 程远. WSN中基于物理不可克隆函数的簇内密钥分配[J]. 计算机工程, 2020, 46(9): 163-171.
[14]	郝占军, 侯姣姣, 党小超, 曲南江. 一种适用于带状区域的WSN节点覆盖优化方法[J]. 计算机工程, 2020, 46(7): 165-172.
[15]	郝占军, 徐宏文, 党小超, 段渝. 一种WSN三维覆盖空洞动态检测与修复算法[J]. 计算机工程, 2020, 46(6): 178-186.

选择文件类型/文献管理软件名称

选择包含的内容

WSN最短链路调度问题的常数近似算法

Constant Approximation Algorithm for Shortest Link Scheduling Problem in Wireless Sensor Network

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

WSN最短链路调度问题的常数近似算法

Constant Approximation Algorithm for Shortest Link Scheduling Problem in Wireless Sensor Network

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价