基于层次分析法和熵理论的网络选择算法

2014-06-27 05:55麻少娟张继荣

陕西科技大学学报 2014年3期

麻少娟，张继荣

(西安邮电大学通信与信息工程学院，陕西西安 710121)

0 引言

随着移动互联网为用户提供更加多样化的服务，用户需要随时随地以最优质的互联网服务质量(QoS)和最低的成本接入无线网络.与此同时，各种无线技术相继出现，如IEEE802.11、WCDMA和LTE等无线网络为用户提供了各种各样的接入方式.此外，支持多种接入方式的移动终端也为用户提供了丰富的服务.因此，如何设计用户终端设备的网络选择算法，实现最佳连接(always best connected，ABC)成为当前的研究热点之一[1].

由于用户喜好、业务特性、网络资源可用性、网络负载等各方面的因素都会影响到网络的选择，片面的考虑一种因素会造成接入选择目标的偏颇和谬误.多属性决策方法(MADM)是解决网络选择问题的重要方法之一.它包含许多算法，如层次分析法(Analytic Hierarchy Process ,AHP)[2]、简单加权法(Simple Additive Weighting，SAW)[3]、模糊理论(Fuzzy Theory)[4]、灰色关联分析法(Grey relational analysis、GRA)[5]和接近理想方案的序数偏好方法(Technique for Order Preference by Similarity to an Ideal Solution, TOPSIS)[6]等.

文献[7]提出了一种主客观权重相结合的方法进行多属性的判决，在进行多参数决策时, 综合使用层次分析法和信息熵来确定网络参数的权重值.但是，在满足QoS为目标的网络选择时，该算法平均分配了每个QoS参数的权重值.文献[8]把层次分析和灰色关联评价方法结合起来，提出一种组合的无线异构网络选择算法，但是网络性能参数的权重具有一定的片面性，无法合理反映网络综合性能.

本文将AHP和熵理论结合起来，设计了一种动态无线异构网络选择算法，首先利用AHP算法对网络选择问题进行深入的剖析，构建网络选择问题的多级层次化模型并对各个属性参数指标进行主观赋权.其次是引入信息熵的理论求得判决属性对应的熵权作为各个参数指标的客观权重.最后是利用区分业务的TOPSIS算法将计算得出的相对接近度最高的网络作为当前的最优接入目标.

1 网络选择算法

终端在接入网络前，先判断用户偏好策略和当前的业务类型，以及实时检测当前所处的网络环境，搜集各个网络的QoS参数.终端中的网络选择模块根据实时QoS参数值，通过本文算法建立接入选择模型来选择在当前环境下的最佳网络.

1.1 层次分析法确定主观权重

20世纪70年代，美国运筹学家T.L.Satty提出了层次分析法，采用此方法可以有效地解决多属性判决问题.作为确定属性权重的常用方法之一，AHP体现出了业务需求和用户的主观喜好[9].

(1)建立递阶层次结构模型

按照AHP分析方法的步骤：首先考虑用户的偏好策略及分析当前的业务类型，建立网络选择的递阶层次结构.本文的判决准则中为了减少乒乓效应，采用文献[10]中的方法，引入历史偏好准则属性参数指标.层次结构模型如图1所示.

图1 层次结构模型

(2)构造标准化网络属性

由当前网络环境下的QoS参数值得到判断矩阵如式(1)所示.

A=(aij)m×n=

(1)

由于不同的属性，其量纲一般不同，首先需要对其做规范化处理，得出标准化决策矩阵B=[bij]m×n.

对于成本型属性(时延、时延抖动、丢包率、网络负载和费用)，按式(2)进行规范化处理，属性值愈小愈好.

(2)

对于效益型属性(比特率)，按式(3)进行规范化处理，属性值愈大愈好.

(3)

(3)建立属性偏好判断矩阵

确定网络参数，两两比较每个属性后，再按照

重要程度进行等级评定.

表1 网络参数对网络选择的重要性比值

注：2,4,6,8 表示两个元素相比，上述相邻判断的中间值.

矩阵C=[cij]n×n为偏好判断矩阵，其中cij表示参数i比参数j的重要性等级，满足条件：cij>0，cii=1且cij=1/cji(i,j=1,2,3,…,n).

由于客观事物的复杂性和用户认识的多样性，所比较的结果可能会出现前后不一致的现象，需要采用文献[11]中的方法对判断矩阵进行一致性检验.

(4)主观偏好权值的计算

在对判断矩阵进行一致性检验之后，各层的权值向量通过式(4)求得同层参数的权重：

(4)

再按照式(5)归一化处理：

(5)

1.2 信息熵确定客观权重

AHP算法中的主观倾向往往较重，判断矩阵的设计很大程度上依赖决策者的主观经验.熵权是一种客观赋权方法[12]，反应了各项参数指标的动态变化程度和参数指标之间的竞争关系，将熵权引入多属性方案中可以有效地消除主观随意性.

(1)由标准化判断矩阵B=[bij]m×n，计算网络属性的信息熵.

(6)

(7)

(2)计算网络属性的偏差度.

dj=1-Ej(j=1,2,3,…,n)

(8)

(3)计算权重向量.

(9)

1.3 确定属性的综合权重[13]

(10)

2 候选方案的排序

TOPSIS算法是为解决单个决策者的多目标问题而提出的一种接近线性加权法的排序方法，其基本思想是：所选择的满意方案应尽可能地接近正理想方案，同时又尽可能地远离负理想方案[14].

(1)将前文中的矩阵B转换为无量纲的标准化矩阵R，R中的元素rij为

(11)

(2)构造加权标准化判决矩阵.采用的标准化公式如下：

v=W×r

(12)

(3)确定理想解V+与负理想解V-

(13)

(14)

其中,J为效益型属性集合，J′为成本型属性集合.

(4)计算各候选方案到正负理想解的距离

(15)

(5)计算各个候选方案的相对接近度

(16)

3 问题建模

3.1 主观权重的建模分析

为了使得网络选择这一多属性判决问题清晰化，先根据用户策略建立第一级的层次化模型，再根据不同的业务QoS特征建立第二级的子层次化模型，最后，通过两级模型的嵌套形成多级的层次化结构.

(1)对不同的用户策略进行建模分析

本文根据实际的应用场景将用户策略分为QoS优先型和费用优先型.分别确定用户策略的属性重要性关系，构建两种策略下的判断矩阵.其矩阵数值分别如表2、表3所示，表中的数据知识代表了本文中决策者的主观判断，不具有绝对性，其数值可根据实际情况进行相应的调整.

表2 基于QoS优先型的判决矩阵

表3 基于费用优先型的判决矩阵

对判决矩阵进行层次单排序，并进行矩阵一致性检验.符合要求后通过式(4)(5)求得两种策略下的指标归一化权重：

W方案一={wQ,wL,wC,wH}=

{0.514 8,0.279 3,0.147 0,0.058 9}

W方案二={wQ,wL,wC,wH}=

{0.290 2,0.162 2,0.500 8,0.046 8}

(2)对不同的业务类型进行建模分析

由于不同类型的业务具有不同的QoS需求，对网络各个QoS参数要求的相对重要性也有所不同.因此，本文依照表4采用AHP算法分别对四种业务的QoS参数相对权值进行分析，如表5至表10所示.

表4 3GPP的业务类别

表5 会话类业务的第一层判决矩阵

表6 会话类业务的第二层判决矩阵

表7 流类业务的第一层判决矩阵

表8 流类业务的第二层判决矩阵

表9 交互类业务的第一层判决矩阵

表10 后台类业务的第一层判决矩阵

其中，交互类与后台类业务不需要显示的数据率保障，因此只有第一层判决矩阵.根据式(4)(5)计算相应的业务在准则层的综合QoS参数权重向量如下所示：

会话类:

w={wD,wDJ,wPLR,wGBR,wMBR}=

{0.395 0,0.395 0,0.162 6,0.039 4,0.007 9}

流类：

w={wD,wDJ,wPLR,wGBR,wMBR}=

{0.058 1,0.215 0,0.299 0,0.214 0,0.214 0}

交互类：

w={wD,wDJ,wPLR,wGBR,wMBR}=

{0.409 1,0.045 5,0.409 1,0,0.136 4}

后台类：

w={wD,wDJ,wPLR,wGBR,wMBR}=

{0.059 7,0.059 7,0.264 6,0,0.616 0}

(3)层次总排序并计算主观权重

通过所得到的各层判决矩阵的层次单排序结果来计算该模型的层次总排序权重，得到不同用户偏好和不同业务类型下的各属性的层次总排序.

QoS优先:

会话类W′=

{0.203 3 0.203 3 0.083 7 0.020 3 0.004 1 0.279 3 0.147 0 0.058 9}

流类W′=

{0.029 9 0.110 7 0.153 9 0.110 2 0.110 2 0.279 3 0.147 0 0.058 9}

交互类W′=

{0.210 6 0.023 4 0.210 6 0 0.070 2 0.279 3 0.147 0 0.058 9}

后台类W′=

{0.030 7 0.030 7 0.136 2 0 0.317 1 0.279 3 0.147 0 0.058 9}

费用优先：

会话类W′=

{0.114 6 0.114 6 0.047 2 0.0114 0.002 3 0.162 2 0.500 8 0.046 8}

流类W′=

{0.016 9 0.062 4 0.086 8 0.062 1 0.062 1 0.162 2 0.500 8 0.0468}

交互类W′=

{0.118 7 0.013 2 0.118 7 0 0.039 6 0.162 2 0.500 8 0.046 8}

后台类W′=

{0.017 3 0.017 3 0.076 8 0 0.178 8 0.162 2 0.500 8 0.046 8}

3.2 对候选网络进行排序

为了解决TOPSIS算法的失序现象，对不同的业务类型利用式(16)分别计算新的相对接近度，其中λ1、λ2取值分别如表11所示.

表11 不同业务的λ1和λ2的参数值

4 仿真实验与结果

图2 无线异构网络示意图

本文在Matlab环境下进行仿真与分析.如图2所示，仿真环境存在四个典型的无线网络，分别是LTE、WCDMA、WLAN1和WLAN2.假设4个场景下多模终端监测到的网络参数如表12所示.

表12 候选网络属性原始参数值

(1)验证算法的有效性和正确性

首先模拟单个用户在不同的地点根据不同的偏好和业务类型来进行网络选择.仿真场景如图2所示，用户初始使用QoS优先的策略模式沿着箭头所指的方向移动.T1时刻在A点接到视频电话(会话类)，T2时刻到达B点进行网页浏览业务(交互类)，T3时刻到达C点后收到一封邮件(后台类)，T4时刻到达D点用户请求视频点播业务(流类)并停止移动，随后在T5时刻更改为费用优先的用户策略模式并持续视频点播业务.

图3 用户不同策略模式和业务下的C值

T1时刻，用户进行视频通话，该业务对端到端时延有严格的要求，由于LTE网络具有低时延，高可靠性的优点，因此，LTE的c值大于WCDMA的c值，该选择符合现实应用情况.T2时刻，用户进行交互类业务，该业务对时延抖动没有要求，但是对丢包率的要求很高，因此具有较低时延和丢包率的LTE网络为最优.T3时刻用户接收到电子邮件，数据率和丢包率对此后台类业务来说更为重要，综合考虑WLAN1网络最优，符合实际需要.T4时刻进行的流业务对网络速率有较高的需求，WLAN1网络具有最高的速率，可见用户的选择也符合了该视频业务的特征.由于流量的价格比较昂贵，用户在T5时刻更改为费用优先策略模式进行网络选择，由图3可见，WLAN2因价格优势成为用户的最佳选择，与实际情况相符.

(2)验证网络负载均衡性

本文采用用户策略为QoS优先模式与AHP算法的方案进行对比来验证网络负载的均衡性.仿真场景为四个网络的共同覆盖区域，初始时，各个网络的负载均为0，当数量为200的用户请求会话类业务时，如图4所示，在AHP方案中，用户更多的接入到LTE网络，而本文方案中的WCDMA网络承担了一部分业务量，减轻了LTE网络的压力，使得网络之间的负载变得更加均衡.当用户请求流业务时，如图5所示，在AHP方案中，由于用户主观因素的影响，用户并没有更多的接入最优网络WLAN1，而本文方案引入熵权，消除了主观用户的随意性，同时也保证了网络之间的负载均衡性.如图6和7所示，交互类和后台类业务同样保证了网络负载之间的均衡性.