DLSOMAC: a MAC Protocol Oriented to Distributed Wireless Link Scheduling Technology
-
摘要: 无线网络分布式链路调度技术通过发掘无线传输间的复用达到提高吞吐量的目的. 链路调度策略的形成需要节点间公平地交互含有如节点ID、队列长度等信息的短报文,并且这些短报文同步传输,导致信道拥挤.由于存在信道空闲侦听开销,在拥挤信道中频繁后退,以及隐藏终端和暴露终端的问题,传统的CSMA/CA (Carrier sense multiple access with collision avoidance)协议传输性能低下,难以为分布式无线链路调度技术服务. 针对链路调度策略形成期间报文短、信道拥挤以及公平性要求的挑战.提出了一个简单的随机MAC (Media access control)协议DLSOMAC (Distributed link scheduling oriented MAC). DLSOMAC协议没有信道侦听过程,以降低短报文的传输延迟开销;基于分布式息票收集算法,均匀分散传输时刻来降低冲撞概率和提高公平性,以满足分布式链路调度技术对MAC层的需求.用排队论分析了DLSOMAC的报文传输延迟性能.仿真实验表明, 在短报文情况下,无论网络负载轻重与否, DLSOMAC协议的报文传输延迟明显优于CSMA/CA,并且报文越短,性能相对越好.即使在长报文的情况下,当网络负载很重时, DLOSMAC协议也稍优于CSMA/CA协议,适合于为自组织网络的分布式链路调度技术服务.Abstract: The distributed link scheduling strategy can improve the performance of throughput notably by exploring multiplexing among wireless transmissions. Conceptually, to form a link scheduling strategy, network nodes need fairly exchange short packet embedded with information, such as node identity, queue length, etc. However, synchronous transmissions of these short packets will result in serious channel collision. Due to the weakness of idle listening overhead, frequent back-off in busy channel, and the infamous hidden terminal and exposed terminal, the traditional CSMA/CA (Carrier sense multiple access with collision avoidance) protocol cannot support distributed link scheduling effectively. To overcome these weaknesses, we propose a novel randomized MAC (Media access control) protocol called DLSOMAC (Distributed link scheduling oriented MAC) in this work. In DLSOMAC, the transmission delay is relatively small since DLSOMAC doesn't have idle listening. We use the distributed coupon collection algorithm to disperse transmissions into different slots uniformly. Thus the collision probability is decreased and fairness guaranteed. We also analyse the transmission delay using queuing theory. Simulation results demonstrate that in short packet transmissions, the network throughput of DLSOMAC outperforms that of CSMA/CA notably under any network loads. Especially, the shorter the packet is, the better the relative performance is. Even when the network load is heavy or the packet is long, the network throughput of DLSOMAC is still slightly greater than that of CSMA/CA. The DLSOMAC is a suitable MAC protocol for ad hoc networks to support distributed link scheduling.
-
Key words:
- MAC /
- link scheduling /
- CSMA/CA /
- randomized /
- ad hoc
-
[1] Jian N, Bo T, Srikant R. Q-CSMA: queue-length-based csma/ca algorithms for achieving maximum throughput and low delay in wireless networks. IEEE/ACM Transactions on Networking, 2011, 20(3): 825-836 [2] Changhee J, Lin X J, Jiho R. Distributed greedy approximation to maximum weighted independent set for scheduling with fading channels. In: Proceedings of the 14th ACM International Symposium on Mobile and Ad hoc Networking and Computing. NewYork, USA: ACM, 2013. 89-98 [3] Schneider J, Wattenhofer R. An optimal maximal independent set algorithm for bounded-independence graphs. Journal of Distributed Computing, 2010, 22(3): 349-361 [4] Zheng Guo-Qiang, Li Jian-Dong, Zhou Zhi-Li. Overview of mac protocols in wireless sensor networks. Acta Automatica Sinica, 2008, 34(3): 305-316(郑国强, 李建东, 周志立. 无线传感器网络MAC协议研究进展. 自动化学报, 2008, 34(3): 305-316) [5] Xu Chao-Nong, Huang Chang-Xi, Hu Cun-Gang, Liu Yong. Dk-hop: a directed k-hop wireless interference model. Acta Automatica Sinica, 2012, 38(6): 1042-1050(徐朝农, 黄长喜, 胡存钢, 刘勇. Dk-hop: 一个有向k跳无线干扰模型. 自动化学报, 2012, 38(6): 1042-1050) [6] Niu Jian-Jun, Deng Zhi-Dong, Li Chao. Distributed scheduling approaches in wireless sensor network. Acta Automatica Sinica, 2011, 37(5): 517-528(牛建军, 邓志东, 李超. 无线传感器网络分布式调度方法研究. 自动化学报, 2011, 37(5): 517-528) [7] Yehuda A, Noga A, Omer B, Eran H, Naama B, Ziv B J. A biological solution to a fundamental distributed computing problem. Science, 2011, 331(6014): 183-185 [8] Kumar S, Raghavan V, Deng J. Medium access control protocols for ad hoc wireless network: a survey. Ad Hoc Networks, 2006, 4(3): 326-358 [9] Norman A. The aloha system-another alternative for computer communications. In: Proceedings of Fall Joint Computer Conference. New York, USA: ACM, 1970. 281-285 [10] Xu K X. How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks. In: Proceedings of the IEEE Global Telecommunications Conference. 2002. Taipei, China: IEEE, 2002. 72-76 [11] Tassiulas L, Ephremides A. Stability properties of constrained queueing systems and scheduling policies for maximal throughput in multihop radio networks. IEEE Transaction on Automatic Control, 1992, 17(5): 1467-1480 [12] Bui L, Sanghavi S, Srikant R. Distributed link scheduling with constant overhead. IEEE/ACM Transactions on Networking, 2009, 17(5): 1467-1480 [13] Joo C, Sharma G, Shroff N B, Mazumdar R R. On the complexity of scheduling in wireless networks. In: Proceedings of the 12th International Conference on Mobile Computing and Networking. New York, USA: ACM, 2006. 227-238 [14] Birand B, Chudnovsky M, Ries B, Seymour P, Zussman G, Zwols Y. Analyzing the performance of greedy maximal scheduling via local pooling and graph theory. IEEE/ACM Transaction on Networking, 2012, 20(1): 163-176 [15] Cole R, Vishkin U. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 1986, 70(1): 32-53 [16] Sudarshan V, Micah A, Dennis G, Don T. Efficient algorithms for neighbor discovery in wireless networks. IEEE/ACM Transaction on Networking, 2013, 21(1): 69-83 [17] Ho T S, Chen K C. Performance analysis of IEEE 802.11 csma/ca medium access control protocol. In: Proceedings of the 7th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications. Taipei, China: IEEE, 1996. 407-411 [18] Li Q, Rus D. Global clock synchronization in sensor networks. IEEE Transaction on Computers, 2006, 55(2): 214-226
点击查看大图
计量
- 文章访问数: 1861
- HTML全文浏览量: 55
- PDF下载量: 590
- 被引次数: 0