自适应概率与稳定性 1-λ r(n)= n-λ ◆将上式代入drift公式，可得： n-1 a网=1-e贤- ③n→oo时，d(n)=? d(n)=λ-e-1 ◆只要λ<e-1,就能保证drift为负值。 若采用自适应的重传概率，只要λ<e-1, S-ALOHA的Backlog过程就是稳定的。 2020年秋季 26/106 无线互联网
自适应概率与稳定性 2020年秋季 26 / 106 无线互联网 � � = � − � � − � 将上式代入drift公式，可得： � � = � − �!� � − � � − � �!� � → ∞时，� � =？ � � = � − �!� 只要� < �!�，就能保证drift为负值。 若采用自适应的重传概率，只要� < �!� ， S-ALOHA的Backlog过程就是稳定的
但是.… 按照r=(1-)/(n-)来设置重试概率要求每个节点 都要精确知道系统当前的Backlog值和平均到达率。 ③怎么办？ ◆近似。 ◆由于n比λ重要，只需近似估计m的大小。 ?怎么近似？ ◆用一个估值Sk来近似k时隙系统的backlog。 通过可观察的系统行为来更新Sk。 ◆将1/Sk作为时隙k发送分组的概率。 。什么是“可观察的系统行为”？ ②如何“更新”？ 2020年秋季 27/106 无线互联网
但是… 2020年秋季 27 / 106 无线互联网 按照� = (� − �)/(� − �)来设置重试概率要求每个节点 都要精确知道系统当前的Backlog值和平均到达率。 怎么办？ 近似。 由于�比�重要，只需近似估计�的大小。 怎么近似？ 用一个估值��来近似�时隙系统的backlog。 通过可观察的系统行为来更新��。 将�/��作为时隙�发送分组的概率。 什么是“可观察的系统行为”？ 如何“更新”？
系统行为的反馈更新 ②什么是“可观察的系统行为”？ 0, idle Zk= 1, successful e, error ③如何“更新”？ Sk+1=Sk al(Zk=0)+bl (Zk=1)+cl(ZK=e) ②Zk=0意味着什么？之Backlog被高估了，故a=-1 ⑦Zk=1意味着什么？◆Backlog估得刚好，故b=0 ②Zk=e意味着什么？之Backlog被低估了，故c=1 ③最后，Sk+1调整得小于1了怎么办？ Sk+1 max{1,Sk al(zx=0)+bI[Zx=1)+cl(zg=e)} 2020年秋季 28/106 无线互联网
系统行为的反馈更新 2020年秋季 28 / 106 无线互联网 什么是“可观察的系统行为” ？ �� = g �, ���� �, ���������� �, ����� 如何“更新”？ ��.� = �� + �� ��)� + �� ��)� + �� ��)� �� = �意味着什么？ Backlog被高估了，故� = −� �� = �意味着什么？ Backlog估得刚好，故� = � �� = �意味着什么？ Backlog被低估了，故� = � 最后，��.�调整得小于1了怎么办？ ��.� = ��� �, �� + �� ��)� + �� ��)� + �� ��)�
但是..（Again?) 上述方案要求每个节点随时监控系统行为；很多应用场 景中这个要求太苛刻了。 ③怎么办？ ◆ 每个节点只根据自己的重传历史来估计Backlog。 ②什么叫“节点自己的历史”？ “我”的上一次（假定是第m次)尝试是否成功。 如果成功了呢？ ◆我刚才估计的Backlog可能正好， 也可能偏大，下一次不妨小一点。 如果不成功呢？ 我刚才估计的Backlog可能偏小， 下一次不妨大一点。 之Sm+1= Sm-b, successful AIMD; a·Sm collision 保证收敛。 2020年秋季 29/106 无线互联网
但是…(Again?!) 2020年秋季 29 / 106 无线互联网 上述方案要求每个节点随时监控系统行为；很多应用场 景中这个要求太苛刻了。 怎么办？ 每个节点只根据自己的重传历史来估计Backlog。 什么叫“节点自己的历史”？ “我”的上一次（假定是第�次）尝试是否成功。 如果成功了呢？ 我刚才估计的Backlog可能正好， 也可能偏大，下一次不妨小一点。 如果不成功呢？ 我刚才估计的Backlog可能偏小， 下一次不妨大一点。 ��.� = o �� − �, ���������� � p ��, ��������� AIMD； 保证收敛
指数退避 ③下面两个方案有何区别？ 个每个时隙都以1/Sm的概率尝试发送。 ②在第xm个时隙尝试发送；xm在[0，Sml之间均匀随机。 ◆它们是一码事。 O指数退避算法： 四冲突后，在随后的第xm个时隙重新尝试。 四xm在[0，Sm]之间均匀随机。 四Sm随着重试次数的增加指数上升。（若a=2,即为 “二进制指数倒退”算法) 2020年秋季 30/106 无线互联网
指数退避 2020年秋季 30 / 106 无线互联网 下面两个方案有何区别？ 它们是一码事。 每个时隙都以�/��的概率尝试发送。 在第��个时隙尝试发送； ��在[�, ��]之间均匀随机。 指数退避算法： 冲突后，在随后的第��个时隙重新尝试。 ��在[�, ��]之间均匀随机。 ��随着重试次数的增加指数上升。（若� = �，即为 “二进制指数倒退”算法）