一种实现无线自组织网络链路公平性的退避参数设计方法

摘要

本发明公开一种实现无线自组织网络链路公平性的退避参数设计方法，其属于无线网络领域。本发明实现无线自组织网络链路公平性的退避参数设计方法包括如下步骤：步骤1：采用定长时隙马尔科夫链对DCF协议进行建模；步骤2：确定每个节点的冲突概率；步骤3：确定每个节点的挂起概率和挂起时间；步骤4：求解每条链路的吞吐量；步骤5：求解实现链路公平性的退避参数值。通过改进前后各条链路饱和吞吐量理论值与仿真值之间的对比，以及在实现加权公平性后各条链路饱和吞吐量仿真值和理论值之间的对比，说明了本发明退避参数设计方法的有效性。

主权项

1.一种实现无线自组织网络链路公平性的退避参数设计方法，其特征在于：包括如下步骤步骤1：利用定长时隙马尔科夫链对DCF协议进行建模；节点在定长时隙马尔科夫链中的状态用{i,j,k,l}表示；其中，j和k分别表示退避阶数和退避计数器的值；i有4个值（i=0、1、2、3），分别表示退避过程、成功传输过程、冲突过程和挂起过程；l表示当前过程剩余的时隙数；定义下述各变量含义：m：重传次数；D_s：发送成功过程时隙个数；D_f：发送失败过程时隙个数；p_f：节点挂起概率；p_c1：瞬时冲突概率；p_c2：持续冲突概率；W_i：第i个退避阶段竞争窗口值；M：挂起过程时隙个数；定长时隙马尔科夫链非空一步状态转移概率表示为：$\left\{\begin{array}{cc}p(0,j,k,k|0,j,k+1,k+1)=1-p_f\left(n\right)& 0\le j\le m,0\le k\le W_j-2\\ p(3,j,k,M\left(n\right)-1|0,j,k,k)=p_f\left(n\right)& 0\le j\le m,1\le k\le W_j-1\\ p(3,j,k,l|3,j,k,l+1)=1& 0\le j\le m,1\le k\le W_j-\mathrm{1,0}\le l\le M\left(n\right)-2\\ p(0,i,j,j|3,i,j+\mathrm{1,0})=1& 0\le i\le m,0\le j\le W_i-2\\ p(1,j,0,D-1|0,j,\mathrm{0,0})=1-p_{c1}\left(n\right)& 0\le j\le m\\ p(2,j,0,D-1|0,j,\mathrm{0,0})=p_{c1}\left(n\right)& 0\le j\le m\\ p(1,j,0,l-1|1,j,0,l)=1-p_{c2}\left(n\right)& 0\le j\le m,1\le l\le D-1\\ p(2,j,0,l-1|1,j,0,l)=p_{c2}\left(n\right)& 0\le j\le m,1\le l\le D-1\\ p(\mathrm{0,0},k,k|1,j,\mathrm{0,0})=1/W_0& 0\le j\le m,1\le k\le W_0-1\\ p(0,j+1,k,k|2,j,\mathrm{0,0})=1/W_{j+1}& 0\le j\le m-\mathrm{1,0}\le k\le W_{j+1}-1\\ p(\mathrm{0,0},k,k|2,m,\mathrm{0,0})=1/W_0& 0\le k\le W_0-1\end{array}\right.,---\left(2\right)$由上述转移概率得到节点n处在退避过程中的每个状态概率为$p(0,j,k,k)=\frac{(W_j-k){(1-p_s\left(n\right))}^{j}p\left(\mathrm{0,0,0,0}\right)}{W_j}(0<k\le W_j-\mathrm{1,0}\le j\le m),---\left(3\right)$其中p_s(n)表示成功发送一个数据包的概率，整个退避过程的概率表示为$\begin{array}{c}A\left(n\right)=\underset{j=0}{\overset{m}{\Sigma }}\underset{k=1}{\overset{W_j-1}{\Sigma }}p(0,j,k,k)\\ =\left\{\begin{array}{c}\frac{p\left(\mathrm{0,0,0,0}\right)}{2}[\frac{1-{\left(2(1-p_s\left(n\right))\right)}^{m+1}}{1-2(1-p_s\left(n\right))}{W}_0-\frac{1-{(1-p_s\left(n\right))}^{m+1}}{p_s\left(n\right)}]m\le m^{\prime }\\ \frac{p\left(\mathrm{0,0,0,0}\right)}{2}[\frac{1-{\left(2(1-p_s\left(n\right))\right)}^{m^{\prime }+1}}{1-2(1-p_s\left(n\right))}{W}_0-\frac{1-{(1-p_s\left(n\right))}^{m+1}}{p_s\left(n\right)}+\frac{W_{\max }[{(1-p_s\left(n\right))}^{m^{\prime }+1}-{(1-p_s\left(n\right))}^{m+1}]}{p_s\left(n\right)}]m>m^{\prime }\end{array}\right.\end{array}$(4)当退避计数器减到0时，节点发送数据包，因此，节点n在一个σ时隙内的发送概率为$\tau \left(n\right)=\underset{j=0}{\overset{m}{\Sigma }}p(0,j,\mathrm{0,0})=\frac{1-{(1-p_s\left(n\right))}^{m+1}}{p_s\left(n\right)}p\left(\mathrm{0,0,0,0}\right).---\left(5\right)$由于ACK长度远小于数据帧长度，可忽略不计，令D_s=D_f=D，则发送成功和发送失败过程中的每个状态的概率可以表示为$p(1,j,0,l)=\left\{\begin{array}{cc}p(0,j,\mathrm{0,0})(1-p_{c1}\left(n\right))& l=D-1\\ p(1,j,0,l+1)(1-p_{c2}\left(n\right))& 0\le l<D-1\end{array}\right.---\left(6\right)$和$p(2,j,0,k)=\left\{\begin{array}{cc}p(0,j,\mathrm{0,0})p_{c1}\left(n\right)& k=D-1\\ p_{c2}\left(n\right)\underset{l=k+1}{\overset{D-1}{\Sigma }}p(1,j,0,l)+p(2,j,0,D-1)& 0\le k<D-1\end{array}\right..---\left(7\right)$因此，节点n处在整个发送过程的概率为${\tau }^{\prime }\left(n\right)=\underset{j=0}{\overset{m}{\Sigma }}\underset{l=0}{\overset{D-1}{\Sigma }}p(1,j,0,l)+\underset{j=0}{\overset{m}{\Sigma }}\underset{l=0}{\overset{D-1}{\Sigma }}p(2,j,0,l)=D·\tau \left(n\right).---\left(8\right)$节点n处在挂起过程的每个状态概率可以表示为p(3,j,k,l)＝p_f(n)p(0,j,k,k) 0≤j≤m,0≤k≤W_j-1,0≤l≤M(n)-1.   (9)定义$p_1\left(n\right)=\frac{(1+M\left(n\right)p_f\left(n\right))}{2}---\left(10\right)$和$p_2\left(n\right)=D\frac{1-{(1-p_s\left(n\right))}^{m+1}}{p_s\left(n\right)}.---\left(11\right)$联立方程（4）、（5）、（8）和（9），利用归一化条件$\underset{j=0}{\overset{m}{\Sigma }}\underset{k=1}{\overset{W_j-1}{\Sigma }}p(0,j,k,k)+\underset{j=0}{\overset{m}{\Sigma }}\underset{l=0}{\overset{D-1}{\Sigma }}p(1,j,0,l)+\underset{j=0}{\overset{m}{\Sigma }}\underset{l=0}{\overset{D-1}{\Sigma }}p(2,j,0,l)+\underset{j=0}{\overset{m}{\Sigma }}\underset{k=1}{\overset{W_j-1}{\Sigma }}\underset{l=0}{\overset{M\left(n\right)-1}{\Sigma }}p(3,j,k,l)=1,---\left(12\right)$求出$\begin{array}{c}p\left(\mathrm{0,0,0,0}\right)\\ =\left\{\begin{array}{c}\frac{1}{p_1\left(n\right)[\frac{1-{(2-{2p}_s\left(n\right))}^{m+1}}{{2p}_s\left(n\right)-1}{W}_0-\frac{1-{(1-p_s\left(n\right))}^{m+1}}{p_s\left(n\right)}]+p_2\left(n\right)}m\le m^{\prime }\\ \frac{1}{p_1\left(n\right)[\frac{1-{(2-{2p}_s\left(n\right))}^{m^{\prime }+1}}{{2p}_s\left(n\right)-1}{W}_0-\frac{1-{(1-p_s\left(n\right))}^{m+1}}{p_s\left(n\right)}+\frac{W_{\max }[{(1-p_s\left(n\right))}^{m^{\prime }+1}-{(1-p_s\left(n\right))}^{m+1}]}{p_s\left(n\right)}]+p_2\left(n\right)}\end{array}\right.\end{array},m>m^{\prime }$(13)最后，定长时隙模型推导出发送节点n的链路吞吐量为$S=\frac{\tau \left(n\right)p_s\left(n\right)E\left[P\right]}{\sigma },---\left(14\right)$其中E[P]表示数据包的平均长度；步骤2：确定每个节点的冲突概率；在给定网络拓扑条件下，根据节点的传输范围、冲突干扰范围和物理载波检测范围确定每条链路的冲突情况，表示出每条链路的冲突概率；假设节点发起传输的第一个时隙中发生冲突的概率为pc1，在传输的过程中其余任意一个时隙中发生冲突的概率为pc2,两种冲突的表达式为$p_{c1}\left(n\right)=1-\underset{i\in \mathrm{ZI},j\in \mathrm{ZP}}{\Pi }(1-\tau \left(i\right))(1-{\tau }^{\prime }\left(j\right))---\left(15\right)$和$p_{c2}\left(n\right)=1-\underset{i\in \mathrm{ZP}}{\Pi }(1-\tau \left(i\right)),---\left(16\right)$其中，ZI、ZP分别为瞬时冲突和持续冲突干扰节点的集合，τ(i)为发送节点i在任一定长时隙上的发送概率，整个发送过程需占用D个时隙，当且仅当这D个时隙均无冲突产生时数据包才能发送成功，则节点n成功发送的概率可以表示为p_s(n)＝(1-p_c1(n))(1-p_c2(n))^D-1.   (17)步骤3：确定每个节点的挂起概率和挂起时间；计算p_f需要利用连续时间的马尔科夫链模型，假设每条链路的数据包到达率是服从均值为g(n)的泊松分布，数据包的平均传输时间为1/u(n)，网络中链路共存的所有情况构成了连续时间马尔科夫链模型的各个状态，每个状态的概率为$Q\left(B\right)=\left(\underset{n\in B}{\Pi }\frac{g\left(n\right)}{\mu \left(n\right)}\right)Q\left(\phi \right),---\left(18\right)$其中，n为状态B中任一条链路，表示没有节点发起传输的状态，由归一化条件可以得到：$Q\left(\phi \right)={\left[\underset{\mathrm{allB}}{\Sigma }\underset{n\in B}{\Pi }\frac{g\left(n\right)}{u\left(n\right)}\right]}^{-1}.---\left(19\right)$在连续时间马尔科夫链模型中，节点监听信道空闲的概率为e^-G(n)σ，其中G(n)表示节点n及其载波检测范围内所有节点的总的传输率，而在定长时隙马尔科夫链中，信道空闲的概率为(1-τ(n))(1-p_f(n))，结合两个表达式，节点n的挂起概率可以表示为$p_f\left(n\right)=1-\frac{e^{-G\left(n\right)\sigma }}{1-\tau \left(n\right)}.---\left(20\right)$G(n)的计算如下：G(n)＝g(n)+Σ_n′∈N(n)A(n′|n)g(n′),   (21)其中N(n)表示节点n的载波检测范围内的所有发送节点的集合，它的补集表示为A(n’|n)表示节点n可以发起传输的条件下，节点n载波检测范围内的节点n’也可发起传输的概率$A\left(n^{\prime }\right|n)=\frac{A(n^{\prime },n)}{A\left(n\right)}=\frac{\underset{H⋐\overline{N\left(n\right)\cup N\left(n^{\prime }\right)}}{\Sigma }\left(\underset{i\in H}{\Pi }\frac{g\left(i\right)}{u\left(i\right)}\right)}{\underset{H⋐\bar{N}\left(n\right)}{\Sigma }\left(\underset{i\in H}{\Pi }\frac{g\left(i\right)}{u\left(i\right)}\right)}.---\left(22\right)$A(n’,n)表示节点n’和n同时可以发送的概率，在连续时间马尔科夫链模型中，A(n)表示为$A\left(n\right)=\underset{H⋐\bar{N}\left(n\right)}{\Sigma }Q\left(H\right)=\frac{\underset{H⋐\bar{N}\left(n\right)}{\Sigma }(\underset{i\in H}{\Pi }g\left(i\right)/u\left(i\right))}{\underset{\mathrm{allH}}{\Sigma }(\underset{i\in H}{\Pi }g\left(i\right)/u\left(i\right))}.---\left(23\right)$下面改写方程（12）：(1+M(n)p_f(n))A(n)+D·τ(n)＝1,   (24)则挂起时间的计算如下：$M\left(n\right)=\frac{1-D·\tau \left(n\right)-A\left(n\right)}{p_f\left(n\right)}.---\left(25\right)$当节点n监听信道空闲时，只有当其持续冲突干扰范围内无干扰节点发送数据时，数据包才能发送成功，因此，在连续时间马尔科夫链模型中，节点n的链路上的吞吐量表示为s(n)＝A(n)g(n)(1-p_c2(n)).   (26)步骤4：求解每条链路的吞吐量；结合步骤1、2、3，利用定长时隙马尔科夫模型和离散马尔科夫模型，构建计算每条链路吞吐量的迭代算法；具体步骤如下：（1）.为每条链路设置一个g(n)的初值，根据数据包长度和传输速率计算出1/u(n)，接着利用连续时间马尔科夫链模型列出状态方程，根据方程（23）计算发送节点n监听信道空闲的概率A(n)；（2）.得到A(n)和g(n)之后，联立方程（5）、（13）、（17）、（20）和（25）计算出发送概率、冲突概率、挂起概率和挂起时间；（3）.然后根据方程（14）计算出每条链路的吞吐量，接着利用方程（26）更新g(n)，重复步骤（1）、（2）、（3），直到收敛得到最后结果；步骤5：求解实现链路公平性的退避参数值；由方程（5）、（13）和（14）可知，吞吐量的表达式可以写成W的一个单调函数，引入方程组$s\left(W_0^n\right)=s\left(W_0^i\right)i=\mathrm{1,2},...,k,---\left(27\right)$其中W₀ⁱ表示第i条链路的最小竞争窗口，确定一条链路的W₀ⁿ值，假设为第n条，改写方程（27），令$a\left(i\right)=\left\{\begin{array}{cc}{p}_1\left(i\right)\frac{1-{(2-{2p}_s\left(i\right))}^{m+1}}{{2p}_s\left(i\right)-1}& m\le m^{\prime }\\ p_1\left(i\right)\frac{1-{(2-{2p}_s\left(i\right))}^{m^{\prime }+1}}{{2p}_s\left(i\right)-1}& m>m^{\prime }\end{array}\right.---\left(28\right)$和$b\left(i\right)=\left\{\begin{array}{c}{p}_1\left(i\right)\frac{1-{(1-p_s\left(i\right))}^{m+1}}{p_s\left(i\right)}m\le m^{\prime }\\ p_1\left(i\right)\{\frac{1-{(1-p_s\left(i\right))}^{m+1}}{p_s\left(i\right)}-\frac{W_{\max }[{(1-p_s\left(n\right))}^{m^{\prime }+1}-{(1-p_s\left(n\right))}^{m+1}]}{p_s\left(n\right)}\}m>m^{\prime }\end{array}\right.,---\left(29\right)$可得$W_0^i=\frac{[1-{(1-P_s\left(i\right))}^{m+1}]E\left[P\right]}{s\left(W_0^n\right)\mathrm{\sigma a}\left(i\right)}+\frac{b\left(i\right)-P_2\left(i\right)}{a\left(i\right)}i=\mathrm{1,2},...,k,---\left(30\right)$具体实施在步骤4的第（2）步中，将W₀作为变量，引入方程（30），确定其中一条链路的W₀ⁿ，更新其余链路的W₀，然后转到第（3）步，最终得到每条链路的最小竞争窗口值，实现加权公平性采用下列方程：$\frac{s\left(W_0^i\right)}{s\left(W_0^n\right)}=\frac{w_i}{w_n}i=\mathrm{1,2},...,k,---\left(31\right)$其中w_i表示权重。