Page 164 - 《软件学报》2021年第8期

2446 Journal of Software 软件学报 Vol.32, No.8, August 2021

3.3 切换机制
在切换机制中包含了组主与组员之间的切换机制和组间不同组员的切换机制:前者是为了平衡组主的能
量消耗;而后者是让组员通过切换到一个更近的组主,减少发射功率从而降低能量消耗.
A. 组主切换机制
在第 2 节的 WiFi Direct 电量消耗的第 2 个测试中,实验结果显示,组主的消耗一直高于组员,并且设备的数
量越多,组主的消耗就越大.所以担任组主的设备在担任一定时间以后需要进行切换,尽量降低该设备的消耗.
文献[20]对设备的能耗和网络的效率进行了研究,提出了每 10min 进行一次设备切换,这个时间段被证实是平衡
能耗和效率的最佳值.因此在本文中,组主每 10min 切换一次,其过程如图 6 所示.

Fig.6 Switching process of group owner
图 6 组主切换过程

组主切换触发,每组的组员进行能耗排名,从能耗消耗最低的组员开始选择.如果该组员愿意成为组主,那
么该组员将成为新的组主;如果该组员不愿意充当组主以避免消耗过多的能耗,则自动选择下一个组员进行判
断;如果所有组员设备都不愿意充当组主,那么原有的组主将继续担任组主.当所有新组主被选出以后,广播给
其他所有的非组主设备,其他设备根据距离通过抢占的方式,加入距离自己最近的组主.
在确定新组主时,如图 6 所示,组员可能愿意成为新组主,也可能不愿意.这涉及到博弈.此外,每个组员都有
独立的选择,且组员的选择会影响最终的结果.因此,新组主的选择过程是一个 NP-Hard 问题.
问题 1. 在组主切换过程中,新组主的选择是一个 NP-Hard 问题.
证明,假设拥有 N 个容量为 C 的盒子,M 个大小为 s 的小球,且 s<C.求在不超过盒子容量 C 的前提下,每个
盒子中可以装多少个小球的所有组合.该问题显然是一个 NP-Hard 问题.在组主切换过程中,假设拥有 N 个组员
设备的为 C 的 WFD 通信组.其中,M 个设备愿意成为组主,s 个设备不愿成为组主,M+s=C.求所有情况下所有愿
意成为组主的组员的集合.这同样也是一个 NP-Hard 问题. □
在本文中,将采用纳什平衡(Nash equilibrium,简称 NS)来解决上述的 NP-Hard 问题.假设设备总数为 N,有设
备的意愿策略组 a n ={a 1 ,a 2 ,…,a n }∪N,a n 的初值为 1,且表示为
⎧ 1, 愿意成为宿主
a = ⎨ (8)
n
⎩ 0, 不愿意成为宿主
意愿策略组即设备是否想成为组主的意愿值集合.每个组员都有两个意愿决策值进行选择,且每个组员的
意愿决策值都初始化为 1.当组主切换发生之后,所有的组员节点按照能耗水平进行排名,从能耗最低的设备开
始进行判断.如果此时 a n 的值为 1,则当前设备愿意成为组主,且 a n 的值设为 0;如果此时 a n 的值为 0,该设备不愿
成为组主,将此时 a n 的值设为 1,并跳过当前的设备.在最坏的情况下,设备都不愿意成为组主,即 a n 的值都是 0.
但是通过纳什平衡,它们的值被设置为 1.在下一次的组主切换中,它们都希望成为新的组主.通过纳什平衡设置