期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

WSN最短链路调度问题的常数近似算法 被引量：1

Constant Approximation Algorithm for Shortest Link Scheduling Problem in Wireless Sensor Network
下载PDF
导出
摘要 针对无线传感器网络中的最短链路调度问题,在有界线性功率分配方式下,提出一种基于物理干扰模型的常数近似算法。采用网格划分方法,使每个时间段所对应链路集合中的链路都满足SINR阈值约束,并对算法的有效性和近似比进行理论论证。仿真结果表明,与TONOYAN算法相比,在多数情况下该算法具有更小的时间延迟。 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.
作者 吕玉华 禹继国 王晨曦
机构地区 曲阜师范大学计算机科学学院
出处 《计算机工程》 CAS CSCD 2013年第7期110-114,共5页 Computer Engineering
基金 国家自然科学基金资助项目(11101243 60373012) 山东省自然科学基金资助项目(ZR2012FM023 ZR2009GM009 ZR2009AM013) 山东省高校科技计划基金资助项目(J10LG09)
关键词 无线传感器网络 链路调度 最大独立集 物理干扰模型 线性功率分配 NP完全 Wireless Sensor Network（WSN） link scheduling maximum independent set physical interference model linear powerassignment NP-complete problem
分类号 TP393.03 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献11

  • 1Wan 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.
  • 2Wan 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.
  • 3Gupta 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. 被引量：4
  • 5孙懋珩,郑煜,周轩.基于混合干扰模型的多信道Mesh网络调度算法[J].计算机工程与应用,2010,46(35):90-94. 被引量：5
  • 6陈剑,贾杰,闻英友,赵大哲,刘积仁.基于TDMA方式WMN中一种链路调度机制研究[J].控制与决策,2010,25(9):1349-1353. 被引量：3
  • 7Goussevskaia 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.
  • 8Blough 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.
  • 9Wan Pengjun, Frieder O, Jia Xiaohua, et al. Wireless Link Scheduling Under Physical Interference Model[C]//Proc. of INFOCOM’11. Chicago, USA: IEEE Press, 2011.
  • 10Goussevskaia O, Halldorsson M M, Wattenhofer R. Algorithms for Wireless Capacity[EB/OL]. [2012-07-11]. http://arxiv.org/ abs/1203.0536.

二级参考文献34

  • 1Jolly G, Mohamed F. An Energy-efficient, Scalable and Collisionfree MAC Layer Protocol for WSN[J]. Wireless Communications and Mobile Computing, 2005, 5(3): 285-304.
  • 2Ergen S C, Varaiya P. TDMA Scheduling Algorithms for Sensor Networks[R]. Berkeley: Department of Electrical Engineering and Computer Sciences, University of California, 2005.
  • 3Behzad A, Rubin I. On the Performance of Graph-based Scheduling Algorithms for Packet Radio Networks[C]//Proceedings of IEEE GLOBECOM'03. [S. l.]: IEEE Press, 2003.
  • 4Ramanathan S. A Unified Framework and Algorithm for (T/F/C) DMA Channel Assignment in Wireless Networks[C]//Proc. of INFOCOM'97. Kobe, Japan: [s. n.], 1997.
  • 5Wan Chieh-Yih, Eisenman S E, Campbell A T, et al. Siphon: Overload Traffic Management Using Multi-radio Virtual Sinks[C]// Proc. of the 3rd ACM Conf. on Embedded Networked Sensor Systems. San Diego, USA: ACM Press, 2005.
  • 6Gupta P, Kumar P R. The Capacity of Wireless Networks[J]. IEEE Transactions on Information Theory, 2000, 46(2): 388-404.
  • 7Holyer I. The NP-completeness of Edge Coloring[J]. SIAM Journal on Computing, 1981, 10(4): 718-720.
  • 8Wang Weizhao, Wang Yu, Li Xiangyang, et al. Efficient Interferenceaware TDMA Link Scheduling for Static Wireless Networks[J]// Proc. of the ACM MOBICOM'06. [S. l.]: ACM Press, 2006.
  • 9Akyildiz I F, Wang X, Wang W. Wireless mesh networks: A survey [J]. Computer Networks, 2005, 47(4): 445-487.
  • 10Jain K, Padhye J, Padmanabhan V, et al. Impact of interference on multi-hop wireless network performance[C]. Proc of MobiCom. San Diego: ACM press, 2003: 66-80.

共引文献9

同被引文献17

  • 1Wan Pengjun, Frieder O, Jia Xiaohua, et al. Wireless linkscheduling under physical interference model [ C ]//Proceed- ings of IEEE INFOCOM. Shanghai : IEEE,2011:838-845.
  • 2Cardieri P. Modeling interference in wireless ad hoc networks [ J]. Communications Surveys & Tutorials,2010,12(4) :551- 572.
  • 3Goussevskaia O, Oswald Y A, Wattenhofer R. Complexity in geometric SINR [ C ]//Proceedings of the 8th ACM interna- tional symposium on mobile ad hoc networking and compu- ting. Montreal : ACM ,2007 : 100-109.
  • 4Andrews M, Dinitz M. Maximizing capacity in arbitrary wire- less networks in the SINR model:complexity and game theory [ C ]//Proceedings of IEEE INFOCOM. Rio de Janeiro :IEEE, 2009 : 1332-1340.
  • 5Goussevskaia O, Wattenhofer R, Halld6rsson M, et al. Capacity of arbitrary wireless networks [ C ]//Proceedings of IEEE IN- FOCOM. Rio de Janeiro : IEEE ,2009 : 1872-1880.
  • 6Wan Pengjun, Jia Xiaohua, Yao F. Maximum independent set of links under physical interference model [ C ]//Proceedings of WASA 2009. Boston : Springer,2009 : 169-178.
  • 7Kesselheim T. A constant-factor approximation for wireless ca- pacity maximization with power control in the SINR model [ C ]//Proceedings of SODA 2011. [ s. 1. ] : [ s. n. ], 2011 :1549-1559.
  • 8Yang Dejun, Fang Xi, Xue Guoliang, et al. Simple and effec- tive scheduling in wireless networks under the physical inter- ference model [ C ]//Proceedings of global telecommunications conference. [s. 1. ]:Is. n. ] ,2010:1-5.
  • 9Xu Xiaohua,Tang Shaojie. A constant approximation algorithm for link scheduling in arbitrary networks under physical inter- ference model [ C ]///Proceedings of the 2nd ACM international workshop on foundations of wireless ad hoc and sensor networ- king and computing. [ s. 1. ] : [ s. n. ] ,2009 : 13-20.
  • 10Xu Xiaohua,Tang Shaojie,Wan Pengjun. Maximum weighted independent set of links under physical interference model [ C ]//Proceedings of WASA 2010. [ s. 1. ] : [ s. n. ],2010:68 -74.

引证文献1

计算机工程
2013年 第7期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部