Threshold Strategy 定义4.5：Threshold Strategy 四门限策略是具有如下形式的平稳策略： S1=(0,0,,0,sm,1,1,,1), s"∈[0,1] 其中z”称为“CS门限”. 信道质量超过该门限，则必定传输； 信道质量低于该门限，则不传输； 信道质量刚好等于该门限，则以概率s传输； 门限策略的关键性质 ©门限策略听起来非常特殊，但其实基于它的分析不会失去一般性 Lemma4.6:假定所有用户都用平稳策略访问信道，则任意用户的 最佳反应一定是门限策略： 2020年秋季 11/48 无线互联网
Threshold Strategy 2020年秋季 11 / 48 无线互联网 门限策略是具有如下形式的平稳策略: �� = �, �, … , �, �� �� , �, �, … , � , �� �� ∈ [�, �] 定义4.5: Threshold Strategy 其中�� �� 称为“CSI门限”. 信道质量超过该门限, 则必定传输; 信道质量低于该门限, 则不传输; 信道质量刚好等于该门限, 则以概率�� �� 传输; 门限策略的关键性质 门限策略听起来非常特殊, 但其实基于它的分析不会失去一般性. Lemma 4.6: 假定所有用户都用平稳策略访问信道, 则任意用户的 最佳反应一定是门限策略
Lemma4.6(1/2) 证明：[参见CCIT Report#626;Jul小y2007] 四反证：假定有一个用户的最佳反应s,不是门限策略 则一定存在两个下标k,L,k<L,使得s>0,s<1. 概率 门限策略示意 四关键思路：增大s并减小s,[即让信道质量更好 的CS得到更高的传输概率]，新策略$：“更好”. 国Step#1:Vm∈z:-{k,I,令=s", cSl门限m: 下标 并令动=s-,=s1+片 概率1 非门限策略示意 传输概率不变：p(s)=∑M=1sπ=p:() 由于R:(z)单调增.平均速率变大了： 下标 r,s-i）=[M=1s0π0R(z)]Πji(1-p(s)<r(s-i) 换句话说，策略$：与S的目标值（传输频率功耗）一样， 但约束（吞吐下限P)“过分”满足了. 2020年秋季 12/48 无线互联网
Lemma 4.6(1/2) 2020年秋季 12 / 48 无线互联网 证明: [参见CCIT Report #626; July 2007] 反证: 假定有一个用户�的最佳反应��不是门限策略. 则一定存在两个下标�,�, � < �, 使得�� � > �, �� � < �. 概率 下标 1 门限策略示意 CSI门限�� 概率 下标 1 非门限策略示意 � � … 关键思路: 增大�� � 并减小�� � , [即让信道质量更好 的CSI得到更高的传输概率], 新策略�K� “更好”. Step#1: ∀� ∈ �� − �,� , 令�K� � = �� � , 并令�K� � = �� � − � �� � , �K� � = �� � + � �� � 传输概率不变: �� �� = ∑�(� �� �� ��� � = ��(�K�) 由于�� �� � 单调增. 平均速率变大了: �� ��, �.� = ∑�(� �� �� ��� ��� �� � B ∏�-� � − �� �� < �� �K�, �.� 换句话说, 策略�K�与��的目标值(传输频率/功耗)一样, 但约束(吞吐下限��)“过分”满足了
Lemma4.6(2/2) 证明：[续] Step#2:任选一个下标m,s>0.由Step#1的分析可知，必然存在 一个6>0，使得取=s”-6后，仍能满足吞吐约束，但功耗降低了. ◆这与“策略S是最佳反应策略”这一断言矛盾. 四证毕. NOTE: 四不用奇怪：这就是贪心算法的“exchange argument”. 门限策略就是求解用户目标的一种贪心算法而已. 回细究该引理的证明，有助于你理解门限策略的内涵 四更有助于理解BR的语义. 2020年秋季 13/48 无线互联网
Lemma 4.6(2/2) 2020年秋季 13 / 48 无线互联网 证明: [续] Step#2: 任选一个下标�, �� � > �. 由Step#1的分析可知, 必然存在 一个� > �, 使得取�K� � = �� � − �后, 仍能满足吞吐约束, 但功耗降低了. 这与“策略��是最佳反应策略”这一断言矛盾. NOTE: 证毕. 不用奇怪: 这就是贪心算法的“exchange argument”. 门限策略就是求解用户目标的一种贪心算法而已. 细究该引理的证明, 有助于你理解门限策略的内涵. 更有助于理解BR的语义
另一个有用的性质 Lemma4.7:门限策略与传输概率 一一映射 四先证：给定一个门限策略s,必有一个概率值p:∈[0,1]与之对应 直接用公式p:(s)=M=1sπ”算出来的那个就是. 即：p:=s元i+∑=m+1π 四再证：给定一个数P:∈[0,1]，必有一个门限概率s:与之对应 这也容易：累加稳态概率，看累加到哪个下标会超过p· 即：找到下标m:使得：2=m+10<p,且i=mπ”≥p: ◆这个下标就是CS门限的下标，而该门限上的策略为： smi p:-2=myt1π mi ①这意味着：每个平稳策略都可用一个标量来唯一表示， 2020年秋季 14/48 无线互联网
另一个有用的性质 2020年秋季 14 / 48 无线互联网 Lemma 4.7: 门限策略与传输概率一一映射. 直接用公式�� �� = ∑�(� �� �� ��� �算出来的那个就是. 先证: 给定一个门限策略��, 必有一个概率值�� ∈ [�, �]与之对应. 即: �� = �� �� �� �� + ∑�(��$� �� �� � 再证: 给定一个数�� ∈ [�, �], 必有一个门限概率��与之对应. 这也容易: 累加稳态概率, 看累加到哪个下标会超过��. 即:找到下标��使得: ∑�(��$� �� �� � < ��, 且∑�(�� �� �� � ≥ �� 这个下标就是CSI门限的下标, 而该门限上的策略为: �� �� = �� − ∑�(��$� �� �� � �� �� 这意味着: 每个平稳策略都可用一个标量��来唯一表示
课堂练习 四找到下标m使得：∑=m+1π<pu,且i=m,π≥pi 而该门限上的策略为： p1-20=m4+1r mi 已知：x:=4,即只有4种不同的信道状态：z}<z子<z<z ① 四稳态概率为：π=0.2，π=0.3，π=0.1，=0.4 ⑦给定p:=0.7,请问s=? @给定p:=0.45,请问s1=? ②给定p:∈[0.5,0.8]，请问s=? 2020年秋季 15/48 无线互联网
课堂练习 2020年秋季 15 / 48 无线互联网 找到下标��使得: ∑�(��$� �� �� � < ��, 且∑�(�� �� �� � ≥ �� 而该门限上的策略为: �� �� = �� − ∑�(��$� �� �� � �� �� 已知: �� = �, 即只有4种不同的信道状态: �� � < �� � < �� � < �� � 稳态概率为: �� � = �. �,�� � = �. �,�� � = �. �,�� � = �. � 给定�� = �. �, 请问�� =? 给定�� = �. ��, 请问�� =? 给定�� ∈ [�. �, �. �], 请问�� =?