相继干扰消除的无线网络中的调度算法
作者:
基金项目:

国家自然科学基金(61070203)


Scheduling Schemes in Wireless Networks with Successive Interference Cancellation
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [16]
  • |
  • 相似文献
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    相继干扰消除(successive interference cancellation,简称SIC)是一种多包接收技术,它从冲突信号中解码报文.SIC 可有效减轻无线网络中的干扰. SIC 的顺序解码特性给链路调度带来了新的挑战.提出并发图以刻画SIC 导致的链路相关性.基于并发图,定义链路的干扰数并据此设计有效的调度机制.证明了基于并发图的链路调度是NP-hard 的,而最大干扰数提供了极大贪婪算法的性能下界.在讨论了一类基于独立集的贪婪算法之后,结合干扰数对链路排序,给出了一种理论上性能更好的算法.仿真结果表明,仅需略高于现有模型的开销,与IEEE 802.11 相比,新调度算法的性能提高可达110%.

    Abstract:

    Successive interference cancellation (SIC) is an effective way of multipacket reception (MPR) to combat interference at the physical layer. The fact that the links decoded sequentially by SIC are correlated at the receiver poses key technical challenges. The study characterizes the link dependence and proposes simultaneity graph (SG) to capture the effect of SIC. Then, the interference number is defined to measure the interference of a link and facilitate the design of scheduling scheme. The study shows that link scheduling over SG is NP-hard, and the maximum interference number bounds the performance of maximal greedy schemes. An independent set based greedy scheme is explored to efficiently construct maximal feasible schedule. Moreover, with careful selection of link ordering, the study presents a scheduling scheme that achieves a better bound. Simulations evaluate the performance. The throughput gain is up to 110% over IEEE 802.11, while the complexity of SG is comparable with that of the conflict graph.

    参考文献
    [1] Gupta P, Kumar PR. The capacity of wireless networks. IEEE Trans. on Information Theory, 2000,46(2):388?404. [doi: 10.1109/ 18.825799]
    [2] Andrews JG. Interference cancellation for cellular systems: A contemporary overview. IEEE Wireless Communications, 2005,12(2): 19?29. [doi: 10.1109/MWC.2005.1421925]
    [3] Weber SP, Andrews JG, Yang XY, de Veciana G. Transmission capacity of wireless ad hoc networks with successive interference cancellation. IEEE Trans. on Information Theory, 2007,53(8):2799?2814. [doi: 10.1109/TIT.2007.901153]
    [4] Halperin D, Anderson TE, Wetherall D. Taking the sting out of carrier sense: Interference cancellation for wireless lans. In: Garcia-Luna-Aceves JJ, ed. Proc. of the ACM MOBICOM 2008. San Francisco: ACM Press, 2008. 339?350. [doi: 10.1145/ 1409944.1409983]
    [5] Brar GS, Blough DM, Santi P. Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks. In: Gerla M, ed. Proc. of the ACM MOBICOM 2006. Los Angeles: ACM Press, 2006. 2?13. [doi: 10.1145/1161089.1161092]
    [6] Wang WZ, Wang Y, Li XY, Song WZ, Frieder O. Efficient interference-aware TDMA link scheduling for static wireless networks. In: Gerla M, ed. Proc. of the ACM MOBICOM 2006. Los Angeles: ACM Press, 2006. 262?273. [doi: 10.1145/1161089.1161119]
    [7] Kumar VSA, Marathe MV, Parthasarathy S, Srinivasan A. Algorithmic aspects of capacity in wireless networks. In: Eager DL, ed. Proc. of the ACM SIGMETRICS 2005. Banff: ACM Press, 2005. 133?144. [doi: 10.1145/1064212.1064228]
    [8] Wang XD, Garcia-Luna-Aceves JJ. Embracing interference in ad hoc networks using joint routing and scheduling with multiple packet reception. In: Hou JC, ed. Proc. of the IEEE INFOCOM 2008. Phoenix: IEEE Press, 2008. 843?851. [doi: 10.1109/ INFOCOM.2008.136]
    [9] Celik GD, Zussman G, Khan WF, Modiano E. MAC for networks with multipacket reception capability and spatially distributed nodes. In: Hou JC, ed. Proc. of the IEEE INFOCOM 2008. Phoenix: IEEE Press, 2008. 1436?1444. [doi: 10.1109/INFOCOM. 2008.202]
    [10] Zhao Q, Tong L. A dynamic queue protocol for multiaccess wireless networks with multipacket reception. IEEE Trans. on Wireless Communications, 2004,3(6):2221?2231. [doi: 10.1109/TWC.2004.837654]
    [11] Zhao Q, Tong L. A multiqueue service room MAC protocol for wireless networks with multipacket reception. IEEE/ACM Trans. on Networking, 2003,11(1):125?137. [doi: 10.1109/TNET.2002.808403]
    [12] Jain K, Padhye J, Padmanabhan VN, Qiu L. Impact of interference on multi-hop wireless network performance. In: Johnson DB, ed. Proc. of the ACM MOBICOM 2003. San Diego: ACM Press, 2003. 66?80. [doi: 10.1145/938985.938993]
    [13] Lü SH, Wang XD, Zhou XM. Link scheduling in wireless networks with successive interference cancellation. In: Rao N, ed. Proc. of the IEEE MSN 2010. Hangzhou: IEEE Press, 2010. 61?67. [doi: 10.1109/MSN.2010.15]
    [14] Malaguti E, Toth P. A survey on vertex coloring problems. Int’l Trans. in Operational Research, 2010,17(1):1?34. [doi: 10.1111/ j.1475-3995.2009.00696.x]
    [15] Network simulator version 2 (NS-2). http://www.isi.edu/nsnam/ns/
    [16] Lü SH, Wang XD, Zhou XM. On the rate adaptation for IEEE 802.11 wireless networks. Computer Networks, 2010,54(17): 3173?3186. [doi: 10.1016/j.comnet.2010.05.020]
    相似文献
    引证文献
引用本文

吕绍和,王晓东,周兴铭.相继干扰消除的无线网络中的调度算法.软件学报,2012,23(4):941-951

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2010-04-14
  • 最后修改日期:2011-01-31
  • 在线发布日期: 2012-03-28
文章二维码
您是第19920949位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号