基于W学习的无线网络传输调度方案

摘要：针对无线网络的传输问题，提出了一种适用于无线网络的智能传输调度方案，在马尔可夫决策过程（MDP）的基础上构建了系统模型，通过W学习算法的引入，中继节点对缓存器储存状态及信道质量进行学习，从而在信息数据包的传输过程中智能地选择数据包传输对象及数据包传输方式来达到在节省能量损耗的前提下尽量减少数据包丢失的目的。通过状态聚合方法解决因状态空间过大而导致的维灾问题，同时采用了行动集缩减来以减少某些状态对应的行动数，利用这些简化方法可以发现逐次逼近法的存储空间压缩率为41%，W学习算法的存储空间压缩率为43%。最后，系统仿真结果表明，提出的传输调度方案可以在节省能耗的基础上尽量地传输数据，减少了数据包的丢失，同时采取的状态聚合法及行动集缩减在有效地简化计算的同时并没有影响算法的性能。

关键词：传输调度方案；马尔可夫决策过程；W学习算法；中继节点；近似最优策略

0引言

随着无线通信技术的不断发展，频谱资源日趋紧张，与此同时，通信网络的规模也在不断扩张中。由于智能传输不仅可以提高频谱分配效率，还可以解决大规模传输网络的传输调度问题，所以适用于无线网络的智能传输调度成为研究热点之一。文献[1]在具有节能意识的传感器通信中构建了一种近似最优的加强学习框架，通过使用加强学习来减少传输对系统转移概率的依赖；文献[2]则基于马尔可夫决策过程（Markov Decision Process， MDP）在学习算法的基础上构建了一种无线电网络的传输调度方案，使得在满足缓存器丢包率约束的前提下，最小化平均功率消耗；文献[3]则基于自适应行为，利用指数退避针对载波侦听多路访问（Carrier Sense Multiple Access， CSMA）网络中节点的竞争与合作建立了一种新的方法；此外也有很多文献对无线网络的智能传输调度进行了相关研究[4-9]。

本文提出的传输调度方案的主要目的是在无线网络传输中综合考虑传输调度导致的数据包丢失和能量损耗，以获得最大的系统效用。本文将基于马尔可夫决策过程对该方案进行建模，通过模拟仿真将本策略中基于W学习算法求出的策略与逐次逼近法求解该MDP的最优策略及几种算法相比较。此外本文提出了状态聚合法及行动集缩减的近似最优策略求解方法，同时证明，在某些假设条件下近似最优策略等价于最优策略。

1系统模型

系统模型如图1所示：存在一个无线节点，作为其他k个无线节点的中继，帮它们转发数据。当k个节点的数据到达中继节点后，将被保存到每个节点所对应的缓存器内，再由中继节点通过每个节点所对应的无线信道帮其转发数据。由于在同一帧内，中继节点只能选择帮一个节点转发数据，所以中继节点将根据每个节点所对应的缓存状态，无线信道状态，来判断在每个时隙内为哪个节点传输数据包及调制方式。假设上层数据到达节点i所对应的长度为Li的缓存器呈现到达率为λi的泊松分布，而节点i所对应的无线信道状态可以定义为：C{c0，c1，c2，…，cn}。

1.1有限状态马尔可夫信道与自适应调制

由于节点所对应的无线信道为快衰落信道，且节点能够对其信道状态准确估计，所以单一节点所对应的传输信道可被建模为遍历的一阶有限状态离散时间马尔可夫链（Finitestate Markov Chain， FSMC）[10]。节点1至节点k对应合并加性高斯白噪声的瑞利信道信噪比（SignaltoNoise Ratio， SNR）呈现指数分布，本文可以将其概率密度表示为函数pSNR（γ）=1γm0exp（-γ/γm0）此公式的表达是否准确，请明确。，其中：γ≥0，γm0表示信道的平均信噪比。本文通过划定信噪比门限Vsnr=[snr1，snr2，snr3，…，snrn]来判定节点传输信道状态，当信道信噪比小于snr1时，定义信道状态为c1；当信道信噪比大于等于这个是否应该为大于等于？请明确。snr1小于snr2时，定义信道状态为c2，以此类推，本文可以将信道分为几种状态：C{c0，c1，c2，…，cn}。对于状态ck，信道处于该状态的概率为pC（ck）=∫Γk+1ΓkpSNR（γ）dγ，且信道状态的转移概率为：

pc（ck，ck+1）=N（Γk+1）Tf/pc（ck）；k∈{0，1，…，K-2}（1

pc（ck，ck-1）=N（Γk）Tf/pc（ck）；k∈{1，2，…，K-1}（2

在这里N（Γk）=2πΓk/γm0fmdexp（-Γk/γm0）， fmd则为最大多普勒频移。对于传输方式相对相移键控（Binary Phase Shift Keying， BPSK）、正交相移键控（Quadrature Phase Shift Keying， QPSK）、8相相移键控（8 Phase Shift Keying， 8PSK）、16相相移键控（16 Phase Shift Keying， 16PSK）等，可以限定其比特误码率（Bit Error Ratio， BER）的界，对于u1即m=1（BPSK）有[11]：

pBER（ck，u1）≤0.5 erfc（ΓkP（ck，u1）/WN0）（3

对于uj， j∈{2，3，4}即m=2，3，…（QPSK，8PSK，…）且BER≤10-3，有：

pBER（ck，uj）≤0.2exp-1.6ΓkP（ck，uj）WN0（2j-1）（4）

其中WN0表示噪声功率。通过上面的不等式，本文可以得出在不同信道状态及传输方式下，满足特定比特误码率所消耗的最小功率。可以假设系统中节点对应的信道状态彼此独立[12]，那么令节点i所对应信道状态转移概率为pci（ci，ci′），整个系统的信道状态转移概率可以表示为：

pch（c，c′）=pc1（c1，c1′）×pc2（c2，c2′）×…×pck（ck，ck′）（5

1.2缓存器的状态变化

定义qi为每帧内（帧长为Ts）到达节点i所对应缓存器里的数据量，而每帧到达缓存器的数据包量呈到达率为λi的泊松分布，那么每帧内到达的数据量qi可以表示为：

pqi（qi）=exp（-λqiTs）（λiTs）qiqi！（6

在某时隙内，假设节点i所对应的缓存器内有bi个数据包，同时中继节点为其传输了ai（ai=V×2mi）个数据包，那么在下一帧时，缓存器内的数据包数为：

b′=min {bi-ai+qi，Li}（7

在整个系统中，节点对应缓存器的长度彼此独立，则定义缓存器内数据包量的转移概率为pbi（bi，bi′），整个系统的缓存器状态转移概率为：

pbu（b，b′）=pb1（b1，b1′）×pb2（b2，b2′）×…×pbk（bk，bk′）（8

2马尔可夫决策过程与传输调度问题

可以将传输调度问题建模为一个马尔可夫决策过程[13-17]。马尔可夫决策过程可以用5个元素来表示：{S，A，P，R，C这5个变量是矩阵、向量或矢量吗，请明确。}。其中：S为状态空间，A、P、R和C分别为行动集、状态转移概率矩阵、收益及代价。

2.2行动集

定义行动集A{a0，a1，…，aN}。一旦采用行动ai，则中继节点将选择为节点i以传输方式mi传输数据。传输方式m（m=1，2，3，4，…）分别可以对应为BPSK、QPSK、8PSK、16PSK……。定义信息的传输速率为V，则使用不同的信息传输方式可以传输的信息量为V×2mi。在本文提出的调度方案中，所希望得到的行动是在当前状态下能够得到最大系统收益的行为，即传输选择问题可以描述为：

2.3收益及代价

由于本文提出的调度方案要达到智能地传输数据，在减少丢包的前提下减少能量的损耗，所以在这里定义系统传输的代价是传输数据所消耗的功率以及缓存器内存储数据的压力值。在状态si下，使用行动ai所需的功率为Pt（si，ai），而缓存器的压力值则定义为exp（gamma×bi）。根据本文提出调度方案的要求，为了使系统传输时，能在满足缓存器丢包率约束的前提下，最小化平均功率消耗，可以将节点i的收益定义为：

Ri=V×2miPt（si，ai）×exp（gamma×bi）（12

gamma可以用来控制传输数据包数量及传输所消耗能量重要性的比重。整个系统的效用则为：

3算法介绍

3.1W学习算法

基于W学习算法进行策略迭代计算所需的环境信息较少，本文提出的调度方案建立在W学习算法的基础上。图2体现了W学习算法的基本思想[18-20]：将整个系统分散开来，每个节点分别学习，通过比较每个节点给出的W值来判断当前状态下系统所应该采取的行动。可以将W值来理解为假设不执行某一行为而导致的损失，定义W值[18-20]为：

在Q学习算法中：ri为每次迭代的收益；visit表示访问次数；为学习因子，其取值为=1/（1+visit），即随着迭代的访问次数增加而的值变小，以此来使得学习算法的最终结果收敛。在实际迭代W学习算法时，一般不可能等到Q学习算法完全迭代完成之后才开始迭代W值，所以为了可以同时迭代Q值与W值，将W值的迭代方式更改为：

Wi+1（si）=（1-w）Wi（si）+w（1-Q）ω（Qi（x，ai）-（ri+γmaxb∈AQi（si+1，b）））（16

用（1-Q）ω来控制当Q值未迭代至收敛时对W值迭代的影响，Q（Q=1/（1+visit））为每次Q值迭代时的学习因子；ω可以用来控制W值的收敛，ω值取得越低则收敛越慢。

在本文提出的系统中，W学习算法可以对中继节点的传输选择进行指导而不依赖于系统状态的转移概率，相比W学习算法，逐次逼近法对近似最优策略进行迭代时则依赖于系统状态的转移概率。然而在实际的信息传输过程中，很多时候节点并不能得到系统状态的转移概率，所以在实际应用中，使用W学习算法能够更好地适应环境。

3.2逐次逼近法

为了评估本文提出方案的性能，将使用逐次逼近法来得到系统的最优策略。由于逐次逼近法并不能通过有限次数的迭代计算直接得到系统的最优策略，而只能通过逐步缩小范围逐渐地逼近系统的最优选择，所需的计算量比较大，所以逐次逼近法并不适用状态空间太大的情况，为了能用逐次逼近法来描述系统的最优选择，需要尽可能地减少系统状态。逐次逼近法的迭代方式[21-22]为：

Vn+1=TVn=maxf∈F{r（f）+βP（f）Vn}=r（fn）+βP（fn）Vn（17

3.3计算量分析

理论上，逐次逼近法迭代次数够多的话，最终得到的策略可以逼近于最优策略，但是需要迭代的计算量却极大。对于逐次逼近法，系统状态数可以表示为S1=（（l+1）×c）k，其中：c为节点所对应信道的状态数，k为节点数。假设N1表示逐次逼近法迭代运算所需的计算量，A1为状态所对应的行为数，那么逐次逼近法所需的计算量为：T1=（（l+1）×c）k×A1×N1；而对于W学习算法，系统状态数为：S2=（l+1）×c×k，迭代运算所需的计算量则为：T2=（l+1）×c×k×A2×N2。其中：N2为W学习算法迭代运算所需的计算量，A2则为W学习算法的系统状态所对应的行为数。在本文的仿真分析中，首先假设系统中存在两个需要传输数据的节点，其上层数据到达率相同，且节点所对应的缓存器长度均为5，信道状态分为4种状态，那么逐次逼近法的系统状态数为576，相对的W学习算法的系统状态数则只有24个。由于逐次逼近法的系统状态数多于W学习算法，可以得到逐次逼近法要迭代收敛所需的计算次数N1将大于W学习算法所需的计算次数N2；而逐次逼近法的状态对应行为数也大于W学习算法。由以上分析可知逐次逼近法不仅需要更多的环境信息，同时其迭代计算量将远远大于W学习算法所需的计算量。

4马尔可夫决策过程求解

4.1状态聚合

在使用逐次逼近法及W学习算法对每个状态进行迭代计算时，如果状态空间的规模很大，不仅会消耗巨大存储空间，而且会减慢算法收敛速度甚至会由于需要迭代次数趋于无穷大从而使算法不收敛，导致维灾[23]。在本文中，使用逐次逼近法的系统状态数为（（l+1）×c）k，W学习算法的系统状态数则为（l+1）×c×k，可以看出随着节点数的增长，系统状态数快速增长，造成算法的不可解，所以在这里采用状态聚合的方法来缩减系统状态空间的规模，减少状态数。

状态聚合的原则是：如果节点对应的信道状态极差，则无需知道信道的具体状态，中继节点直接选择不为其传输数据。

对于系统中的每个节点来说，当其所对应的传输信道状态极差时，系统为其传输数据将消耗大量功率，同时还不一定能传输成功，造成能量的损失，所以在这种情况下，选择不为其传输数据为更优的策略。所以对于状态ci=0，本文均选择不为节点i传输数据，那么可以将所有拥有状态c=0的系统状态聚合起来[24]，即本文将所有状态c=0的系统状态均选择不传输数据。当所有节点信道状态为：C{c1=0，c2=1，c3=2}，缓存器长度均为l=2，则在上层数据到达率相同的情况下，系统的组合状态矩阵空间为：

S=（0，0），（0，1），（0，2），（1，0），（1，1），（1，2），（2，0），（2，1），（2，2）

S={（0，0），（0，1），（0，2），（1，0），（1，1），（1，2），（2，0），（2，1），（2，2）}

则根据上述聚合方法，可以将系统状态矩阵空间聚合为：S1={（0，0），（0，1），（0，2）}，S2={（1，0）}，S3={（1，1）}，S4={（1，2）}，S5={（2，0）}，S6={（2，1）}，S7={（2，2）}。基于以上聚合状态，可以重新定义系统状态，再按照逐次逼近法及W学习算法来对系统进行迭代学习，减少计算量。可以证明，利用上文所提出的状态聚合，逐次逼近法在减少计算复杂度的同时，迭代结果所受的影响极小。

引理1将状态空间S划分为W个没有交集的子空间S1，S2，…，SW。给定行动a，任意s∈SW，如果有Q（s，a）=δ（w，a），则采用基于状态聚合的相关值迭代算法能够得到最优策略[23]。

定理1如果每个节点的状态转移概率独立且相同，则使用状态聚合方法迭代得到的近似最优策略等价于最优策略。

用数学归纳法证明。

证明在最优策略的求解过程中，逐次逼近法及W学习算法的迭代方程分别为式（17）和（14）。由于本文的状态聚合法，当系统信道状态极差时明显有，r（fn）及ri均为0，则根据迭代计算可以得到对于聚合状态Sw={（s1，s2，…，sk）}有Vn（sk，a）=0，Q（sk，a）=0，sk∈Sw，由引理1可知，基于本文的状态聚合的相关值迭代算法可以得到最优策略。

4.2行动集缩减

在迭代运算中使用行动集缩减也可以减少内存消耗，同时加速算法的收敛。根据系统设定，可以知道，所有状态均对应有相同的行动集。而行动集缩减则是在尽量小影响算法性能的基础上，将某些状态下的行动集缩小。

引理2一个以最小化负收益为优化目标的MDP，给定状态S，若ps（s，s′/a）=ps（s，s′/a′）且i（s，a′）

基于引理2，可以得出定理2。

定理2基于上述行动集缩减得到的策略等价于最优策略。

定理2的基本思路陈述如下：

首先，如果某信道的状态很差，则通过该信道发送数据包不但不会成功，还会大量消耗功率，而且会造成数据包的丢失；其次，相对于不发送数据包而言，发送数据包也不能改变缓存器的存储状态。因此当某节点的信道状态很差时，中继节点选择不给该节点传输数据是更好的行动。即对于存在状态c=0的所有系统状态，本文均可以将其所选择的行为直接定义为不为其传输数据，通过这种定义就可以达到缩减行动集的目的。直接定为不为其传输数据。由于可以减少行动集的选择。不通顺，请作相应调整。

4.3计算量分析

本方案提出了状态聚合及行动集缩减的近似最优策略求解方法。根据上文分析可以知道，在系统中存在两个需要传输数据的节点，其上层数据到达率相同，且节点所对应的缓存器长度均为5，信道状态分为4种状态时，逐次逼近法的系统状态数为SS=576，其状态行为对应矩阵规模为TS=4032，而在使用了状态聚合及行动集缩减后的系统状态数为SS′=361，状态行为对应矩阵规模为TS′=2377；而W学习算法的系统状态数为SW=24，状态行为对应矩阵规模为TW=96，在使用了状态聚合及行为集缩减后的系统状态数为SW′=19，状态行为对应矩阵规模为TW′=55。可以得到，通过使用状态聚合及行为集缩减，逐次逼近法的空间存储压缩率为41%，W学习算法的空间存储压缩率为43%。同时在仿真分析中可以看出，使用状态聚合及行为集缩减对逐次逼近法及W学习算法的性能影响极小，但却大幅度缩减了计算量。

5仿真结果与分析

为了评估W学习算法在本系统中的性能，本文定义了三种算法来同本方案进行比较，同时将逐次逼近法得到的近似最优策略视为系统的最优策略，此外通过引入状态聚合法及行动集缩减来在不影响算法性能的基础上减少迭代计算量。仿真图中为了表示方便，将自己定义的3种算法简称为AL1、AL2和AL3；将W学习算法简称为WL，使用了状态聚合及行为集缩减后的W学习算法称为WL1；将逐次逼近法简称为SA，使用了状态聚合及行为集缩减后的逐次逼近法称为SA1。

定义1算法AL1选择尽力为节点传输数据，即首先中继节点选择为存储更多数据的缓存器传输数据，然后选择不超过缓存器内数据包的尽量大的调制方式，以此来传输尽量多的数据。

定义2算法AL2希望尽量降低能耗，选择为信道状态更好的节点传输数据，同时使用消耗能量最少的传输方式。

定义3算法AL3选择为存储更多数据的缓存器传输数据，而调制方式则随机选择。

在这里本文将逐次逼近法得到的结果视为系统的最优选择。在图3～5中，分别表示了3种简易算法：逐次逼近法、W学习算法以及使用了状态聚合的逐次逼近法和使用了行动集缩减的W学习算法在存在两个节点传输数据，缓存器长度为5，且两个缓存器的数据包到达率相同时，在不同数据包到达率下的丢包个数，消耗能量以及平均效用的比较。且两个缓存器的数据包到达率相同时的系统效用、丢包数量和消耗能量的比较。

图3为在不同数据到达率下几种算法传输所得到的系统效用，图3为两个缓存器的数据包到达率相同时几种算法在几种到达率下传输所得到的系统效用。从中可以看出，使用W学习算法能够得到比较好的系统效用。

6结语

本文通过在无线通信网络传输中引入W学习算法，使信息的传输达到智能化、合理化，并在此基础上构建了基于马尔可夫过程的系统模型，通过W学习算法来对节点的传输选择进行指导。同时，为了节省存储空间，加速算法收敛，本文提出了状态聚合法、行动集缩减。经过验证，可以发现W学习算法可以很好地对信息的传输进行指导，在兼顾信息丢包以及能量消耗的同时，相比逐次逼近法极大地缩减了计算量。在未来的工作中，将把系统拓展到分布式无线网络中，利用学习算法来对其智能传输进行研究。