无线互联网 Handout05(续) Random Access 王晟 博士教授博导 2020年秋季无线互联网 1
Random Access 王晟 博士 教授 博导 无线互联网 Handout 05(续) 2020年秋季 无线互联网 1
NOTES 这部分内容来自以下参考书： Ishai Menache and Asuman Ozdaglar Network Games:Theory,Models,and Dynamics "synthesis lectures on communication networks",Morgan Claypool,2011 Chapter 4:Wireless Network Games 4.1:Noncooperative Transmission Scheduling in Collision Channels 2020年秋季 2/48 无线互联网
NOTES 2020年秋季 2 / 48 无线互联网 这部分内容来自以下参考书: Ishai Menache and Asuman Ozdaglar Network Games: Theory, Models, and Dynamics “synthesis lectures on communication networks”, Morgan & Claypool, 2011 Chapter 4: Wireless Network Games 4.1: Noncooperative Transmission Scheduling in Collision Channels
CONTENT 问题模型 2 门限策略 3 均衡分析：存在性 4 均衡分析：最佳性 5 均衡控制：BRD 6 小结 2020年秋季 3/48 无线互联网
CONTENT 2020年秋季 3 / 48 无线互联网 1 2 3 4 问题模型 门限策略 均衡分析: 存在性 均衡分析: 最佳性 5 均衡控制: BRD 6 小结
基本设定 假定： 四n个用户，上行通信. 四固定发射功率.没有功率控制功能 四只有“别人都不传输”时，你的传输才会成功： CSI:Channel State Information 四现行无线局域网的基础协议主要基于CSMA/ALOHA. ◆并不利用CS信息. @但802.11n标准已开始强调在MAC中利用CS1信息. ①本部分内容中，我们假定用户基于CS进行随机访问决策. 2020年秋季 4/48 无线互联网
基本设定 2020年秋季 4 / 48 无线互联网 �个用户, 上行通信. 假定: 固定发射功率. è没有功率控制功能. 只有“别人都不传输”时, 你的传输才会成功. CSI: Channel State Information 现行无线局域网的基础协议主要基于CSMA/ALOHA. 并不利用CSI信息. 但802.11n标准已开始强调在MAC中利用CSI信息. 本部分内容中, 我们假定用户基于CSI进行随机访问决策
关于CSI的假设 四每时隙开始时，用户获知信道状态信息 时隙k开始时用户获知的CS表示为ik∈2：CR+ 该值越大，则信道质量越好. 四2：表示用户可能经历的信道状态的取值集合，x:=|忆l 我们假定2为有限集合.2={z,z行，，z,z<z经<…<z 四假定8：全{5k}1是各态历经的马氏链；且i=1,,n之间相互独立.。 令π：表示马氏链3：的稳态概率矢量 π：的第m个分量π表示的是CSlz”∈2；的出现概率， 2020年秋季 5/48 无线互联网
关于CSI的假设 2020年秋季 5 / 48 无线互联网 每时隙开始时, 用户获知信道状态信息. 时隙�开始时用户�获知的CSI表示为��,� ∈ �� ⊂ ℝ$ 该值越大, 则信道质量越好. ��表示用户�可能经历的信道状态的取值集合, �� = �� 我们假定��为有限集合. �� = �� � , �� � , … , �� �� , �� � < �� � < ⋯ < �� �� 假定�� ≜ ��,� �(� ) 是各态历经的马氏链; 且��,� = �, … , �之间相互独立. 令��表示马氏链��的稳态概率矢量. ��的第�个分量�� �表示的是CSI �� � ∈ ��的出现概率
关于用户(1/2) 用户目标 四在确保吞吐量不低于P:的前提下，最小化功耗. 吞吐门限P:由用户的上层应用决定.假定为已知常量. 由于没有功控，因此减少功耗的手段只能是减少传输频率/概率。 假定用户永远有分组待传. 去掉用户需求的时变特性→单纯考察协议性能. 》用户策略 四用户i的平稳策略是一个映射：S:2→[0,1] 用户策略可表示为一个x维矢量：S1=(s品，s经，，s)∈[0,1]x 其中s表示：CS为z时用户i的传输概率 回例如：策略(0，…，0,1)表示一个特殊的策略：仅当CS最大时尝试传输 2020年秋季 6/48 无线互联网
关于用户(1/2) 2020年秋季 6 / 48 无线互联网 在确保吞吐量不低于��的前提下, 最小化功耗. 用户目标 吞吐门限��由用户�的上层应用决定. 假定为已知常量. 由于没有功控, 因此减少功耗的手段只能是减少传输频率/概率. 假定用户永远有分组待传. 去掉用户需求的时变特性è单纯考察协议性能. 用户策略 用户�的平稳策略是一个映射: ��:�� → �, � 用户策略可表示为一个��维矢量: �� = �� � , �� � , … , �� �� ∈ �, � �� 其中�� �表示: CSI为�� �时用户�的传输概率. 例如: 策略(�, … , �, �)表示一个特殊的策略: 仅当CSI最大时尝试传输
关于用户(2/2) 用户的传输概率/传输率 四给定策略S,给定信道马氏链3 用户在任意时隙的传输概率为：p(s)=∑=1s”πW )用户的平均速率/平均吞吐 四给定所有用户的策略s=(S1,S2,,S).[每个用户的传输概率都确定了] 用户传输成功的概率为：几i(1-p(s)） 四假定用户在信道状态zm下传输，其得到的平均吞吐(bps)为R:(z). 用户i的平均速率为：r:(s)=[∑=1s"πR(z)]·Π+i(1-p1(s)） 四博弈论习惯表达：1)称s为策略断面/组合profile. 2)用s-:表示策略断面中除用户之外的其他策略组合 →即：(，S-i)=s 2020年秋季 7/48 无线互联网
关于用户(2/2) 2020年秋季 7 / 48 无线互联网 给定策略��, 给定信道马氏链��. 用户的传输概率/传输率 用户�在任意时隙的传输概率为: �� �� = ∑�(� �� �� ��� � 用户的平均速率/平均吞吐 给定所有用户的策略� = ��, ��, … , �� . [每个用户的传输概率都确定了] 用户�传输成功的概率为: ∏�-� � − �� �� 假定用户�在信道状态�� �下传输, 其得到的平均吞吐(bps)为�� �� � . 用户�的平均速率为: �� � = ∑�(� �� �� ��� ��� �� � B ∏�-� � − �� �� 博弈论习惯表达: 1) 称�为策略断面/组合/profile. 2) 用�.�表示策略断面中除用户�之外的其他策略组合 è即: ��, �.� = �
小结一下 四用户选择不同的策略s=(s,s子，…，s) 会导致不同的传输概率：p:(s)=∑=1sπ 进而影响其吞吐：r(S,S-i) 四其目标是：保证r(s,s-)≥p的前提下，尽量减小p:(S)! ③用户可以通过自己的策略选择达到这个目标吗？ ◆不一定.别忘了，所有用户的决定是相互影响的 ②那么，在所有用户都各自决定其策略的情况下（没有中心控制，能否 达到一种“大家都满意”的状态？ ◆纳什均衡(NE:Nash Equilibrium)就是对这种状态的描述. 2020年秋季 8/48 无线互联网
小结一下 2020年秋季 8 / 48 无线互联网 用户选择不同的策略�� = �� � , �� � , … , �� �� 会导致不同的传输概率: �� �� = ∑�(� �� �� ��� � 进而影响其吞吐: �� ��, �.� 其目标是: 保证�� ��, �.� ≥ ��的前提下, 尽量减小�� �� . 用户�可以通过自己的策略选择达到这个目标吗? 不一定. 别忘了, 所有用户的决定是相互影响的. 那么, 在所有用户都各自决定其策略的情况下(没有中心控制), 能否 达到一种“大家都满意”的状态? 纳什均衡(NE: Nash Equilibrium)就是对这种状态的描述
NE 定义4.2[NE点] 四如果策略断面s满足条件：i,s1∈argmins,pi(si):r(S,s-i)≥pl 则称s为NE点. ©解读：NE是一个特殊的策略断面.该策略组合下，每个用户的吞吐约束 都能得到满足；并且没有用户可以“单方面”修改其策略来降低功耗。 四另一种解读：如果策略断面s中任一S都是s-的最佳反应，则s为NE. 给定“别人的策略组合”s-如果s满足定义中的条件，则我们称 S:是s-i的最佳反应(BR:Best Response). ONE是否存在？ 存在性、最佳性，以及均衡控制是所有 博弈模型中的三个核心问题 ②如果存在，是不是最好的？ 在研究这些问题之前，我们要先弄明白 ①如何达到最好的NE? 一类特殊的用户策略：门限策略. 2020年秋季 9/48 无线互联网
NE 2020年秋季 9 / 48 无线互联网 定义4.2 [NE点] 如果策略断面�满足条件: ∀�, �� ∈ �������/� �� �K� : �� �K�, �.� ≥ �� 则称�为NE点. 解读: NE是一个特殊的策略断面. 该策略组合下, 每个用户的吞吐约束 都能得到满足; 并且没有用户可以“单方面”修改其策略来降低功耗. 另一种解读: 如果策略断面� 中任一��都是�.�的最佳反应, 则�为NE. 给定“别人的策略组合” �.�, 如果��满足定义中的条件, 则我们称 ��是�.�的最佳反应(BR: Best Response). NE是否存在? 如果存在, 是不是最好的? 如何达到最好的NE? 存在性、最佳性, 以及均衡控制是所有 博弈模型中的三个核心问题. 在研究这些问题之前, 我们要先弄明白 一类特殊的用户策略: 门限策略
CONTENT 问题模型 2 门限策略 3 均衡分析：存在性 4 均衡分析：最佳性 5 均衡控制：BRD 6 小结 2020年秋季 10/48 无线互联网
CONTENT 2020年秋季 10 / 48 无线互联网 1 2 3 4 问题模型 门限策略 均衡分析: 存在性 均衡分析: 最佳性 5 均衡控制: BRD 6 小结