Drift分析(1/3) Backlog的drift定义为：d(n)=E(Bk+1-Bk BK=n) 由发展方程可知：d(n):=E(Ak-DkBk=n) 为了求得这个均值，我们需要研究P(Ak一Dk Bk=n) ⑦若新到达分组数目Ak≥2，Dk=? ◆无论Backlog分组是否重试，Dk=0。 故有： am Pr(Ak -Dk mlBk =n)=e-, form≥2 m! 若新到达分组数目Ak=1,Dk=? 若新到达分组数目Ak=0,Dk=? 2020年秋季 21/106 无线互联网
Drift分析(1/3) 2020年秋季 21 / 106 无线互联网 Backlog的drift定义为：� � ≔ � ��.� − �� �� = � 由发展方程可知： � � ≔ � �� − �� �� = � 为了求得这个均值，我们需要研究�� �� − �� �� = � 若新到达分组数目�� ≥ �，�� =？ 无论Backlog分组是否重试， �� = �。 故有： �� �� − �� = � �� = � = �� �! �!� , ��� � ≥ � 若新到达分组数目�� = �，�� =？ 若新到达分组数目�� = �，�� =？
Drift分析(2/3) 若新到达分组数目Ak=1,Dk=? ◆ 若所有Backlog都不重试，Dk=1,Ak-Dk=0 若至少1个Backlog重试，Dk=0,Ak-Dk=1 ◆故有： P(Ak-Dk=1|Bk=n)=e-(1-(1-r)) 若新到达分组数目Ak=0,Dk=? 若所有Backlog都不重试，Dk=0,Ak-Dk=0 若超过2个Backlog重试，Dk=0,Ak-Dk=0 ◆ 若刚好只有1个Backlog重试，Dk=1,Ak-Dk=-1 故有： Pr(Ak-Dk =-1Bk =n)=e-inr(1-r)n-1 2020年秋季 22/106 无线互联网
Drift分析(2/3) 2020年秋季 22 / 106 无线互联网 若新到达分组数目�� = �，�� =？ 若新到达分组数目�� = �，�� =？ 若所有Backlog都不重试，�� = �,�� − �� = � 若至少1个Backlog重试，�� = �,�� − �� = � 故有： �� �� − �� = � �� = � = ��!� � − � − � � 若所有Backlog都不重试，�� = �,�� − �� = � 若超过2个Backlog重试，�� = �,�� − �� = � 若刚好只有1个Backlog重试，�� = �,�� − �� = −� 故有： �� �� − �� = −� �� = � = �!��� � − � �!�
Drift分析(3/3) 求均值，可得： d(n)=-Pr(Ak -Dk =-1|Bk n) +Pr(Ak-Dk =1Bk =n) +mPr(Ak -Dk =mlBk =n) =-e1-ra+7) 任给入，r>0,足够大后，上式取值必为正值。 ◆换句话说，{Bk}不稳定。 ①S-ALOHA会导致很大的Backlog,且会持续增加下去。 2020年秋季 23/106 无线互联网
Drift分析(3/3) 2020年秋季 23 / 106 无线互联网 求均值，可得： � � = −�� �� − �� = −� �� = � +�� �� − �� = � �� = � +��� �� − �� = � �� = � = � − �!� � − � � � + �� � − � 任给�, � > �，�足够大后，上式取值必为正值。 换句话说，{��}不稳定。 S-ALOHA会导致很大的Backlog，且会持续增加下去
问题出在哪里？ ⑦回忆一下，我们的描述中哪点有问题？ ◆ 重传概率不能是恒定的，应该是自适应的。 ③什么叫做“自适应”？ ◆Backlog越多，重传概率应该越小。 ③这样就一定能保证稳定吗？ ◆我们来看一个分析。 2020年秋季 24/106 无线互联网
问题出在哪里？ 2020年秋季 24 / 106 无线互联网 回忆一下，我们的描述中哪点有问题？ 重传概率不能是恒定的，应该是自适应的。 什么叫做“自适应”？ Backlog越多，重传概率应该越小。 这样就一定能保证稳定吗？ 我们来看一个分析
成功概率 已知Backlog分组数目为n的条件下，成功传送（无冲突） 的概率Ps(n)等于多少？ 只有两种情况可以保证成功传送： 个只有一个新到达分组，且所有Backlog不重试。 概率=？之e-(1-r)n 2 没有新到达，且只有一个Backlog重试。 概率=？ 之e-nr(1-r)n-1 Ps(n)=Ae4(1-r)n+e-inr(1-r)n-1 ?使得Ps(n)达到最大值的r为多少？ 求导并令之为0，解得： 1-λ 随着n的增加，r会 r(n) n-λ 变小：自适应。 2020年秋季 25/106 无线互联网
成功概率 2020年秋季 25 / 106 无线互联网 已知Backlog分组数目为�的条件下，成功传送（无冲突） 的概率�� � 等于多少？ 只有两种情况可以保证成功传送： 只有一个新到达分组，且所有Backlog不重试。 没有新到达，且只有一个Backlog重试。 概率=？ ��!� � − � � 概率=？ �!��� � − � �!� �� � = ��!� � − � � + �!��� � − � �!� 使得�� � 达到最大值的�为多少？ 求导并令之为0，解得： � � = � − � � − � 随着�的增加，�会 变小：自适应