Weakly-hard real-time scheduling algorithm for wireless networks
-
摘要: 提出了一种结合信道状况考虑的(m, k)-firm弱硬实时调度算法.该算法将消息划分为强制(mandatory)和可选(optional)2种类型,并优先调度强制消息.消息的类型由线下静态分配和线上动态调整共同决定.其中,静态分配使用(m, k)-pattern分配消息类型,动态调整是在不违反(m, k)-firm约束的前提下尽力减少强制消息在差信道状况下传输.理论分析证明:①在假设所有强制消息都实时成功传输的前提下,经动态调整的消息集仍然满足(m, k)-firm;②在使用平均分布(m, k)-pattern时,动态调整之后不改变消息集中强制消息的N次重传可调度性.仿真结果表明,该算法与仅使用静态分配消息类型的算法比较,能够改善弱硬实时的可调度性能,节省无线网络中带宽和能耗的开销.Abstract: A (m, k)-firm scheduling algorithm combined with wireless channel state consideration was proposed. The algorithm classified the messages into mandatory ones and optional ones, and scheduled the mandatory messages in higher priority. The message type was jointly decided by static offline assignment and dynamical online adjustment. The static assignment used (m, k)-pattern to assign the message types, and the dynamic adjustment adjusted message types by trying to reduce the number of mandatory messages in the bad channel state without breaking the (m, k)-firm constraints. The theoretical analysis prove that ①the dynamic adjustment will not break the (m, k)-firm constraints if assuming all the mandatory messages can be transmitted successfully before deadline, and ②the dynamic adjustment will not change the mandatory messages- schedulability when using evenly distributed (m, k)-Pattern. The simulation results show that compared with the algorithm that assigns message types in static way this algorithm can improve the schedulability and save the wireless networks- bandwidth and energy.
-
Key words:
- real time systems /
- wireless networks /
- scheduling algorithms /
- channel state information
-
[1] Bernat G,Burns A,Llamosi A.Weakly hard real-time systems [J].IEEE Transactions on Computers,2001,50(4):308-321 [2] Hamdaoui M,Ramanathan P.A dynamic priority assignment technique for streams with (m,k)-firm deadlines [J].IEEE Transactions on Computers,1995,44(12):1443-1451 [3] Koren G,Shasha D.Skip-over:algorithms and complexity for overloaded systems that allow skips [C]//Real-Time Systems Symposium.Pisa:IEEE,1995:110-117 [4] Ramanathan P.Overload management in real-time control applications using (m,k)-firm guarantee [J].IEEE Transactions on Parallel And Distributed Systems,1999,10(6):549-559 [5] Quan G,Hu X.Enhanced fixed-priority scheduling with (m,k)-firm guarantee [C]//Real-Time Systems Symposium.Orlando:IEEE,2000:79-88 [6] Kim K H,Kim J.An energy-efficient FEC scheme for weakly hard real-time communications in wireless networks[C]//Embedded and Real-Time Computing Systems and Applications.Sydney:IEEE,2006:415-419 [7] Willig A.Scheduling multiple streams with (m,k)-firm deadlines having different importance over markovian Channels[C]//Emerging Technologies and Factory Automation.Catania:IEEE,2005:79-85 [8] Semprebom T,Montez C,Moraes R.Distributed DBP:a (m,k)-firm based distributed approach for QoS provision in IEEE 802.15.4 networks [C]//Emerging Technologies & Factory Automation.Mallorca:IEEE,2009:1-8 [9] Gilbert E N.Capacity of a burst-noise channel [J].Bell System Technical Journal,1960,39(8):1253-1265 [10] Niu Linwei,Quan gang.Energy minimization for real-time systems with (m,k)-guarantee [J].IEEE Transactions on Very Large Scale Integration Systems,2006,14(7):717-729 [11] Zheng Q,Shin K G.On the ability of establishing real-time channels in point-to-point packet-switched networks [J].IEEE Transactions on Communication,1994,42(234):1096-1105 [12] Shakkottai S,Srikant R.Scheduling real-time traffic with deadlines over a wireless channel [J].Wireless Networks,2002,8:13-26 -
点击查看大图
计量
- 文章访问数: 6578
- HTML全文浏览量: 206
- PDF下载量: 927
- 被引次数: 0
下载:
