基于高阶马尔可夫链WSN低时延调度算法
|
摘要
对于无线传感网络,节点数据到达率和服务都随着时间和环境不断变化,基于Glauber动态模型的CSMA无线传输网络的调度解决方案,吞吐量较优,但马尔可夫链对链接状态随时间推移构成根本性约束,基于此提出一种新的基于高阶马尔可夫链的低延时排队序列链路调度算法,首先观察局部链路状态信息,然后构造可行链路演化的马尔可夫链时间表。实验结果表明,通过有效的"去相关"链路进程,该方法实现吞吐量最优,而且能提供更好的延时性能。
Several CSMA algorithms based on the Glauber dynamics model have been proposed for wireless sensor network link scheduling,as viable solutions to achieve the throughput optimality,yet simple to implement. However,their delay performance still remains unsatisfactory,mainly due to the nature of the underlying Markov chains that imposes a fundamental constraint on how the link state can evolve over time. In this paper,we propose a new approach toward better queuing delay performance,based on our observation that the algorithm needs not be Markov Chain,as long as it can be implemented in a distributed manner. Our approach hinges upon utilizing past state information observed by local link and then constructing a high-order Markov chain for the evolution of the feasible link schedules. We show that our proposed algorithm, named delayed CSMA, achieves the throughput optimality, and also provides much better delay performance by effectively ‘de-correlating’ the link state process. Our simulation results demonstrate that the delay under our algorithm can be reduced in some cases,compared to the standard Glauber-dynamics-based CSMA algorithm.
Several CSMA algorithms based on the Glauber dynamics model have been proposed for wireless sensor network link scheduling,as viable solutions to achieve the throughput optimality,yet simple to implement. However,their delay performance still remains unsatisfactory,mainly due to the nature of the underlying Markov chains that imposes a fundamental constraint on how the link state can evolve over time. In this paper,we propose a new approach toward better queuing delay performance,based on our observation that the algorithm needs not be Markov Chain,as long as it can be implemented in a distributed manner. Our approach hinges upon utilizing past state information observed by local link and then constructing a high-order Markov chain for the evolution of the feasible link schedules. We show that our proposed algorithm, named delayed CSMA, achieves the throughput optimality, and also provides much better delay performance by effectively ‘de-correlating’ the link state process. Our simulation results demonstrate that the delay under our algorithm can be reduced in some cases,compared to the standard Glauber-dynamics-based CSMA algorithm.
引文
[1]阚保强,魏祥麟,范建华,等.MHWN吞吐量最优的分布式链路调度算法[J].信息工程大学学报,2016,17(5):10-16.
[2]Joo C,Lin X,Shroff NB.Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks[J]IEEE INFOCOM.2008,17(4):1103-1111.
[3]Leconte M,Ni J,Srikant R.Improved bounds on the throughput efficiency of greedy maximal scheduling in wireless networks[J].Acm Interational Symposium on Mobile Ad Hoc Networking&Computing,2009,19(3):165-174.
[4]Jiang L,Walrand J.A distributed CSMA algorithm for throughput and utility maximization in wireless networks[C]//Conference on Communication,Illinois,USA,IEEE/ACM Trans,2008.
[5]Shah D,Shin J.Delay optimal queue-based CSMA[J].Acm Sigmetrics Performance Evaluation Review,2010,38(1):373-374.
[6]Lotfinezhad M,Marbach P.Throughput-optimal random access with order-optimal delay[J].IEEE INFOCOM,2010,28(6):2867-2875.
[7]Lam K K,Chau C K,Chen M,et al.Mixing time and temporal starvation of general CSMA networks with multiple frequency agility[J].IEEE International Symposium on Information Theory,2012,22(5):2676-2680.
[8]Huang P K,Lin X.Improving the delay performance of CSMA algorithms:a virtual multi-channel approach[J].IEEE INFOCOM,2013,12(11):2598-2606.
[9]Lee C H,Eun D Y,Yun S Y,et al.From glauber dynamics to metropolis algorithm:Smaller delay in optimal CSMA[J].IEEE International Symposium on Information Theory,2012,59(5):2681-2685.
[10]Hayes T P,Sinclair A.A general lower bound for mixing of single-site dynamics on graphs[J].Annals of Applied Probability,2007,17(3):931-952.
[11]李峰,司亚利,陈真,等.基于马尔可夫链的轻量级机会路由转发策略[J].通信学报,2017,38(5):108-120.
[2]Joo C,Lin X,Shroff NB.Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks[J]IEEE INFOCOM.2008,17(4):1103-1111.
[3]Leconte M,Ni J,Srikant R.Improved bounds on the throughput efficiency of greedy maximal scheduling in wireless networks[J].Acm Interational Symposium on Mobile Ad Hoc Networking&Computing,2009,19(3):165-174.
[4]Jiang L,Walrand J.A distributed CSMA algorithm for throughput and utility maximization in wireless networks[C]//Conference on Communication,Illinois,USA,IEEE/ACM Trans,2008.
[5]Shah D,Shin J.Delay optimal queue-based CSMA[J].Acm Sigmetrics Performance Evaluation Review,2010,38(1):373-374.
[6]Lotfinezhad M,Marbach P.Throughput-optimal random access with order-optimal delay[J].IEEE INFOCOM,2010,28(6):2867-2875.
[7]Lam K K,Chau C K,Chen M,et al.Mixing time and temporal starvation of general CSMA networks with multiple frequency agility[J].IEEE International Symposium on Information Theory,2012,22(5):2676-2680.
[8]Huang P K,Lin X.Improving the delay performance of CSMA algorithms:a virtual multi-channel approach[J].IEEE INFOCOM,2013,12(11):2598-2606.
[9]Lee C H,Eun D Y,Yun S Y,et al.From glauber dynamics to metropolis algorithm:Smaller delay in optimal CSMA[J].IEEE International Symposium on Information Theory,2012,59(5):2681-2685.
[10]Hayes T P,Sinclair A.A general lower bound for mixing of single-site dynamics on graphs[J].Annals of Applied Probability,2007,17(3):931-952.
[11]李峰,司亚利,陈真,等.基于马尔可夫链的轻量级机会路由转发策略[J].通信学报,2017,38(5):108-120.