一种面向异构无线网络环境的网络选择方法

摘要

本发明提出一种面向异构无线网络环境的网络选择方法，具体为：(1)将接入同一网络的所有用户及未被网络接入的单个用户视为联盟，并建立多业务效用函数；(2)根据(1)获得的效用函数及所有用户集合建立联盟博弈模型；(3)引入用户享乐偏好，将上述模型构建为享乐联盟形成博弈模型；(4)基于享乐偏好建立换位规则，各用户根据该规则进行分布式联盟形成；(5)联盟形成收敛于稳定的联盟结构，该结构给出了网络选择的结果；(6)周期性的更新联盟形成过程，以自适应异构无线环境的动态变化。本发明所阐述的方法具有分布式、动态化与环境自适应性等优点，能够获得较好的异构系统总效用与用户接纳总数，并趋近于异构系统总效用的最大值。

说明书

技术领域

本发明涉及无线通信技术领域，具体涉及一种异构无线网络的网络选 择方法。

背景技术

随着通信技术的飞速发展，接入网络呈现出多种无线接入技术共存的 异构无线网络环境。为了克服无线通信中资源的限制，满足任何时间、任 何地点、任何业务的接入需求，提供不同QoS、高速率的IP多媒体业务， 实现融合化的异构无线网络(heterogeneous wireless networks)已经成为无 线通信技术发展的必然趋势。

在无线异构环境下，对一个具备接入多种网络的多模终端用户而言， 实现无缝服务链接的关键在于如何在多重覆盖区域选取最优的网络进行接 入。这是因为，不同的候选网络在其架构，信号条件，服务质量保障等方 面皆有不同，选取非最优的网络可能导致更差的服务体验或者更高的服务 代价。为此，网络选择是异构无线网络中的核心问题。

近年来，网络选择方法与机制的研究热点在于，一方面，为了适应无 线环境高度的动态性，要求网络选择机制亦具有较高的动态性；另一方面， 凭借低复杂度的优点及不依赖于任何对各网络进行协调的中央控制设施， 网络选择正逐渐从中心化走向分布式，从网络端决策走向用户端驱动。

发明内容

本发明的目的在于提出一种面向异构无线网络环境的网络选择方法， 该方法首次将联盟形成的视角引入到异构网络领域，具有分布式，动态化 的特点，降低了网络选择的复杂度，同时能够通过联盟形成的自组织过程， 动态化的适应无线环境的复杂变化，提升异构系统总效用与最大接纳用户 总数，并极其趋近异构系统总效用的最大值。

一种面向异构无线网络环境的网络选择方法，其特征在于，包含以下 步骤：

步骤1)将t时刻接入同一网络的所有用户或未被网络接入的单个用 户标记为联盟S_k，根据用户所请求的业务类型建立各联盟S_k的联盟总效用 函数v(S_k)；

步骤2)建立可转移效用的联盟博弈模型(N(t)，v(S_k))，N(t)为t时刻 请求服务的用户集合，依据公平性分配准则将联盟总效用函数v(S_k)分配给 联盟S_k内的用户，得到各用户的个体收益函数φ_n(S_k)；

步骤3)依据用户n∈N(t)的个体收益函数φ_n(S_k)设计用户n对联盟S_k的 偏好函数f_n(S_k)，依据偏好函数f_n(S_k)为用户n对任意两个其可能从属的联盟 S_α，S_β建立一个完备的、反身的、可传递的二元偏好关系S_α≥_nS_β，进而将联 盟博弈模型(N(t)，v(S_k))重构为享乐联盟博弈模型(N(t)，≥_n)；

步骤4)依据享乐联盟博弈模型(N(t)，≥_n)，用户n从当前从属的联盟 换位到一个更加偏好的联盟，依次迭代换位直至用户n不能冉换位到新联 盟；

步骤5)用户n选择在步骤4)迭代换位后的最终联盟对应的网络作 为目标接入网络。

进一步地，还包括步骤6)周期性的重复步骤4)与步骤5)的联盟换 位过程，以自适应异构无线环境的动态变化。

进一步地，所述联盟总效用函数v(S_k)表征用户向目标网络请求业务服 务的服务收益和服务代价。

一种面向异构无线网络环境的网络选择方法，其特征在于，包含以下 步骤：

步骤a)将t时刻接入同一网络的所有用户或未被网络接入的单个用 户标记为联盟S_k，根据用户所请求的业务类型建立各用户的个体效用函数 v_n(S_k)；

步骤b)建立不可转移效用的联盟博弈模型(N(t)，V(S_k))，N(t)为t时刻 请求服务的用户集合，V(S_k)是由联盟S_k内各用户的个体效用函数v_n(S_k)组成 的向量；

步骤c)依据用户n∈N(t)的个体效用函数v_n(S_k)设计用户n对联盟S_k的 偏好函数f_n(S_k)，依据偏好函数f_n(S_k)为用户n对任意两个其可能从属的联盟 S_α，S_β建立一个完备的、反身的和可传递的二元偏好关系S_α≥_nS_β记为≥_n，进 而将联盟博弈模型(N(t)，v(S_k))重构为享乐联盟博弈模型(N(t)，≥_n)；

步骤d)依据享乐联盟博弈模型(N(t)，≥_n)，用户n从当前从属的联盟 换到一个更加偏好的联盟，依次迭代换位直至用户n不能冉换位到新联盟；

步骤e)用户n选择在步骤d)迭代换位后的最终联盟对应的网络作 为目标接入网络。

进一步地，还包括步骤f)周期性的重复步骤d)与步骤e)的联盟换 位过程，以自适应异构无线环境的动态变化。

进一步地，所述个体效用函数v_n(S_k)表征用户向目标网络请求业务服务 的服务收益与服务代价。

本发明的技术效果体现在：

本发明所述的一种面向异构无线网络环境的网络选择方法，首次以联 盟形成的时间审视异构网络的网络选择问题，具有天生的动态性与分布式 特点，通过自组织成稳定的联盟结构，能够自适应无线系统的复杂环境变 化，诸如用户的移动，呼叫的生灭，业务类型的切换等，同时，相比传统 的基于接收信号强度(RSNS)的网络选择方法，能够大大提高系统的最大 用户通纳数目，提升系统的总体效用，并趋近于系统总效用的最大值。

附图说明

图1是本发明一种面向异构无线网络环境的网络选择方法流程图；

图2是一个异构无线网络系统实例示意图；

图3是多业务服务收益函数曲线图，图3a)为带宽为0-10000Kbps时的 多业务服务收益函数曲线图，图3b)是图3a)在带宽为0-900Kbps时的放大 情形；

图4是一个35个用户分布下的网络选择结果示意图；

图5是系统总效用值比较示意图；

图6为了应对异构系统的动态变化而进行的动态化网络选择过程示意 图；

图7动态变化后的网络选择结果示意图；

图8异构系统最大容纳用户数目的比较示意图。

具体实施方式

为了更清楚地体现本发明一种面向异构无线网络环境的网络选择方法 具体执行过程及优点，下面结合附图及具体实施例做进一步详细说明。显 然，所描述的实施例仅仅是本发明的一部分实施例，本领域普通技术人员 在没有付出创造性劳动的前提下所获得的所有其他实施例，都属于本发明 保护的范围。

图2给出了实施例所用的一个异构无线网络系统，包括如下K＝4个网 络：1个全球微波互联接入WiMAX网络，标记为网络1，即网络服务提 供商SP₁(不失一般性的，本发明假发每个网络都被一个网络服务提供商所 管理)，1个基于IEEE 802.11协议的无线局域网络WLAN，标记为网络3， 即SP₃，及2个相邻的宽带码分多址蜂窝网络WCDMA，分别标记为网络2， SP₂与网络4，SP₄，不同的网络k拥有不同的覆盖半径D_k与最大带宽B_k， 图2可以明显的看出该异构无线环境存在多重覆盖区域，表1给出了本实 施例采用的一个具体的网络参数值。在整个异构系统的覆盖范围内(即网 络1的覆盖范围内)，随机分布与动态变化的网络用户需要选取合适的目标 网络进行接入。把接入同一网络k的用户集合标记为联盟S_k，其中1≤k≤K， 把暂时被系统阻止接入的用户视为单身联盟S_k，其中k＞K。在本发明中“用 户”考虑的均为请求服务的活跃用户。

表1异构无线系统的网络参数

下面本发明建立用户效用函数，在本实例中，本发明将直接建立联盟 总效用函数v(S_k)：不失一般性的，本发明考虑每个SP_k都能提供三种业务 J＝{voice(语音)，data(数据)，video(视频)}，每个用户n向各个网络请求一种 业务服务j∈J，每个SP_k可以供给该用户R_n，k的带宽，这样的话可以定义如 下的服务收益函数u_j(R_n，k)：

$u_{\mathrm{data}}\left(R_{n,k}\right)=\frac{{\log }_2((R_{n,k}+15)/15)}{1.21}$

图3给出了上述3种业务的服务收益函数曲线。可以看到，该收益函 数的定义与业务特征密切相关，表征了不同业务在不同带宽条件下的用户 体验或服务满意水平。这样的话，对任意一个接入网络k的用户联盟S_k， 其中1≤k≤K，其服务收益总和可表达为：

$U\left(S_k\right)=\underset{n\in S_k}{\Sigma }{u}_j\left(R_{n,k}\right),$$\forall j\in J,$k＝1，2，...，K

接下来，考虑服务支付。每个服务提供商接纳一次用户呼叫，都收取 一个费用值，进一步的，采取一种差异化定价策略，即不同的SP_k对不同的 业务呼叫收取不同的费用值，例如，WCDMA网络对于高优先级的业务呼 叫，例如语音呼叫，可以收取低费用，类似的，WLAN网络更喜欢数据业 务，这些偏好可以通过差异化定价上得到体现，因此，可以定义如下的3×K 的价格矩阵P：

$P=\left(\begin{array}{ccc}{p}_1^{\mathrm{voice}}& ...& p_K^{\mathrm{voice}}\\ p_1^{\mathrm{data}}& ...& p_K^{\mathrm{data}}\\ p_1^{\mathrm{video}}& ...& p_K^{\mathrm{video}}\end{array}\right)$

其中表示网络k或网络服务提供商SP_k对每次来自用户的业务为j的 呼叫收取的费用。具体的，本实施例采用的一个价格矩阵为：

$P_{3\times 4}=\left(\begin{array}{cccc}0.04& 0.02& 0.08& 0.02\\ 2.5& 3.5& 2.0& 3.5\\ 3.5& 4.0& 3.0& 4.0\end{array}\right)$

最后，考虑信号接收强度(Received Signal Strength，RSS)对效用值函 数的影响。信号接收强度是异构网络网络选择中普遍采用的决策标准之一， 它可以体现网络信号的接收质量，显然，用户更愿意接入提供更高RSS的 网络。由于异构系统中不同的无线网络在最大发射功率与接收门限的差异， 为此，可参考文献，W.Shen and Q.A.Zeng，“Cost-function-based network  selection strategy in integrated wireless and mobile networks，”IEEE  Transactions on Vehicular Technology，vol.57，no.6，pp.3778-3788，November 2008.(融合化无线与移动网络下基于代价函数的网络选择策略，IEEE车载 技术汇刊，57卷第6期，2008年11月)定义一种相对信号接收强度(Relative  Received Signal Strength，RRSS)，网络k的RRSS定义如下：

${\mathrm{RRSS}}_k=1-\frac{\log \left(d_{n,k}\right)}{\log \left(D_k\right)},$其中k＝1，2，...，K

其中d_n，k是用户n到SP_k的距离。针对实施例，更低的RRSS显然会降低终 端用户的业务服务收益或者满意水平，为此，可以定义一个RRSS的减函 数，作为代价函数的第二部分。对任意一个用户联盟S_k，其中1≤k≤K，该 代价函数定义为：

$C\left(S_k\right)=\underset{n\in S_k}{\Sigma }(1-{\mathrm{RRSS}}_k(d_{n,k}+1))$

$=\frac{\log \left(\underset{n\in S_k}{\Pi }(d_{n,k}+1)\right)}{\log \left(D_k\right)}$

于是，对任意一个用户联盟S_k，本发明可以给出其联盟总效用函数如下：

该效用函数表征了任意一个用户联盟S_k在t时刻所获得的总效用值。其中， 第一项表示接入网络k的用户联盟获得的效用值为服务收益减去代价函数； 第二项表示用户没有被网络接入，即成为单身联盟时，其效用值为0，第三 项表示如果联盟S_k中存在处于网络k覆盖半径之外的用户，则该联盟不能 形成。注意到，本效用函数基于多业务服务收益或满意水平，接入支付， 接收信号强度代价函数三部分直接建立了一个联盟的总效用，不失一般性， 考虑其他参数及形式的效用函数模型也是可行的。

至此，建立了一个可转移效用联盟博弈模型(TU coalitional game)(N(t)， v(S_k))，其中效用v(S_k)也称为博弈模型的特征函数(characteristic function)， 对于可转移效用的联盟博弈，表征联盟S_k的总效用值可以在它的成员之间 以任意规则划分。因此，接下来需要定义一种公平性分配准则，以赋予每 个用户个体收益。常见的分配准则包括基于Nucleolus的最大最小化公平分 配解，Sharply Value分配等，在本实施例中，采取一种相对简单的平等公 平方案，即对每一个用户n∈S_k，其个体收益为：

${\phi }_n\left(S_k\right)=\frac{1}{\left|S_k\right|}(v\left(S_k\right)-\underset{m\in S_k}{\Sigma }v\left(\right\{m\left\}\right))+v\left(\right\{n\left\}\right)$

由于用户接入不同的SP_k会获得不同的特征函数值，根据联盟博弈论的定 义，SP_k需要视为该博弈模型的特殊用户，因此，联盟S_k(1≤k≤K)等价于 {SP_k，S_k}，而联盟S_k(k＞K)也可以表征为{SP₀，S_k}。最后，为了防止SP_k在 不同的联盟间跳动，也就是说，一个联盟内只能有一个SP_k，有v({SP_k1，SP_k2， S_k})＝0，对所有的k1，k2＝1，2，...，K。

注意到，在所定义的上述(N(t)，v(S_k))联盟博弈模型中，由于联盟代价及 对SP约束的存在，其大联盟，也就是所有用户和SP组成为一个联盟的情 形往往是不存在的，换句话说，该模型不具有超可加性，因此，该模型属 于联盟形成博弈(coalition formation game)，即往往在所有参与者中，最终 稳定结构是一些分离的小联盟，即联盟结构H(也可以称为一个联盟分割， 即H＝{S₁，...，S_r}，r为用户组成的联盟的总个数，包括接入网络的联盟和各个 单身联盟)。

接下来，引入享乐设置。在本实施例中，定义如下的二元偏好关系≥_n：

$S_{\alpha }{\ge }_n{S}_{\beta }\iff f_n\left(S_a\right)\ge f_n\left(S_{\beta }\right)$

其中S_α，是两个包含用户n的联盟，即n∈S_α且n∈S_β。f_n是对任意一 个用户n所定义的用户偏好函数，它表征了用户对从属于某联盟的偏好数 值。上述关系是指，用户n更愿意成为S_α的成员，或者至少，它对S_α与S_β的喜好是相同的。

在本实施例中，对任意的一个用户n及其所属于的联盟S_k使得n∈S_k， 定义如下的增量偏好函数f_n：

f_n(S_k)＝|S_k|·φ_n(S_k)-(|S_k|-1)·φ_m(S_k\{n})

其中用户m∈S_k\{n}，φ_n(S_k)，φ_m(S_k\{n})是出于联盟中的每个用户所获得的个 体收益值。

至此，上述所建立的网络选择联盟形成博弈(N(t)，v(S_k)被重构为一个享 乐联盟形成博弈(N(t)，≥_n)。

接下来，基于上述享乐联盟形成博弈定义享乐换位规则，进行分布式联 盟形成：给定一个当前的用户联盟结构或分割H＝{S₁，...，S_r}，任何一个用户 n决定离开它当前所属的联盟S_H(n)＝S_k，k∈{1，...，r}并加入另一个联盟 当且仅当S_g∪{n}＞_nS_H(n)。这样的话，{S_k，S_g}→{S_k\{n}，S_g∪{n}}， 且H→H′，H′表示每发生一个享乐换位操作所产生的新的联盟结构。注意， ＞_n表示严格的偏好关系，回顾上文定义的偏好关系与偏好函数，即

(|S_g|+1)·φ_n(S_g∪{n})-|S_g|·φ_m(S_g)＞

|S_k|·φ_n(S_k)-(|S_k|-1)·φ_m(S_k\{n})

根据步骤5的描述，各用户n根据该换位准则依次迭代进行换位，直至 没有用户能够进行再次换位，即联盟结构收敛于最终的结构H_f，且本实施 例得到的H_f是Nash稳定的。注意到，本实施例给出的换位规则能保证每 次的独立换位操作都能产生一个过去未曾访问过的新联盟结构，可以保证 迭代收敛。

显然的，H_f给出了网络选择的结果。其中，单身联盟S_k(k＞K)即{SP₀，S_k} 为暂时被异构系统阻塞的用户集合，亦即未接入用户；联盟S_k(1≤k≤K)即 {SP_k，S_k}内的用户，则选择网络k作为目标网络接入。图4给出了一种35 个随机分布用户在本实施例所给出的异构网络系统下的最终分布式自组织 成的稳定H_f，即网络选择结果。其中圆形，三角形与方形分别代表用户请 求的是语音，数据与视频业务，中空标示为接入1号WiMAX网络的用户， 实心标示为接入2号WCDMA网络的用户，十字标示为接入3号WLAN 网络的用户，其他为接入4号WCDMA网络的用户。该例予中不存在未接 入用户。且H_f下的4个联盟的总效用值分别为v(S₁)＝21.3238，v(S₂)＝9.2979， v(S₃)＝18.7035，and v(S₄)＝6.8542，因此，系统总效用值为56.1794，此时等于 该35个网络用户分布情形下的最优解(尽管最优解的获得为NP完全问题， 采用一种中心化搜索方法以获取最优解，但是该最优解仅在联盟总用户数 较小的情况下获得，当用户过多时，由于空间爆炸，搜索最优解将十分困 难，时间复杂度很高，直至几乎不可能获得)。为了验证本发明所采取的方 法能够使得系统总效用及其趋近于系统总效用的最大值，同时比W.Shen  and Q.A.Zeng，“Cost-function-based network selection strategy in integrated  wireless and mobile networks，”IEEE Transactions on Vehicular Technology，vol. 57，no.6，pp.3778-3788，November 2008.(融合化无线与移动网络下基于代 价函数的网络选择策略，IEEE车载技术汇刊，57卷第6期，2008年11月) 中介绍的单一的RSNS选择方法更好，本发明进行10000次蒙特卡洛实验， 即随机布撒用户位置，随机分配用户业务呼叫类型，通过逐渐增加用户数 量，记录中心化搜索给出的总效用值(仅在用户数在40个以内提供)最优 解，本发明给出的总效用值及RSNS方法给出的总效用值三者的关系，图5 给出了三者的比较关系，可以看到，本发明给出的方法远远优于RSNS方 法，同时及其趋近于最优解。

根据步骤6，以周期Γ更新上述联盟形成过程，即每个用户根据当前的 联盟结构(即上一周期收敛的联盟结构)重新依次迭代进行上述享乐换位 过程，直至收敛于新的稳定联盟结构。该步骤的目的在于动态化自适应无 线环境的复杂变化，例如，节点移动到新的位置，重新进行享乐换位后， 可能节点会离开当前联盟，进入更偏好的新联盟。对本发明所提出的异构 网络选择博弈而言，每一次换位操作，都相当于一次网络切换过程。为了 验证本发明所提出的方法对动态环境的自适应性，以图4给出的网络选择 结果记为时刻t₀，在[t₀，t₀+Δ·Γ]，其中Δ∈[1，25]的时间间隔内，考虑用户34 为车载用户，从t₀时刻的(0.6，02)匀速运动到(-0.6，0.2)位置，并在该过程 中两次却换他的业务类型，与此同时，一个步行用户15从(-0.11，-0.05)匀 速运动到(-0.11，0.07)，进一步的，当Δ＝6时，用户5结束呼叫，不再视为活 跃用户，当Δ＝16，一个用户36向系统发起语音接入请求。图6给出了面对 上述复杂动态情形下的[t₀，t₀+Δ·F]内基于本发明所提出的方法各相关用户如 何进行动态化网络重选择与切换以自适应上述变化，图7给出了Δ＝25，即 上述变化结束后的网络选择结果，将它与图4即动态变化前的网络选择结 果进行对比，可以看到，对大部分静态用户而言，他们的目标网络在此期 间没有发生变化，从而证明本发明所提出的方法可以避免频繁的网络切换， 节省不必要的切换开销。

最后，基于图5的蒙特卡洛实验场景，图8给出了本发明所提出的方 法对异构系统最大容纳用户数目(即能够接入的用户总数)的变化与比较 情况。可以看到，本发明所提出的方法相比于前文所述的RSNS方法能够 提高容纳用户数目。特别的，当网络运营商升级他们的网络后，例如图8中 SP₁将原表1的WiMAX网络升级为基于802.16m的，最大带宽为B₁＝ 30Mbps的网络后，系统最大容纳用户数能够得到大幅的，进一步的提升。