中继激励算法可被需求节点用于促进中继协作转发，相关研究可分3类：博弈激励机制、信誉激励机制和虚拟货币激励机制。博弈论激励机制^[4]引入博弈思想刻画需求节点和中继节点之间的交互行为，从而寻找实现双方收益最大化的行为策略(包括资源分配策略与协作激励策略)。信誉激励机制^[5]依据某个节点参与中继的历史信息，计算得到其信誉值，其他节点据此决定是否为其提供中继服务。虚拟货币激励机制^[6-7]又称为“支付-补偿”算法，借鉴经济学公平交易思想，建立节点之间通行的虚拟货币，用于购买中继服务。需求节点应根据中继节点所消耗的资源量，支付等额的虚拟货币。若节点仅购买服务却不提供服务，将迅速耗尽虚拟货币而无法继续获取中继服务，从而促使节点参与协作转发。3类机制各有优劣，虚拟货币激励机制因更加易于实施，受到研究人员的高度重视。立足于此，本文将需求节点与中继节点之间的激励过程建模为基于虚拟货币的买卖模型^[8]，双方针对交易标的分别出价，按照预定协议进行交易，以实现激励自私中继的目的。

中继选择算法可被需求节点用于选出最佳中继参与业务转发，相关研究已大量涌现^[9-12]。根据选择出参与转发的中继个数分为单中继选择、多中继选择和自适应数目中继选择。根据转发路径的中继跳数，分为单跳中继选择和多跳中继选择。根据中继选择算法的执行方式可分为中心式中继选择和分布式中继选择。需要说明，任一中继选择算法均需基于某一优化目标(节点距离、发射功率、转发时延、信道容量等)构建相应的中继最优选择模型，采用特定的求解策略，实现最佳中继的可靠选择。鉴于此，本文综合考虑成交价格和分流容量构建基于双层规划^[13]的中继选择模型，采用联合动态规划和穷尽搜索的分类求解策略以快速求解上述模型，从而选择出性价比最佳中继实现业务子流到相应小区的迁移接入。本文算法将基于买卖模型的中继激励机制和基于双层规划的中继选择模型有机结合以联合解决上述两类问题，从而实现基于多流并发的拥塞小区内高速率业务需求保障目标。

如图 1所示，泛在无线环境是由各种类型的无线网络(如3G/4G/WiMAX等)重叠覆盖形成的泛在通信环境。这些网络在空中接口、组网方式、覆盖范围以及传输容量等方面具有巨大的异构特性，共同为散布其中的海量终端节点提供泛在的无线接入。在未来泛在无线环境下，多宿主场景将变得非常普遍，以解决拥塞小区内高速率业务保障问题。在典型的业务多宿主迁移场景中，需求节点因所在小区流量过载已无可用资源，故而需将高速率业务分成多个子流并分别通过相邻中继转发，以接入到相应的邻近空闲小区。

图  1  多宿主场景图

需求节点置身泛在无线环境，周围存在大量中继节点可供协作转发，亦存在许多(同构或异构)空闲小区可供业务迁移。故设业务需求节点s位于拥塞小区A之中：小区A周围存在N个(同构或异构)空闲小区，记为$\mathit{\Gamma} = \{ {k_1}, {k_2}, \cdots, {k_N}\} $，相应的空闲小区基站集$D = \left\{ {{d_1}, {d_2}, \cdots, {d_N}} \right\}$。实际上，需求节点s往往不在空闲小区的覆盖范围之内或者与其采用异构的通信方式，故需中继转发才能接入上述小区。若某节点可与节点s通过WiFi直连技术形成Ad-hoc式连接，并可同时连接上述的空闲小区，则称之为节点s的中继节点；所有接入到空闲小区${k_i} \in \mathit{\Gamma} $的中继节点称为节点s的中继节点子集${R_{{k_i}}} = \{ {r_{{k_i}1}}, {r_{{k_i}2}}, \cdots, {r_{{k_i}{L_i}}}\} $，${L_i}$为相应中继节点的数目。则节点s的中继节点总集为$R = \{ {R_{{k_1}}}, {R_{{k_2}}}, \cdots, {R_{{k_N}}}\} $，且设任意两个中继节点子集相交为空集，即任一中继节点仅能接入一个空闲小区。

针对本文的上行业务场景，需求节点s需要将高速率业务(如VR视频直播)分流发送到多个不同中继子集的节点，经转发后分别传输到相应空闲小区，继而在核心网服务器实现业务流的汇聚。业务子流的无线传输路径由需求节点到中继节点的WiFi链路和中继节点到小区基站的蜂窝链路组成。由于WiFi链路采用WiFi直连技术，其传输容量假定始终大于业务子流速率，故业务子流传输路径的容量(简称分流容量)取决于相应瓶颈即蜂窝链路的容量。此外借助分布式感知技术，假定需求节点对中继节点和空闲小区的相关信息具有完全认知。假定所有中继均是自私且理性的，故采用适当的激励机制能够促使中继节点参与转发。由于同一子集${R_{{k_i}}}$内各中继节点到相应小区${k_i}$的信道状况差异明显，将信道带宽分别分配给多个中继节点同时接入小区方式的综合性能(容量和功率)远不如将信道带宽全部分配给某个(信道状况良好)中继节点单独接入小区的方式，故假定最多选择一个中继节点接入某一空闲小区。

首先，构建基于买卖模型的中继激励机制：中继节点根据自身消耗的功率资源量出价，需求节点根据相应的分流容量大小出价，两者按照既定规则进行交易，以激励中继节点参与转发。根据前面所述，分流容量${\nu _{{r_{{k_i}l}}{d_i}}}$(业务子流路径的传输容量)等于相应的中继节点${r_{{k_i}l}} \in {R_{{k_i}}}$到小区基站${d_i} \in D$的蜂窝链路容量。该指标表征了经过${r_{{k_i}l}}$的业务子流路径所能承载的最大业务速率，依据香农定理表示为：

式中，${w_{{k_i}}}$为空闲小区${k_i}$可分配的上行信道带宽；${p_{{r_{{k_i}l}}}}$为中继节点${r_{{k_i}l}}$愿意消耗的功率大小；${n_{{d_i}}}$表示链路接收端${d_i}$的高斯白噪声的功率谱密度；${\gamma _{{r_{{k_i}l}}{d_i}}}$为蜂窝链路的损耗系数。简单起见，${\gamma _{{r_{{k_i}l}}{d_i}}}$可表示为：

式中，${g_{{r_{{k_i}l}}}}$和${g_{{d_i}}}$分别表示${r_{{k_i}l}}$的发射天线增益和${d_i}$的接收天线增益，仿真中统一设为1；${\lambda _{{k_i}}}$为传输信号波长，根据小区${k_i}$的上行载波频率而定；${\zeta _{{r_{{k_i}l}}{d_i}}}$为${r_{{k_i}l}}$到${d_i}$的距离；$\phi $为衰落系数。

在买卖模型之中，虚拟货币作为买卖双方出价的衡量标尺，具有类似于真实货币的各类属性^[6-7]。为保证虚拟货币的可靠流通，该类货币应由第三方权威平台负责实时结算和精准记录。

作为买方，需求节点s显然期望各子流路径具有更大的分流容量，以承载其高速率业务需求。因此，分流容量越大，需求节点s相应出价越高。因此，需求节点s对中继节点${r_{{k_i}l}}$的出价表示为分流容量${\nu _{{r_{{k_i}l}}{d_i}}}$的递增函数形式：

式中，$\delta > 0$为调节因子，用于调节出价的取值尺度。

作为卖方，中继节点${r_{{k_i}l}}$期望付出较小的成本代价获取较高的虚拟货币。采用${r_{{k_i}l}}$愿意消耗的功率大小${p_{{r_{{k_i}l}}}}$作为衡量成本代价的指标。考虑实际情况，为保证${r_{{k_i}l}}$到${d_i}$满足最低通信要求，${p_{{r_{{k_i}l}}}}$应大于阈值${p^{\min }}$；为保证${r_{{k_i}l}}$不对其他小区通信造成干扰，${p_{{r_{{k_i}l}}}}$应小于阈值${p^{\max }}$。一方面，消耗功率越大，中继节点${r_{{k_i}l}}$相应要价越高，要价函数应包含${p_{{r_{{k_i}l}}}}$的递增函数部分；另一方面，为防止要价过高导致交易失败，反而无法获得虚拟货币，要价函数还应引入${p_{{r_{{k_i}l}}}}$的递减函数部分。故而，中继节点${r_{{k_i}l}}$对需求节点s的要价应表示为${p_{{r_{{k_i}l}}}}$的平缓递增函数：

式中，$\alpha $和$\beta $为非负权重因子；$\varphi \geqslant 1$为幂率因子。

在公平交易过程之中，讨价还价和价值一致是必须遵循的基本原则^[8]。由式(3)和式(4)可知，中继节点${r_{{k_i}l}}$和需求节点s分别从各自角度给出各自所认定的中继服务价值。买卖模型的关键在于通过讨价还价使得双方在价格承受范围之内对中继服务价值的认定趋于一致。趋于一致的中继服务价值即为成交价格，由基于双方出价的价值协商函数计算得到。

若${\text{pr}}_{{r_{{k_i}l}}}^y - {\text{pr}}_{{r_{{k_i}l}}}^s \leqslant 0$，则双方出价始终在对方价格承受范围之内，故总能达成交易。此时，价值协商函数：

此种情况下，成交价格${\text{pr}}_{{r_{{k_i}l}}}^y \leqslant {\text{pr}}_{{r_{{k_i}l}}}^c \leqslant \frac{{{\text{pr}}_{{r_{{k_i}l}}}^y + {\text{pr}}_{{r_{{k_i}l}}}^s}}{2}$，介于双方出价之间并偏向${\text{pr}}_{{r_{{k_i}l}}}^y$，符合交易过程以卖方为主导的实际情况。若$0 < {\text{pr}}_{{r_{{k_i}l}}}^y - {\text{pr}}_{{r_{{k_i}l}}}^s \leqslant {\theta _{\min }}$，由于双方出价非常接近且以卖方为主，故价值协商函数：

此种情况下，${\text{pr}}_{{r_{{k_i}l}}}^c$介于双方出价之间并等于${\text{pr}}_{{r_{{k_i}l}}}^y$。若${\theta _{\min }} < {\text{pr}}_{{r_{{k_i}l}}}^y - {\text{pr}}_{{r_{{k_i}l}}}^s \leqslant {\theta _{\max }}$，此时${\text{pr}}_{{r_{{k_i}l}}}^c$直接等于${\text{pr}}_{{r_{{k_i}l}}}^y$显然对于需求节点不够公平，故价值协商函数定义为：

此种情况下，${\text{pr}}_{{r_{{k_i}l}}}^c$仍然介于双方出价之间并偏向于${\text{pr}}_{{r_{{k_i}l}}}^y$。若${\text{pr}}_{{r_{{k_i}l}}}^y - {\text{pr}}_{{r_{{k_i}l}}}^s > {\theta _{\max }}$，此时双方差价过大，无法达成一致，交易失败。综合上述4种情况即可得到基于买卖模型的中继激励机制。需求节点针对中继节点子集${R_{{k_i}}}$各节点执行上述激励机制，即可得到初步成交中继节点子集${\text{C}}{{\text{R}}_{{k_i}}} = \{ {r_{{k_i}l}}|\forall {r_{{k_i}l}} \in {R_{{k_i}}}$且${r_{{k_i}l}}$达成交易}，进而得到初步成交中继节点总集${\text{CR}} = \{ {\text{C}}{{\text{R}}_{{k_1}}}, {\text{C}}{{\text{R}}_{{k_2}}}, \cdots, {\text{C}}{{\text{R}}_{{k_N}}}\} $，最后得到分流容量总集${\text{FR}} = \{ {\text{F}}{{\text{R}}_{{k_1}}}, {\text{F}}{{\text{R}}_{{k_2}}}, \cdots, {\text{F}}{{\text{R}}_{{k_N}}}\} $ (${\text{F}}{{\text{R}}_{{k_i}}} = \{ {v_{{r_{{k_i}l}}{d_i}}}| \forall {r_{{k_i}l}} \in {\text{C}}{{\text{R}}_{{k_i}}}\} $分流容量子集)和成交价格总集${\text{PR}} = \{ {\text{P}}{{\text{R}}_{{k_1}}}, {\text{P}}{{\text{R}}_{{k_2}}}, \cdots, {\text{P}}{{\text{R}}_{{k_N}}}\} $(${\text{P}}{{\text{R}}_{{k_i}}} = \{ {\text{pr}}_{_{{r_{{k_i}l}}}}^c|\forall {r_{{k_i}l}} \in {\text{C}}{{\text{R}}_{{k_i}}}\} $成交价格子集)。

根据前面所述，对于每个空闲小区，最多选择一个中继节点接入的方式具有更优异的综合性能。因此，构建基于双层规划的中继选择模型：由上层优化模型得到面向各空闲小区的性价比最佳中继节点集，由下层优化模型得到满足节点s的业务速率要求且总交易价格最低的中继集合，以最佳性价比实现业务多流并发迁移接入。

在上层优化模型中，性价比指标${\mathit{\Omega }_{{r_{{k_i}l}}}}$被用以衡量空闲小区${k_i}$内中继节点${r_{{k_i}l}}$提供中继服务的综合性能：

可以看出，${\mathit{\Omega} _{{r_{{k_i}l}}}}$综合考虑了${r_{{k_i}l}}$的成交价格和分流容量。进而，构建面向小区${k_i}$的上层中继选择模型：

式中，${\text{C}}{{\text{R}}_{{k_i}}} \subset {\text{CR}}$，${r'_{{k_i}}}$表示面向小区${k_i}$的最佳中继节点。对于各空闲小区分别执行上述模型，可得面向小区的最佳中继节点集${\text{OR}} = \{ {r'_{{k_1}}}, {r'_{{k_2}}}, \cdots, {r'_{{k_N}}}\} $。

由上层优化模型构建下层中继选择模型：

式中，$\nu _{{\text{req}}}^s$为需求节点s的业务速率要求；${\text{Z}}{{\text{R}}^*}$为满足业务速率需求且总成交价格最低的最终成交中继节点集。据此，需求节点s即可将业务分流到${\text{Z}}{{\text{R}}^*}$的各中继节点，从而最终实现多流并发迁移接入。

由前面可知，上层优化模型的最优解构成了下层优化模型的解空间，故被联合建模为双层规划模型^[13]。对于上层优化模型，直接采用穷尽搜索方法暴力求解。此时，需求节点的计算复杂度不超过$O((2L - 1)N)$(L为接入不同空闲小区的初步成交中继个数的最大值，N为空闲小区个数)，若由各小区基站分布式执行上层优化模型，则相应的计算复杂度不超过$O(2L - 1)$。由于L受实际中继个数所限，故上述解法的线性复杂度完全可以接受。

对于下层优化模型，直接采用暴力解法，需求节点的计算复杂度将超过$O({2^N})$，故而该优化问题是NP-Hard问题。为实现该优化问题的快速求解，引入一组N元0-1数值向量$({x_1}, {x_2}, \cdots, {x_N})$，将下层优化模型等价转化为0-1整数规划问题：

显然，如果采用穷尽搜索方法求解$\{ x_1^*, x_2^*, \cdots, x_N^*\} $，共有$2N \cdot {2^N}$次计算操作，计算复杂度为$O(2N \cdot {2^N}) = O(N \cdot {2^{N + 1}})$。显然，当N较大时，穷尽搜索方法的计算量将会迅猛增加。可以证明，上述问题具有递推特性，可被视为0-1背包问题，应利用动态规划方法^[14]加以求解。需将业务需求速率$v_{{\text{req}}}^s$以$\mathit{\Delta }$为量化间隔，使之成为离散整型量$\mathit{\Lambda} = \left[{\frac{{v_{{\text{req}}}^s}}{\mathit{\Delta} }} \right]$，$[\cdot]$表示取整运算。由此，可得动态规划的递推公式：

式中，$\left[{\frac{{{\nu _{{{r'}_{{k_i}}}{d_i}}}}}{\mathit{\Delta} }} \right]$表示分流容量${\nu _{{{r'}_{{k_i}}}{d_i}}}$的量化整型量，$\ell (0, j) = + \infty, j > 0$且$\ell (i, j) = 0, {\text{ }}j \leqslant 0$。根据式(12)，可得以i为行以j为列的$\ell (i, j)$的二维递推表。若$\ell (i, j) = \ell (i - 1, j)$，则表明$x_i^* = 0$；若$\ell (i, j) = \ell \left( {i - 1, j - \;\left[{\frac{{{\nu _{{{r'}_{{k_i}}}{d_i}}}}}{\mathit{\Delta} }} \right]} \right) + {\text{pr}}_{{{r'}_{{k_i}}}}^c$，则表明$x_i^* = 1$；若三者均相等，则$x_i^* = 0$和$x_i^* = 1$均可。依据上述规则，可对二维递推表通过反向判断方式，最终获得全局最优解$(x_1^*, x_2^*, \cdots, x_N^*)$。

故动态规划方法的整体计算复杂度为$O(N(\mathit{\Lambda} + 1))$。考虑到前述穷尽搜索方法计算复杂度为$O(N \cdot {2^{N + 1}})$，则$N \geqslant {\log _2}(\mathit{\Lambda} + 1) - 1$时，动态规划方法效率更高；反之，则穷尽搜索方法效率更高。

综上，采用分类求解策略求解本文的双层规划模型：对于上层优化模型，直接采用穷尽搜索方法求解；对于下层优化模型，当$N \geqslant {\log _2}(\mathit{\Lambda} + 1) - 1$时，采用动态规划方法求解，反之则采用穷尽搜索方法求解。

综上所述，本文算法的流程为：

1) 初始化网络场景，形成多空闲小区(个数为N)、多中继节点的泛在通信场景；初始化系统参数：各空闲小区的${w_{{k_i}}}$、${n_{{d_i}}}$、${g_{{d_i}}}$和${\lambda _{{k_i}}}$，各中继节点的${p_{{r_{{k_i}l}}}}$、${g_{{r_{{k_i}l}}}}$、${\zeta _{{r_{{k_i}l}}{d_i}}}$和$\phi $，需求节点的$\nu _{{\text{req}}}^s$；初始化算法参数：$\delta $、${p^{\min }}$、${p^{\max }} \alpha $、$\beta $、$\varphi $、${\theta _{\min }}$、${\theta _{\max }}$、$\mathit{\Delta }$。相关节点均通过分布式感知获得上述信息。

2) 一旦需要业务迁移，需求节点根据式(1)~式(3)出价，中继节点根据式(4)出价，两者根据式(5)~式(7)分布式执行基于买卖模型的激励机制，由此得到初步成交中继节点总集CR、分流容量总集FR和成交价格总集PR。

3) 需求节点通知各空闲小区基站根据式(8)~式(9)分布式建立上层优化模型，并采用穷尽搜索方法求解，得到面向小区的最佳中继节点集OR。

4) 需求节点根据式(11)建立下层优化模型，根据N的大小选择穷尽搜索方法或者动态规划方法求解，得到$(x_1^*, x_2^*, \cdots, x_N^*)$。

5) 需求节点根据OR和$(x_1^*, x_2^*, \cdots, x_N^*)$，采用达成一致的成交价格激励相应的中继节点实现多流接入，从而以最佳性价比保障自身高速率业务需求。

在规定范围的矩形区域内通过随机方式部署网络小区和网络节点，异构小区之间重叠覆盖，确保需求节点的临近空闲小区平均数N=8，各空闲小区的相应中继节点数服从[10, 20]的均匀分布。相关参数设置如表 1所示。本仿真基于蒙特卡罗方法，并通过Java语言实现。所有数据点均为10次仿真结果的平均值。

由于每个节点均假定为自私的，故采用自私性(selfishness)表示中继节点拒绝合作的概率。各中继节点以该概率决定合作与否。若节点自私性小于某一阈值，则视为合作节点，反之视为非合作节点，仿真中该阈值设为0.4。假设所有节点的初始虚拟货币数为1 000 units，合作节点和非合作节点初始化为各占节点总数的50%(即相应的节点密度均为0.5)，合作节点和非合作节点的自私性分别初始化为0.2和0.8。此外，当任一节点提供中继服务后而未获得激励，其合作意愿均会降低，即节点自私性提高(仿真中，每次提高0.1)，从而导致合作节点转化为非合作节点。图 2给出了在没有执行中继激励机制情况下合作节点和非合作节点的节点密度随小区节点数的变化比较。小区节点数越多意味着小区拥塞可能性提高，希望业务迁移的需求节点随之增加。如图 2所示，当节点数较少时，需求节点将很少，中继节点提供中继服务的机会和次数就会较少，因而相应的节点密度在初始值0.5左右；随着节点数增加，需求节点将增加，中继节点提供中继服务的机会和次数也会增加，在没有给予激励的情况下合作节点因自私性提高变为非合作节点，故而合作节点密度降低且非合作节点密度升高；随着节点数增大到一定数值，需求节点将很多，各中继节点提供多次中继服务后均将转换为非合作节点，即合作节点密度趋于0而非合作节点密度趋于1。显然，没有激励机制的中继服务无法持久，最终导致没有节点愿意提供中继服务，进而难以保证需求节点的业务体验。因此，引入本文提出的中继激励机制变得非常必要。

图  2  无激励机制下节点密度随小区节点数的变化

图 3给出了采用本文的中继激励机制在不同自私性下中继节点的平均收益(获得的虚拟货币数)随请求交易次数的变化。这里，假设所有中继节点的自私性均统一设为selfishness，请求交易次数指每个中继节点被请求提供服务的次数。如图 3所示，中继节点自私性越大，其实际参与交易的次数越小，因而所获收益越小；在自私性一定时，随着请求交易次数的增加，中继节点实际参与交易(提供服务)的次数增加，因而所获收益相应增加。显然，在继激励机制的刺激下，各中继节点的收获正比于付出，故而愿意提供中继服务，以便获得更多的虚拟货币。

图  3  不同自私性下中继节点平均收益随请求交易次数的变化

在初步验证了本文中继激励机制有效性的基础上，进一步构建3类比较算法(PEF算法、RPP算法和QRPS算法)以评估本文算法(基于激励机制的双层规划中继选择算法)的整体性能。PEF算法综合考虑了中继节点的能量代价和时延代价，采用基于转发补偿的定价激励机制^[15]，在此价格基础上，选择各小区性价比最佳的中继节点(参见3.2.1节)，从中选出若干性价比排序在前的中继节点，直到满足需求节点的业务速率为止。RPP算法采用基于发射功率和剩余能量比值的定价激励机制^[16]，以此价格为基础，采用同于PEF算法的中继选择方法。QPRS算法采用本文的基于买卖模型的定价激励机制(参见3.1节)，从每个小区各随机选择一个中继节点，并从中选出若干的中继节点，直到满足需求节点的业务速率为止^[17]。图 4给出了基于上述4类算法的需求节点支出随业务需求速率变化的比较结果。这里，4类算法均面向多宿主场景分别选择出各自中继节点集，以此为基础统一按照本文定价机制计算需求节点总支出，以保证在相同的指标下比较性能。图 5给出了基于4类算法的中继节点发射功率随业务需求速率变化的比较结果。这里，4类算法均面向多宿主场景分别选择出各自中继节点集，以此为基础计算集合内所有中继节点的发射功率之和。如图 4和图 5所示，随着业务需求速率的增加，基于4类算法的业务需求节点支出和中继节点发射功率均随之增加。比较4类算法可知，QPRS算法以随机方式选择中继节点集，相应地性能最差(需求节点支出和中继节点发射功率均最高)；PEF算法和RPP算法采用类似于本文3.2.1节方法(上层优化模型)选择性价比最佳的中继节点集，需求节点支出和中继节点发射功率性能均介于QPRS算法和本文算法之间；相比于PEF算法，RPP算法定价机制更加接近于本文算法(将发射功率作为主要定价因素)，故而RPP算法性能均优于PEF算法；相比3类比较算法，本文算法基于更加合理的定价激励机制，采用双层规划模型选择全局最优的中继节点集，故而在保障业务需求速率的前提下在需求节点支出和中继节点发射功率两个方面的性能表现均最佳。

图  4  需求节点支出随业务需求速率变化的比较

图  5  中继节点发射功率随业务需求速率变化的比较

面向泛在无线环境下多宿主场景，提出一种基于激励机制的双层规划中继选择算法，以解决拥塞小区内高速率业务需求保障问题。首先，将需求节点与中继节点之间的激励过程建模为基于虚拟货币的买卖模型，双方针对交易标的分别出价，按照预定协议进行交易。其次，综合考虑成交价格和分流容量构建基于双层规划的中继选择模型，采用联合动态规划和穷尽搜索的分类求解策略以快速求解上述模型，从而以最佳性价比激励中继节点实现多流并发迁移接入。最后，通过仿真验证了本文算法的有效性。