Backlog 考虑S-ALOHA系统中的某个时隙k。 四Ak:slot k新到达的分组数目。 四Bk:slot ki开始时等待重传的包数目(Backlog)。 四Dk:slot k中离去的分组。之显然，Dk∈{0,1} 同样很显然，Bk+1=Bk十Ak一DK 四假定新到达分组服从速率为λ的泊松过程。 四假定Backlog分组在每个时隙尝试重传的概率都是r。 {Bk}构成DTMC。 ①下面的任务就是研究该DTMC的稳定性。 WHAT is it? WHY? HOW? 2020年秋季 16/106 无线互联网
Backlog 2020年秋季 16 / 106 无线互联网 考虑S-ALOHA系统中的某个时隙�。 ��：slot �新到达的分组数目。 ��：slot �开始时等待重传的包数目(Backlog)。 ��：slot �中离去的分组。 显然，�� ∈ {�, �} 同样很显然，��.� = �� + �� − �� 假定新到达分组服从速率为�的泊松过程。 假定Backlog分组在每个时隙尝试重传的概率都是�。 {��}构成DTMC。 下面的任务就是研究该DTMC的稳定性。 WHAT is it？ WHY？ HOW？
WHAT D马氏链若存在稳态概率分布，则称之为稳定的。 关于马氏链稳态分布的几个结论。 四不可约非周期的齐次马氏链必然存在极限分布。 即：π；=limπ}。其中π}表示时刻n发现系统 m→00 处于状态的概率。 四对于transient马氏链，或零常返马氏链，有πj=0。即 不存在稳态分布。 四对于正常返马氏链，有π；>0。即存在稳态分布{π}。该 分布由下述方程组唯一确定： 1=∑n,西=∑P刚 四有限状态马氏链必存在稳态分布。 2020年秋季 17/106 无线互联网
WHAT？ 2020年秋季 17 / 106 无线互联网 马氏链若存在稳态概率分布，则称之为稳定的。 关于马氏链稳态分布的几个结论。 不可约非周期的齐次马氏链必然存在极限分布。 即：�� = lim �→5 �� �。其中�� �表示时刻�发现系统 处于状态�的概率。 对于transient马氏链，或零常返马氏链，有�� = �。即 不存在稳态分布。 对于正常返马氏链，有�� > �。即存在稳态分布{��}。该 分布由下述方程组唯一确定： � = P � �� , �� = P � ����� 有限状态马氏链必存在稳态分布
WHY ③不存在稳态分布意味着什么？ ◆任何有限取值的状态都是不可能的（概率为0）。 ③这又意味着什么？ ◆状态取值趋于无穷。 我们的问题中，B}不稳定意味着什么？ Backlog分组的数目会不断累积，趋于无穷，永远没 机会被正确、无误地传输。 ◆这正是我们担心的，也正是我们想要研究的。 2020年秋季 18/106 无线互联网
WHY？ 2020年秋季 18 / 106 无线互联网 任何有限取值的状态�都是不可能的（概率为0）。 不存在稳态分布意味着什么？ 这又意味着什么？ 状态取值趋于无穷。 我们的问题中，{��}不稳定意味着什么？ Backlog分组的数目会不断累积，趋于无穷，永远没 机会被正确、无误地传输。 这正是我们担心的，也正是我们想要研究的
HOW?(1/2) 最容易想到的方法：研究方程组的解。 ◆若解为正值，就是正常返的，存在稳态分布。 很遗憾，多数情况下该方法intractable(方程数目无穷) 另一个思路：研究状态变量的Lyapunov函数。 更具体地说，是研究下面这个东西： E(f(Xn+1)-f(Xn)Xn=i3, 或者E{f(X+1)川Xn=i-f() 马氏链稳定性的研究中，通常取f(x)=x。即研究下式： d(i):E(Xn+1-XnlXn =i} ◆这个量称为drit。 2020年秋季 19/106 无线互联网
HOW？(1/2) 2020年秋季 19 / 106 无线互联网 最容易想到的方法：研究方程组的解。 若解为正值，就是正常返的，存在稳态分布。 很遗憾，多数情况下该方法intractable(方程数目无穷)。 另一个思路：研究状态变量的Lyapunov函数。 更具体地说，是研究下面这个东西： �{� ��.� − �(��)|�� = �}， 或者� � ��.� �� = � − �(�) 马氏链稳定性的研究中，通常取� � = �。即研究下式： � � : = �{��.� − ��|�� = �} 这个量称为drift
HOW?(2/2) d(i):E(Xn+1-XnlXn=i} ⑦若drift大于0，意味着什么？ ◆从时刻开始，系统状态取值趋于增大。 ◆直觉上，该马氏链不存在稳态分布。 ◆事实上，有定理表明，这一直觉是正确的。 ◆而且反向的定理（dit小于0则稳定)也存在。 ①因此，我们只需研究{Bk}的drift的取值符号，就可 确定{Bk}的稳定性。 2020年秋季 20/106 无线互联网
HOW?(2/2) 2020年秋季 20 / 106 无线互联网 � � : = �{��.� − ��|�� = �} 若drift大于0，意味着什么？ 从时刻�开始，系统状态取值趋于增大。 直觉上，该马氏链不存在稳态分布。 事实上，有定理表明，这一直觉是正确的。 而且反向的定理（drift小于0则稳定）也存在。 因此，我们只需研究 �� 的drift的取值符号，就可 确定 �� 的稳定性