网络算法

2024-07-23

网络算法（精选十篇）

网络算法篇1

1 图的存储结构和网络图的显示

1.1 图的几种存储结构

关于计算机图的运算和存储，主要是结合存储图的基本结构，不仅仅存在关联矩阵和邻接矩阵的结构，同时也存在邻接表和十字链表的形式。对于关联矩阵和邻接矩阵的结构而言，主要是一种数组结构；对于邻接表和十字链表而言，主要是一种链表结构。邻接表有不惟一的表示，在边表节点的连接次序的表达中，往往需要结合邻接表的算法形式。对于网络图的表示而言，邻接多重的形式有较好的效果。

1.2 网络图的显示

网络图的计算机显示理论基础主要结合C语言实现网络图的绘制。在网络图点与点之间的连线分析中，往往存在错综复杂的一种顶点和边的关系，并在屏幕的网络图绘制中将各个顶点画出，物理坐标系的确定如图1所示。

在x轴和y轴的计算过程中，更要保证取值为整数。通过在屏幕上画边，将顶点坐标找出，屏幕上对顶点任意添加中，需做好方法的根本绘制。

图的显示算法完成中，通过对网络图绘制，将若干条边和顶点添加，将若干条边和顶点删除，并在历史的查询中对时间进行记录。网络图显示和查询系统的基本框图，如图2所示。

网络图显示的算法结合中，通过对网络图进行绘制，并在网络图相关信息的输入时，对邻接多重表进行修改，关于新加的顶点将其标记为visited，同时也是True。新的边节点生成之后，在图中P位置的对应中，将新增加边的顶点找到，如图3所示。实际的操作如下所示：

网络图显示中涉及的一些功能算法实现需要结合一些辅助性的功能将网络图画出并做好网络图的调整，及时地存储网络图，并对若干条边和相关顶点添加之后，做好图形的显示，进而构建出网络图计算机显示和查询的基本系统。

2 网络图计算机算法和显示方法

在现代化网络图的广泛应用中，结合计算机算法和实际的显示过程不仅仅存在点符号全控制一种算法，同时也存在边符号控制算法。对于网络图的显示方法而言，需要做好多种显示方法的一种不断分析和应用。

2.1 点符号全控制的一种算法

点符号的基础理论，主要是结合了全控制算法的一种发展变化模式。这种符号全控制算法在将相关理论中，是结合符号控制算法的一种形式，是基于闭领域的一种组织结构，在符号全控制算法中，将极限度引入，并做好最大最小度的限定，这种网络图的符号控制算法下限过程中，实现下界之间的根本更新过程。在符号全控制算法图像的进行中，结合下界问题的更新角度，对下界的具体网络图进行根本上的满足。网络图符号的全控制算法的进行中，保证符号有着一定的完整性和全面性。网络图算法的研究，更要做好思路的不断拓展，实现算法的根本完善和改进。

2.2 边符号控制的一种算法

在2001年符号边控制算法被首次提出，其在m边的最小符号边控制算法的确定中，实现了网络图控制算法理论内容的全面丰富和完善。2002年，网络图的符号控制算法在对上界和下界进行确定中，结合特殊网络符号边控制算法的确切值，实现了网络图符号边控制算法界限。

2.3 网络图的显示方法

对于符号和边符号的显示而言，通过结合网络图的一种显示方法，在屏幕对相关网络图进行绘制中，就要做好数据的输入和点的添加。数据的输入，要求使用者将指令在计算机输入网络图中输入，并对相关数据信息进行输入。这种相关数据信息，不仅仅包括顶点的个数N，同时也包括边的数目M以及顶点的坐标。通过对邻接多重表创建，在邻接双重表中将数据输入，进而将网络图的数据输出环节完成。这种对边和顶点的输入过程中，做好边和顶点指令的添加并输入新添加的数目。顶点新添加的过程，有着孤立性的特点。在网络的不完整连通中，往往要结合基础性的环节，做好网络图的根本绘制。

因此，在网络图计算机算法和实际的显示中，以点符号全控制算法和边符号控制算法为基础，在网络图的控制算法应用中，做好网络图的完善性设计，实现计算机算法和显示系统的更高工作效率。

3 实际运用中计算机算法和显示方法的改进

现代化生活的各个领域中，网络图的广泛运用推动了现代化社会进程的全面发展。对于计算机网络图中的符号全控制而言，结合边符号控制系统的完善，对计算机的显示进行控制，实现查询和显示相结合的网络图系统的完善。

计算机算法和显示中，结合网络图显示和相关的查询系统，在系统的不稳定设置中，注重系统中网络图的多次修改。通过对顶点和边进行不断修改，这种多次的修改操作实现了数据的实时查询，不仅仅将图像的古板有效避免，同时也避免了图像的模糊。结合数据库的形式，在数据库存储中对相关数据进行操作，将数据查询的基础需要有效解决，实现对系统的不断完善。在不同对象的分析中，做好系统的全面改进。基于在交通网络中的应用，实现了计算机算法和显示方法的有效性。

在现代化社会的全面发展中，计算机算法和显示方法的应用，不仅仅需要更多人力和知识的投入，同时在多次的实践应用中，更要结合现代化社会的发展，结合各个领域的实际需求，对网络图技术进行根本上的完善。对计算机算法和显示方法的不断完善，更要本着时代经济发展的主题，实现计算机算法和显示方法的基础性完善。

4 结语

随着时代经济的飞速发展，现代化科学技术的突飞猛进，实现了计算机技术的广泛应用。在网络图理论的基础性应用中，通过结合理论的不断控制性发展，做好相关理论性的创新发展，注重人才的全面培养，在计算机网络图相关人才的培养中，将网络图的应用领域范围不断扩大，并做好知识系统的一种综合性吸收和发展。

参考文献

[1]刘乃维.论网络图的计算机算法[J].计算机光盘软件与应用,2014,8(13):95-96.

[2]付欣.网络图的计算机算法和显示方法的研究[J].电脑知识与技术,2013,6(35):7946-7947.

[3]王莉.网络图的计算机算法和显示方法研究[J].山东农业工程学院学报,2015,32(3):42-43.

[4]王永欣,佟立飞,唐艺灵.基于FPGA的网络图像采集处理系统设计[J].现代电子技术,2011,34(20):29-32.

[5]付博研,卢振洋,白立来,等.一种改进的Canny算法及其仿真验证[J].现代电子技术,2014,37(18):11-14.

配电网络潮流计算算法论文篇2

目前，传统的电力系统潮流计算方法，如牛顿-拉夫逊法、PQ分解法等，均以高压电网为对象;而配电网络的电压等级较低，其线路特性和负荷特性都与高压电网有很大区别，因此很难直接应用传统的电力系统潮流计算方法。由于缺乏行之有效的计算机算法，长期以来供电部门计算配电网潮流分布大多数采用手算方法。80年代初以来，国内外专家学者在手算方法的基础上，发展了多种配电网潮流计算机算法。目前辐射式配电网络潮流计算方法主要有以下两类：

(1)直接应用克希霍夫电压和电流定律。首先计算节点注入电流，再求解支路电流，最后求解节点电压，并以网络节点处的功率误差值作为收敛判据。如逐支路算法，电压/电流迭代法、少网孔配电网潮流算法和直接法、回路分析法等。

(2)以有功功率P、无功功率Q和节点电压平方V2作为系统的状态变量，列写出系统的状态方程，并用牛顿-拉夫逊法求解该状态方程，即可直接求出系统的潮流解。如Distflow算法等。

网络拥塞控制算法研究综述篇3

摘要：在本文中，作者着重阐述了TCP拥塞控制和IP拥塞控制中的典型算法以及目前一些较有影响的拥塞控制算法，分析了当前拥塞控制算法设计过程中存在的不足，并给出了一个有意义的研究方向。

关键词：TCP拥塞控制IP拥塞控制控制理论

0引言

近二十年来，计算机网络经历了飞速的发展，使得信息的交流变得方便和快捷，然而由于网络数据流量的激增，拥塞问题随之而产生，且变得越来越严重，己经成为制约网络发展和应用的一个瓶颈，如何更好的预防和控制拥塞是近年来网络研究的热点问题之一。产生网络拥塞的根本原因在于用户(或叫端系统)提供给网络的负载大于网络资源容量和处理能力，表现为数据包延时增加、丢弃概率增大、上层应用系统性能下降。

1TCP拥塞控制

据统计，Internet上的95％的数据流使用的是TCP协议，因此TCP拥塞控制一直是网络拥塞控制研究的重点。

1.1TCP Tahoe Tahoe是TCP的早期版本，它包括了最基本的TCP拥塞控制算法，由“慢启动”、“拥塞避免”和“快速重传”三部分组成。“快速重传”根据3个重复的确认分组来判断分组丢失的出现，从而减少等待“重传时钟”超时的过程，提高了分组的传输效率。除此之外，Tahoe对往返时间的计算也作了相应的改进，以便更准确地设定超时重传的时间。

1.2TCP Reno Reno在Tahoe的基础上增加了“快速恢复”算法来提高拥塞恢复的效率。当发送端收到一定数量的重复ACK之后，即进入“快速恢复”阶段。源端在接收到足够多的重复的ACK之后，用接着到来的重复ACK触发新数据分组的发送。只有在接收到新发分组的ACK后，源端才退出“快速恢复”阶段。Reno的“快速恢复”优化了单个分组从数据窗口。

1.3TCP New-Reno New-Reno对Reno算法作了一些小改进，以消除有多个分组从同一数据窗口丢失时对重传定时器的等待。改进考虑到发送端在“快速恢复”阶段收到的“恢复ACK”是确认部分而不是全部出现在“快速恢复”阶段的分组。New-Reno直到所有在“快速恢复”阶段开始时出现的分组都被确认，才会退出“快速恢复”。

1.4TCP SACK Sack算法也是对Reno的改进，当检测到拥塞后，不用重传数据包丢失到检测到丢失时发送的全部数据包，而是对这些数据包进行有选择的确认和重传，从而避免不必要的重传，减少时延，提高网络吞吐量。由于使用选择重传，所以在一个窗口中数据包多包丢失的情况下，Sack性能优于New-Reno。但是Sack的主要缺点是要修改接收端TCP。

1.5TCP Vegas Vegas对Reno进行了三项改进：首先采用新的重传触发机制，即只要收到一个重复的ACK就断定超时，以便及时检测到拥塞；而在慢启动阶段则采用了更加谨慎的方式来增加拥塞窗口cwnd，以减少不必要的分组丢失：改进“拥塞避免”阶段的窗口调整算法，通过观察以前的TCP连接中RTT值改变情况来控制cwnd，当RTT变大时就认为发生拥塞，开始减小cwnd，如果RTT变小，就增加cwnd，解除拥塞，理想情况下cwnd就会稳定在一个合适的值上。这样使拥塞机制的触发不再依靠包的具体传输时延，而只与RTT的改变有关。

2IP拥塞控制

在互联网这样的复杂系统中，不能指望所有用户在其应用中兼容端到端的TCP拥塞控制机制，网络也需要参与资源的控制工作。因此，需要采用路由器的拥塞控制方法，即IP拥塞控制。

2.1先进先出(First ln first Out，FIFO)FIFO是一种最简单的调度算法，又被称为“先到先服务”，即第一个到达路由器的数据包首先被传输，接着到达的数据分组在路由器中排队，等待输出，如果包到达时缓存己满，那么路由器就不得不丢弃该包。这种方法的优点是实施简单，但没有考虑被丢弃包的重要程度。由于FIFO总是丢弃到达队尾的包，所以又称为“去尾”(drop tail)算法。但“去尾”和FIFO是两个不同的概念。FIFO是一种包调度策略，决定包传送的顺序；“去尾”是一种丢弃策略，决定哪些包被丢弃。

2.2随机早期检测(Random Early Detection，RED)RED解决的问题主要包括：①早期探测路由器可能发生的拥塞，并通过随机丢弃或标记分组来通知源端采取措施避免可能发生的拥塞：②公平地处理包括突发性、持久性和间隙性的各种TCP业务流；③避免多个TCP连接由于队列溢出而造成同步进入“慢启动”状态；④维持较小的队列长度，在高吞吐量和低时延之间做出合理平衡。

2.3显式拥塞指示算法(ExpIicit Congestion Notification，ECN)在ECN算法中，路由器采用RED算法管理缓冲区，当平均队列长度处于两个阈值之间时，路由器按照一定概率给报文设置CE使能位，而不是简单地丢弃该报文。当下端路由器发生拥塞时，首先选择有CE使能位的报文丢弃。ECN优势在于不需要重传超时，有效地提高网络带宽的使用效率。

2.4公平排队算法(Fair queuing，FQ)FQ算法是一种“轮询”调度算法。在FQ算法中，路由器对每个输出线路有一个排队队列，路由器按“轮询”方式处理包。当一条线路闲时，路由器就来回扫描所有队列，依次将每队第一个包发出。当某个流的数据包到达过快时，其队列就会很快占满，属于这个流的新到的包就会被丢弃。采用这种方式，每个数据流就不可能牺牲其它数据流而多占资源。

2.5加权公平排队算(Weighted Fair queuing，WFQ)WFQ是FQ的改进算法。对每个流(排队)分配一个权值。这个权值决定了路由器每次发往该队列的比特数量，从而控制数据流得到的带宽。WFQ中权值可以由路由器自己决定，也可以由源端通过某种信令通知路由器来决定。总之，WFQ根据不同数据流应用的不同带宽要求，对每个排队队列采用加权方法分配缓存资源，从而增加了FQ对不同应用的适应性。

3TCP与IP拥塞控制比较

显然TCP基于窗口的端到端拥塞控制，本质上是一种基于信源的控制策略。它有明显的不足：①在感知到拥塞到采取控制行动之间存在着显著的时延；②信源可能不按照网络的指令操作；③某些策略中反馈需要在网络中增加额外的分组。基于IP的拥塞控制策略实施在网络层，不必依赖信源来均匀地分配资源，所以不存在以上那些问题。基于IP的拥塞控制策略是公平的，基于IP控制的主要问题在于增加共享资源(主要是路由器)的复杂性。事实上，很多策略的复杂性是与共享路由器的信源数成正比的，当网络的链路速率增加时信源数量也随之增加。

4总结

网络算法篇4

关键词：无线Mesh网络,服务质量,文化算法,粒子群优化算法

0 引言

无线Mesh网络是一种动态、多跳、自组织网络[1]。与传统的WLAN相比具有显著的优势,如高速率、非视距传输、高可靠性等,因此近年来得到了广泛的应用。然而,它也存在不少的问题,路由选择就是其中之一,解决该问题的关键就是在无线Mesh网络中支持QoS。因此基于QoS的无线Mesh网络路由算法的研究已成为一个热点。

多约束QoS路由问题是NP完全问题[2]。研究人员用遗传算法、粒子群算法等启发式算法进行求解。但这些算法都存在不足,如遗传算法冗余迭代运算较多,求解精度不高;粒子群算法易陷入过早停滞等。文化算法是 Reynolds于 1994年提出的一种进化算法[3]。从进化角度看,任何一种符合文化算法要求的进化算法都可以嵌入文化算法框架中作为种群空间的一个进化过程[4]。粒子群算法(PSO)[5]是由Eberhart和Kennedy于1995年提出一种新型的群体智能算法。

基于此,本文提出一种新的文化-粒子群算法的无线Mesh网络QoS路由算法(CA-PSO-QoSR),群体空间采用PSO算法作为演化策略,信念空间引入遗传操作。仿真实验显示CA-PSO-QoSR算法能够较好的求解无线Mesh网络QoS路由,具有较强的搜索满足QoS约束的全局最优路由的能力。

1 无线Mesh网络 QoS路由问题的数学描述

1.1 网络模型

本文采用无向赋权图G=(V,E)表示网络结构,其中V表示网络节点集,E表示网络链路集。每个节点v∈V的传输范围r,设节点vi,vj∈V,d(vi,vj)是两节点之间的距离,则当d(vi,vj)≤r时两节点之间存在一条边e∈E。

1.2 QoS路由指标的形式化

一般QoS路由问题包含多个约束条件,常见的有时延、费用、带宽、时延抖动和丢包率等。这里主要考虑带宽、时延、时延抖动和费用四个约束条件。

给定图G =(V,E),源节点s到目的节点d的路径集为T,对于一条路径t∈T 的边集为E(t ),则其QoS参数描述如下:

bandwidth(t)=min{bandwidth(e)} (1)

delay(t) =∑delay(e) (2)

delay_jitter(t) =∑delay_jitter(e) (3)

cost(t) =|E(t)| (4)

其中,e∈E(t)。

1.3 无线Mesh网络QoS路由问题公式化

多约束QoS路由问题公式化地描述如下:给定网络G=(V,E),需要寻找一条路径t∈T 使其满足如下QoS需求:

bandwidth(t)≥Bmin (5)

delay(t)≤Dmax (6)

delay_jitter(t)≤DJmax (7)

即在从源节点s到目的节点d的所有路径中选择满足式(5)-式(7)且使cost(t)最小的路径。

2 CA-PSO-QoSR算法描述

2.1 CA-PSO-QoSR算法基本思想

CA-PSO-QoSR的基本思想是利用文化算法的双层进化策略,将PSO作为群体空间的一个进化过程嵌入到文化算法模型中。图1所示即为CA-PSO-QoSR算法的总体框架,这种双重演化机制不仅可以有效地减少搜索时间,得到较高的效率,而且还保证了种群的多样性,从而最终得到满足QoS约束的最优路径。

2.2 CA-PSO-QoSR算法详细设计

2.2.1 编码方案

本文采用路径节点序列编码机制进行不等长编码,这种编码方案能够确保生成的路由实际上可连通,同时能够满足QoS约束条件且不存在环路。

2.2.2 适应度函数

个体x的适应度函数定义如下:

$f i t_{x} = {\begin{cases} 1 / c_{x} b_{x} \geq B_{\min} \land d_{x} \leq D_{\max} \\ 0 e l s e \end{cases} (8)$

其中,bx,dx,cx分别对应个体x路径的带宽、时延和费用,Bmin和Dmax分别表示可接受的最小带宽和最大时延。

2.2.3 群体空间进化策略

群体空间中引入粒子群优化算法,针对无线Mesh网QoS路由寻径的特点,借鉴了文献[6]中提出的惯性权重的概念,用于在种群进化过程中更好地对局部最优与全局最优进行权衡,提高收敛速度并有效地避免“早熟”现象的发生。

1) 初始化

群体空间采用随机生成的方法得到粒子初值,且对网络中所有节点建立连接关系表,使得随机搜索只在实际可连通的节点中进行,这样可过滤掉不满足带宽约束的链路,并保证每个粒子对应的路径中无重复节点。

初始化时需对陷入循环等问题进行处理,如图2所示,虚线标示的区域就是一种典型的循环区域,这时如果不给予干预,粒子就会陷入循环。对此本文采用回溯策略,即及时终止区域内的无效搜索并返回到前一节点(图中的节点2),在节点2的后继节点集合中选择除5以外的其他可行节点,直到能够跳出循环为止。当随机生成的粒子数目达到预定的种群规模时,初始化过程结束。

2) 粒子的速度和位置更新

设群体空间进化至第k代,整个种群全局历史最优位置记为Pgbest,种群中第i个粒子(亦称为粒子i)的历史最优位置记为Pibest,粒子i在当前代的位置和速度分别记为Pik和Vik,则其在下一代的位置Pik+1和速度Vik+1按下式进行求解:

$\begin{array}{l} V_{i}^{k + 1} = (\frac{ω}{ω + c_{1} \times r_{1} + c_{2} \times r_{2}} \otimes V_{i}^{k}) \oplus \\ (\frac{c_{1} \times r_{1}}{ω + c_{1} \times r_{1} + c_{2} \times r_{2}} \otimes (Ρ_{i b e s t} - Ρ_{i}^{k})) \oplus (\frac{c_{2} \times r_{2}}{ω + c_{1} \times r_{1} + c_{2} \times r_{2}} \otimes (Ρ_{g b e s t} - Ρ_{i}^{k})) (9) \end{array}$

P $_{i}^{k + 1}$ =P $_{i}^{k}$ +v $_{i}^{k}$ (10)

其中,⊕表示多项选一,⨂表示以其左操作数代表的概率选择其对应右操作数代表的动作,c1和c2为学习因子,r1和r2是均匀分布于(0,1)区间内的随机数, c1×r1用以表示粒子向其自身经过的最优位置学习的比重,c2×r2用以表示粒子i向整个种群全局历史最优位置学习的比重。

引入惯性权重ω来平衡算法的局部寻优和全局寻优的能力,设定ωmax和ωmin为给定的边界值,须满足条件0<ωmin<ωmax,其取值分别为0.8和1.2。

$ω = ω_{\max} - \frac{ω_{\max} - ω_{\min}}{i t e r_{\max}} \times k (11)$

2.2.4 信念空间进化策略

1) 信念空间初始化

信念空间采用与群体空间相同的编码形式,其群体规模取为群体空间中群体规模的α倍,初值取为当前群体空间中适应值较优的相同数目个体。

2) 遗传算子的设计

(1) 选择操作

根据个体适应度值,选出当前种群中适应度值最高的个体(记为fitmax),将其保留并直接复制到下一代中,然后用赌轮盘方式选出一定数目个体进行交叉、变异后再进入下一代个体。记个体i的适应度值为fiti,α·N为信念空间的种群规模,则赌轮盘方式中个体i被选中的概率pi可按下式得到:

$p_{i} = f i t_{i} / (\sum_{i = 1}^{α \cdot Ν} f i t_{i} - f i t_{\max}) (12)$

通过赌轮盘方式选出数目为2(α·N-1)的个体,执行完交叉和变异操作后,按适应度值进行排序,以保证种群规模始终恒定为依据,从中选择较优的适量个体进入下一代种群中。

(2) 交叉操作

采用单点交叉策略来实现信念解群体共享信念信息,把两个父代个体的部分结构加以替换重组而生成新个体,根据给定的交叉概率pc执行交叉操作。生成的新个体中可能会存在环路,冗余环路的存在导致个体开销增大,在一定程度上降低算法的收敛速度,所以需对子代个体进行冗余环路的检测和消除操作。

(3) 变异操作

交叉操作完成后会产生新的子代个体,这里以给定的变异概率pm为依据判断是否进行变异操作,如果需要则采用受限的变异策略[10]。具体变异过程如下:

在目标个体中,在除首尾节点外的所有节点中随机选择一个节点作为变异节点,然后从目标节点开始反向遍历,若有节点可直接连接到变异节点,就剔除剩余节点直接将当前节点与变异节点相连接。这是为了去除多余链路,减少开销。如图3(a)所示,变异节点为节点4,目的节点为节点10,原有路由序列为3-5-6-9-10,从节点10开始倒序查找,判断是否能和节点4直接相连,当遍历到节点6发现其和节点4之间有链路直接相连,丢弃掉剩余的节点直接将节点4与节点6连接,变异策略完成。

如果遍历操作直到变异节点的直接后继结点处仍没有可与其相连的节点,就采用初始化空间时所用的方法,即随机搜索生成变异节点到目的节点的一条路径,用以代替原个体中变异节点与目的节点之间的链路,如图3(b)所示,变异节点和目的节点为节点4和10,原有路由序列为3-5-6-10,从节点10开始倒序查找,直到节点5 (变异节点的直接后继结点)也没有节点能与节点4直接相连。将随机产生节点4与节点10之间的一段链路如7-9-10,变异策略完成。

2.2.5 通信协议

通信协议是文化算法框架中两个空间的交互渠道。通过接受操作(acceptance)和影响操作(influence)实现空间的不断交流,将各自最新的搜索结果及时地反馈交互,进行信息共享。

1) 接受操作

在群体空间演化过程中采用定期更新的策略,每当粒子群优化算法运行AcceptStep代时,用种群中当前全局最优个体替换信念空间群体的最差个体。

2) 影响操作

本文采用动态的选择影响时机,使得信念空间对群体空间的影响随着演化代数的增加而增大。通过设定一个动态变化的变量InflunceSetp,信念空间中种群每运行InflunceSetp代时,将信念空间群体中适应值较好的一定数目个体,替换群体空间中适应值较劣的同样数目个体。InflunceSetp的值通过下式计算得:

InflunceSetp=N1+N 2(itermax-CurrentStep)/itermax (13)

其中,N1、N2为常数,itermax为算法最大演化代数;CurrentStep为当前群体空间进化代数。这里N1、N2取值分别为2和5。

2.3 CA-PSO-QoSR算法流程

Input:无线Mesh网络G,群体空间种群规模N,最大迭代次数itermax,QoS路由约束组Multi_Cs=f(x)(Snode,Dnode,Bmin,Dmax,DJmax)及其它参数;

Output:满足约束条件的最优QoS路由;

Begin

CurrentStep←0;

//第0代初始化群体空间和信念空间;

While 不满足终止条件 do

Begin

For i=1 to N do //群体空间PSO算法进行搜索

//更新粒子i的速度、位置和Pibest;

End For

更新全局最优位置Pgbes;

If CurrentStep % AcceptStep=0 Then

执行接受操作;

执行选择操作,选出(α·N -1)对个体组合;

For i=1 to (α·N -1) do //随机生成操作概率ptemp = rand(0,1);

If (ptemp≤pc) Then

//满足交叉概率对个体组合i执行交叉操作;

If(ptemp≤pm) Then

//满足变异概率对新得到的子代个体执行变异操作;

End For

将前(α·N -1)个适应度值较优的个体保留至下一代;

If CurrentStep % InflunceSetp =0 Then

执行影响操作;

CurrentStep←CurrentStep +1;

End

输出群体空间中的最优解Pgbest;

End

3 仿真实验和结果分析

本文通过仿真实验对CA-PSO-QoSR算法的可行性和有效性进行验证,同时选择基本的粒子群优化算法(PSO-QoSR)、改进遗传算法(GA-QoSR)[7]和遗传粒子群优化算法(GA-PSO-QoSR)[8]进行比较。设定Mesh网络范围是90m×120m的区域,其中分布有随机生成的100个节点,每个节点有唯一的标识号,节点间通信距离为r≤30m。链路上的QoS度量均随机生成:带宽取[1]之间的整数,时延、费用均取[1]之间的整数,时延抖动取[0.01,0.1]之间的小数。算法中各参数设置为:群体空间种群规模N=30,信念空间规模为αN=0.4N=12,最大迭代次数为itermax =50,c1=1.6,c2=1.8,交叉概率pc=0.9,变异概率pm=0.1。

3.1 CA-PSO-QoSR在不同约束下的搜索结果分析

选取不同的源与目的节点,对CA-PSO-QoSR在不同的QoS约束下的路由寻径进行实验。选取3组不同的源和目的节点,在不同的QoS约束下分别进行10次实验,所得结果见表1。

表1 不同QoS约束下CA-PSO-QoSR的寻优结果

如表1所示,在不同的QoS约束条件下,CA-PSO-QoSR算法总能搜索出从源节点到目的节点的一条路径,并且在满足QoS约束的基础上寻找具有较低费用的路由。表明了CA-PSO-QoSR算法中以各约束为必要条件、费用为目标函数的机制,保证了针对合理的业务请求都能够找到一条满足约束的较优路由。

3.2 CA-PSO-QoSR全局寻优能力分析

本节为评价CA-PSO-QoSR算法在不同QoS约束条件下的全局寻优能力,设定源节点为2,目的节点为16,表2为各算法在(2,100,0.8)和(6,60,0.4)两种QoS约束条件下分别运行10次得到的结果。如表2所示,四种算法均能对给定的源和目的节点搜索出满足约束条件的路由,但求得解的质量却相差很大。

其中,PSO-QoSR算法因过早陷入局部最优,所得路由费用最大。GA-QoSR算法结合多种因素对个体基因的选择进行指导,使得搜索结果相比PSO具有明显提高。GA-PSO-QoSR将遗传算法中的交叉、变异思想引入到粒子群优化算法中,融合了两种算法的优点,使得新算法能够较快的收敛到较优解,但其中粒子群算法每代搜索的全部结果都要执行遗传操作,使得冗余计算程度较高,同时对粒子群算法中向全局最优位置学习的机制利用不够充分。而本文提出的CA-PSO-QoSR通过文化算法框架,利用“精英知识”思想提取粒子群优化算法的较优结果,进而实现基于“精英知识”的双向指导,保证算法具有更好地发现全局最优解的能力。

3.3 CA-PSO-QoSR收敛速度分析

选定源节点为2,目的节点为16,考察CA-PSO-QoSR和PSO-QoSR、GA-QoSR、GA-PSO-QoSR三种算法在同等条件下搜索得到最优解所需的迭代次数。针对QoS约束为(2,100,0.8)和(6,60,0.4)两种情况,每种算法运行数据如图4和图5所示,图中四种算法迭代至25代后均得到收敛,故在此处省略掉后25代的搜索结果。

从两图中可知:基本的PSO算法求解QoS路由问题时虽然搜索速度较快,但是全局寻优能力有限,极易陷入局部极值。GA-QoSR算法在交叉、变异等操作中引入了去除环路、削减路由开销等策略,在一定程度上减少了GA求解时所需的大量冗余计算,提高了算法的执行效率。GA-PSO-QoSR融合了GA和PSO两种算法的优点,相对PSO-QoSR和GA-QoSR而言其全局寻优能力得到了进一步提升,但对GA与PSO的进化信息利用不充分。CA-PSO-QoSR算法基于文化算法的双层进化框架,结合其精英思想使得PSO算法的向最优个体学习机制效率更高,从而加快了算法收敛到全局较优解的速度。

4 结语

针对无线Mesh网络的特点,本文提出了一种基于文化-粒子群算法的无线Mesh网络QoS路由算法,在群体空间中采用粒子群优化算法作为演化策略,同时将遗传操作引入到信念空间中实现精英解集的迭代更新,通过信念空间中不断进化的精英解信息指导群体空间的搜索。仿真实验验证了新算法更能满足QoS路由中带宽、时延和时延抖动等重要指标,具有较好的全局寻优能力和更快的搜索速度。

下一步的工作重点是继续优化算法,并与现有路由协议相结合,模拟实际网络环境对算法性能展开更加全面和深入的分析。

参考文献

[1]Akyildiz I F,Xudong Wang.A Survey on Wireless Mesh Networks[J].IEEE Communications Magazine,2005,43(9):23-30.

[2]Wang Zheng,Crowcroft J.Quality-of-Service routing for supportingmultimedia applications[J].IEEE Journal on Selected Areas in Com-munications,1996,14(7):1228-1234.

[3]Reynolds R G.An Introduction to Cultural Algorithms[C]//Proceed-ings of the Third Annual Conference on Evolutionary Programming,World Scientific.River Edge,New Jersey:[s.n.],1994:131-139.

[4]齐仲纪,刘曼丹.文化算法研究[J].计算机技术与发展,2008(5):126-129.

[5]Kennedy J,Eberhart R C.Particle Swarm Optimization[C]//Proc.Of IEEE Int.Lconf.On Neural Networks.IEEE Service Center.Pis-cataway,NJ,1995:1942-1948.

[6]Colorni A,Dorigo M,Maniezzo V.Distributed optimization by ant col-onies[C]//Proceedings of the first European conference on artificiallife,1992:134-142.

[7]吴巍,阮秋琦.用改进的遗传算法解决多约束QoS单播路由问题[J].铁道学报,2005,27(6):71-76.

网络层学习之一选路算法篇5

一、概述

1.转发和选路

网络层的功能是要将分组从一个主机移动到另一个主机从而使得主机之间可以互相通信。为此需要网络层提供两种功能：

转发：路由器（三层交换机）将进入其某个输入链路的分组转发到其某个输出链路。它是将分组从一个输入链路移动到一个输出链路，是一个路由器的本地动作。

选路：在分组从一个主机流向另一个主机的过程中，网络层必须决定分组所走过的路径。计算这个路径信息的算法就是选路算法。它是一个网络范围的动作，决定分组从其源到目的应该走的路径

路由器在网络层是一个极其重要的设备，每台路由器都由一张转发表。路由器检查到达分组首部中的一个字段的值，然后利用该值在路由器的转发表中进行查询，以决定该如何转发该分组。查询的结果是分组将被转发的路由器的链路接口。

选路算法决定了转发表中的值。选路算法可能是集中式（由某个中心点执行）的也可能是分布式的（运行在各台路由器上），无论采用何种方法，路由器都要接受选路协议报文以配置其转发表。

连接建立：在有些计算机网络中，连接建立也是网络层的重要功能。比如ATM，它要求从源到目的地沿着所选择的路径彼此握手，以便在源和目的之间建立起状态。

2.网络服务功能

网络层能够提供的特定服务包括（但实际上不一定提供）：

确保服务：确保能最终到达目的地

具有时延上届的确保交付：不仅确保交付，而且确保在时延上届内交付

有序分组交付：确保分组按照它们被发送的顺序到达目的地

确保最小带宽：只要发送主机以低于特定比特率的速录传输，分组就不会丢失

确保最大时延抖动：发送方发送两个连续分组的时间间隔和接收方接收它们的时间间隔之间的差值在一定范围内

安全性服务：使用仅仅发送方和接收方所知晓的密钥通信。

但是因特网的网络层提供的是无连接的不可靠的服务，尽力而为的服务，其含义是：

不可靠：IP层不保证IP数据报能成功到达目的地。如果需要保证可靠传输，则需要使用其它协议，比如TCP。

无连接：IP不维护任何关于后续数据报状态的信息，每个数据报的处理是相互独立的。因此两个IP之间的多个报文可能乱序到达，可能走不同的路径。。。

3.分组转发

在因特网中，每当一个主机要发送一个分组时，它就为该分组加上目的主机的地址，然后将该分组发送出去。

当分组在网络中向目的地传输时，它会经过一系列路由器。每个路由器都使用该分组的目的地址来转发给分组。每台路由器都由一个将目的地址映射到链路接口的转发表，每当分组到达时，路由器就利用分组的目的地址在转发表中查找一个合适的输出链路接口，然后路由器将分组从该输出链路接口发送出去。

在因特网中，路由器的转发表可以由选路算法或者管理员更新。由于转发表的修改可能发生在任意时刻，因而两个主机之间的分组在不同的时刻走的可能是不同的网络路径，并可能无序到达。

1.最长前缀匹配规则

网络前缀：是网络地址的前边某些连续比特。比如对于地址 11101111 11011110 1000000 00000001，其对应的8比特前缀为11101111 ， 16比特前缀为11101111 11011110

在该规则下，路由器的转发表中记录的是网络前缀和输出链路接口之间的对应关系。当查转发表时，仍然利用目的地址来进行匹配，但是可能会有很多歌匹配，这个时候取匹配到的比特数目最多的表象作为命中表项，并根据它来转发分组。

二、路由器

网络层的最主要的功能是将分组从一台主机移动到另一台主机。该功能主要是由路由器完成的。典型的路由器结构如下：

输入端口：它接入输入的物理链路，和链路远端的数据链路层交互，并完成查找和转发功能，以使得输入分组能够进入到合适输出链路接口。对于控制分组，它则会进入选路处理器。

交换结构：它将路由器的输入接口连接到它的输出接口。

输出端口：存储经过交换结构发送给它的分组，并将分组发送出去。同时它执行和输入端口相反的链路层功能和物理层功能。

选路处理器：执行选路协议，维护选路信息和转发表，

1.输入端口

输入端口的线路端接功能与数据链路处理时限了与通向路由器的各个输入链路相关的物理层和数据链路层。输入端口的查找/转发功能对路由器的转发功能是非常重要的。在很多路由器中，就是在这里来确定一个到达的分组经交换结构转发给哪个输出端口。输出端口的选择是取决于转发表中的信息，虽然转发表是由选路处理器计算的，但是通常每个输入端口都会有一份转发表的影子拷贝，并且会被及时更新。正因为输入端口拥有转发表的本地拷贝因而就可以在每个输入接口做出转发决策，而无需调用中央选路处理器，这种模式可以避免在路由器的某个节点产生转发处理瓶颈。

在输入端口处理能力受限的路由器中，输入端口会将分组转发给中央绚丽处理器，然后由它执行转发表查找并将分组转发到恰当的输出端口。

在有了转发表后，转发决策就很简单，就是查找转发表，但是由于主干路由器的转发表规模很大，而且我们期望输入端口的处理速度能够达到线速或者说我们期望查表的速度越快越好，因而就需要对转发表的组织和查询进行优化，常见的方式有：

以树形结构存储转发表，树的每一级对应目的地址中的一个比特，如果地址比特位0则搜索其左子树，否则搜索右子树。采用这种结构，N比特的目的地址可以在N步之内找到相应的转发表项。

内容可寻址内存CAM，采用树形结构对于主干路由器来说还是太慢了，CAM允许将一个IP地址交给CAM，然后由CAM在常数时间内返回该地址对应的转发表项的内容。

将最近访问的转发表保存在高速缓存。

找到分组输出端口后，分组就可以进入交换结构。这个时候分组可能会被阻塞，因而来自其它输入端口的分组可能正在使用交换结构。被阻塞的分组需要在输入端口排队。

2.交换结构

通过交换结构，分组可以从一个输入端口交换到一个输出接口。三种交换技术：

经内存交换：输入端口和输出端口之间的交换是在CPU的直接控制下完成。分组到达时，端口通过中断方式通知选路处理器，该分组从输入端口被拷贝到处理器内存，然后选路处理器取出分组的目的地址，查找转发表找到输出端口，并将分组拷贝到输出端口的缓存中。这种模式下，转发吞吐量受限于内存带快。PC一般采用该方式。有些现代路由器也采用内存交换，但是与PC的区别在于查表和将分组存储到适当的存储位置是由输入线路卡上的处理器来执行的。

经总线交换：输入端口经一根共享总线直接将分组送到输出接口，不需要选路处理器的干预。这种模式下，路由器的交换带宽受限于总线带宽。

经一个互联网络交换：高端路由器一般采用该方式，它可以克服单一、共享式总线的带宽限制。纵横式交换机时一个由2n条总线组成的互联网络，它将n个输入接口和n个输入接口连接。

在这种由纵横式交换机构成的互联网络中任意两个端口之间都有自己的专用总线，因而可以克服单一、共享式总线的带宽限制。使用这种网络时，往往把长度变化的IP分组分片成固定尺寸的信元，加上标签通过互联网络进行交换，这些信元在输出接口再被装配成初始分组。这种方式能够极大的简化并加快通过互联网络的分组交换。

3.输出端口

输出端口取出存放在输出端口内存中的分组并将它传送到输出链路上。它在数据链路层和物理层上实现与输入接口相反的功能

4.排队

在输入端口和输出端口都可能出现排队。随着这些队列的增长，路由器的缓存空间可能会耗尽，进而导致出现丢包。

对于有N个输入接口和N个输出接口的路由器，定义交换结构速率为交换结构能够从输入端口移动分组到输出端口的速率。则如果交换结构的速率至少是输入线路速率的N倍，则在输入端口不会出现排队，这是因为即便所有的N个端口都在接收报文，交换结构也能够将其全部移动到输出接口。但是对于输出接口，假设交换结构速率为线路速率的N倍，则在最坏情况下，到达所有N个输入端口的分组都要被发送到同一个输出端口，在这个情况下，输出端口发送一个分组的同时它要接收N个分组，因而就会导致排队，这种情况持续下去就会导致输出端口的队列不断增长并耗尽内存出现丢包。

由于会出现排队，因而缓存大小的设置就非常关键，缓存大小设置的经验方法是：缓存量=平均往返时延*链路的容量。

1.分组调度

输出端口出现排队，一个重要的问题就是输出端口如何发送这些排队的分组，可能的方式有：

先来先服务FCFS

加权公平队列，它在具有排队等待传输的分组的不同的端到端连接之间公平的共享输出链路。

2.队列管理

另外的一个问题是如果没有足够的缓存来缓存一个分组，是丢弃该分组，还是丢弃一个已排队的分组来为新的分组腾出空间。相关的策略通常为主动队列管理算法AQM。随机早期检测算法RED是一种常见的算法，其思想是为输出队列长度维护一个加权平均值：

无线传感网络改进APTT定位算法篇6

摘要：未知节点定位是无线传感网络中的研究重点之一，目前最常用算法为基于免测距原理的APIT算法。该算法具有通信开销小、硬件简单易实现等优点，但其基本思想为质心原理定位，故定位精度难以提高，特别是当锚节点稀疏时无法定位。针对APIT定位算法无法定位，锚节点三角形不包含待定节点的情况，提出一种改进两点定位法，并与原APTT定位算法相结合，提高了定位精度及未知节点覆盖率。endprint

网络算法篇7

对于优化无线传感器网络的负载平衡和通信, 我们已经进行了大量的研究。其中最著名的一种研究方法是基于GEAR协议的无线传感器网络节点分配法。目前几乎所有的无线传感器网络都基于此协议。GAER协议是一个基于地理位置的路由器协议。它将该节点的位置信息作为选择路由器的主要依据, 并根据监测目标的地理位置, 进行特定方向的信息传送, 以降低无线网络路由的开销。

然而, 随着无线传感器网络的应用环境变得越来越复杂, 基于GEAR算法的基本通信协议也逐渐显示出了严重的缺陷, 许多研究人员都提出了规则传感器网络节点的调度方法。但鉴于节点随机分布的特点, 它无法保证有效的对所有节点进行有规则的调度。假设通过一种非可靠的模式来选择网络节点, 则需要太多的经验知识, 从而极大地限制了网络节点的调度。有的学者研究了一种基于模糊模式的节点调度方法, 通过这种方法可以使用最少的资源找出合适的节点位置。然而, 该方法的缺陷是高度依赖于地理位置, 能耗等经验知识来进行调度, 这就大大的限制了它的应用性和实用性。

2 传统的无线传感器网络GEAR节点分配算法和缺陷

GEAR算法是经典的无线传感器网络的分配算法, 它由两部分组成。第一部分中, 节点根据自己的位置坐标感测周围节点的能量, 并根据检测结果, 转发它所接收到的数据包, 而第二部分, 洪水数据包的传输用于目标区域。该文的研究集中于整个网络的能量平衡, 从而强调的是该算法的第一部分。当该节点检测周围的节点能量时, 如果发送在某个节点N上的数据P, 则需要先定位传感器节点周边邻居节点的存在, 然后选择一些邻居节点, 并将其设置为Ni, 并将节点传输目标区域作为中心结点 (将区域R标记为D) 。在传感器节点收到传输数据的之后, 开始收集邻居节点并把所有节点的价值作为据悉成本h (Ni, R) 。以最小代价选择节点作为网络传感器节点N的数据, 并将之传送到下一个节点。传感器网络中的每个节点都将被赋予一个h (Ni, R) 的据悉成本。根据网络数据的传送, 不规则的进行数值的更新。当并非一个节点接收前一个节点据悉成本代价的时候, 网络将会通过h (Ni, R) 计算默认的传输代价。C (Ni, R) 的公式如下:c (Ni, R) =αd (Ni, R) + (1-α) e (Ni)

在上式中, 公式α, d (Ni, R) 以及e (Ni) 是表示距离表达式的常系数, 该节点到下一跳临近节点间的最大距离, 以及从该节点到下一跳节点间数据传送的最大能量消耗。节点将根据所选择的下一跳节点表达式更新其据悉成本h (N, R) 。如果下一跳节点是Nmin, 那么h (N, R) 将根据以上公式进行h (Nmin, R) 和c (N, Nmin) 的总和计算转换。GEAR算法的最大优势在于它可以基于网络的经营情况, 及时更新调控因子α的价值, 以此来保证能量平衡和网络路由器的理性选择。当α系数达到1时, GEAR算法的主要功能在于地理位置识别和路由。该算法不断调整参数以平衡网络的能量, 提高它的性能, 延长网络的寿命。

然而, 随着网络规模的不断增长, 调度协议遭遇了严重的缺陷, 其缺陷主要在于节点选择的随机性变大, 节点的能量负载没有充分考虑。如果该节点选择错误, 就会出现网络挤塞。这是当前无线网络通信的一个难题, 。

3 模糊加固Q学习算法

为了解决上述问题, 该文引入了强化学习方法。但在Q强化学习方法中, 需要很多经验知识作为支持, 这就进一步限制了它的实用性。为了克服这个难题, 该文提出了向强化学习Q点模糊逼近, 模糊控制的输入情况是是成对的状态控制。通过在最佳状态下搜索的Q值, 并在添加前面的相应干扰因素后, 在模糊控制环境下发挥算法的功效。模糊控制环境在状态转换的过程中得出一个算好的模糊奖励值Q。根据模糊值的错误, 进行模糊控制系统结构的调整和学习。这就可以更好地符合无线传感器网络节点模糊能量的环境。从图1可以看出, 采用电脑模糊控制的加强型Q学习系统结构。

在此框架下, 学习过程中使用模糊控制网络来描述和存储相关任务。当学习过程通过传感器感知的当前状态为Q时, 就会根据当前状态进行模糊搜索控制, 并在未知的经验中取得最佳的选择。随后, 它会考虑修改最佳策略, 使搜索和利用之间达到平衡, 以取得执行的最佳效果。

4 基于模糊加强Q学习改进型GEAR算法的建议

基于GEAR传统无线传感网络协议实现了通过地理位置与能量感知的路由选择。但GEAR网络负载平衡只提供了有限的支持。例如, 如果在网络中的传送路径上出现拥堵, 地理位置和能源消耗将保持不变, 并且将仍然使用以前的路径发送到网络拥塞区域。这将导致额外的能量消耗。该文通过将模糊强化学习机制引入传统算法, 从而本文将网络负载均分到传感器的每一个节点的功能得以实现, 从而减少节点的能量消耗, 延长了无线传感器网络的生命周期。

5 实验仿真与分析

为了证明论文提出算法的有效性, 该文采用2种传感器网络仿真工具, 即OMNET++仿真工具和第三方模型移动框架2 (以下简称为MF2) , 以进行节点的随机部署。这些工具不仅具有随机部署传感器节点的功能, 也可以主动的设置部署传感器坐标值。网络区域中已经设定的传感器主要假定在目标区域的检测和收集数据的责任。此外, 该文在应用层上还设计了数据采集模块的仿真实现, 如图2所示

在实验模拟中, 假设节点之间的最大通信距离为200米, 基站节点的通信半径均为100米;选定的传感器节点的通信半径设置为10米, 然后发射功率和传播传感器的灵敏度可以用下面的公式计算:

在上式中, 公式Ws, Wsa, Wra是指一组发送终端的系数, 这些终端用于表示发送终端的发送功率和天线增益值。Wrs表示带有被设置为D的通信半径接收端的灵敏度。假定所有的绝对功率Ws, 所有远程基站节点和网络中的传感器节点在20m内W (=17d Bm) , 网络传感器节点为1m W的 (=8d Bm) , 我们可以得到的基本站节点的接收灵敏度为-55d Bm, 接收灵敏度的传感器节点c和所有节点的仿真参数如表1所示:

6 结论

论文在分析传统GEAR传感器节点分配算法和模糊增强型Q学习算法的基础上, 提高了GEAR传感器网络平衡算法。使用模糊神经网络向强化学习结合的Q值与无线传感器节点的分配过程中, 选择发送节点根据模糊的Q值或Q值的近似值。它改善了传统的GEAR节点分配算法的缺陷, 即高度依赖于地理位置, 能源消耗及其他经验知识进行调度。最后, 通过仿真实验, 证明通信能量消耗曲线的趋势是低于传统的算法, 从而能够避免网络的拥挤。

参考文献

[1]刘玉宏, 詹英.室内Cricket无线传感器网络定位方法的改进[J].计算机工程与应用, 2010 (21) .

[2]赵军, 李鸿斌, 王智.无线网络室内定位系统研究[J].信息与控制, 2008 (4) .

[3]高明, 吉祥, 刘宇, 等.ZigBee技术在室内定位中的应用[J].西安工业大学学报, 2010 (1) .

[4]杨东勇, 顾东袁, 傅晓婕.一种基于RSSI相似度的室内定位算法[J].传感技术学报, 2009 (2) .

[5]宋上雷, 刘果.无线传感器网络及能耗策略[J].数字通信世界, 2005 (11) .

[6]陈雄, 杜以书, 唐国新.无线传感器网络的研究现状及发展趋势[J].系统仿真技术, 2005 (2) .

[7]陶诗涌, 罗惠琼.密集型无线传感器网络多对一的传送能力及数据压缩研究[J].计算机与信息技术, 2005 (5) .

[8]胡文基, 徐明伟.无线传感器网络安全路由协议分析[J].北京邮电大学学报, 2006 (1) .

[9]马斌, 周小佳.无线传感器网络拓扑优化研究[J].网络安全技术与应用, 2006 (4) .

社会网络链接预测算法研究篇8

作为一种抽象结构, 社会网络是指由节点和边组成的, 用来描述节点之间复杂关系的网络。由于社会网络在社会学、心理学、计算机学甚至生物学等多个领域的广泛应用, 研究者们对社会网络的研究方兴未艾。随着社会网络数学性质不断被挖掘, 研究者发现社会网络中节点之间的链接关系对整个社会网络分析起到重要作用。对链接关系进行挖掘意义较大, 可以揭露网络中隐藏的关系。而链接预测是链接挖掘中的一个最基本问题, 它基于节点属性以及已经观察到的链接信息, 对两个节点之间是否会出现链接进行预测。链接预测不仅可以用来预测在时间演化尺度下未来可能出现的链接关系, 还可以用来检验出由错误信息所导致的虚假链接。作为社会网络分析的一个重要方向, 链接预测与社会学、图形学有着密切关系, 并逐渐发展成为国内外研究热点。

近年来, 研究者提出了很多解决链接预测的相关算法, 这些算法一般是基于监督学习的链接预测、基于概率模型的链接预测、基于节点相似度的链接预测等。但是社会网络是动态发展变化的, 随着时间的推移会出现很多新的节点和边, 同时一些旧的节点和边会消失。因此传统的链接预测算法只有与时间属性相结合才能更好地刻画网络的演变机制, 从而发现网络的演变规律。

1 相关研究

目前, 社会网络链接预测研究主要分为如下3个方向:

(1) 基于节点相似度的链接预测[1,2]。根据预先设定好的相似度评分函数对节点间的相似度进行打分, 然后根据打分值将所有没被发现的链接进行排序, 相似度分数越高则该两个节点存在链接的可能性越大。该方法的缺点是考虑网络拓扑结构, 而忽视了网络的其它因素, 例如时间因素, 从而导致预测结果差强人意。

(2) 基于概率模型的链接预测[3,4]。首先利用社会网络中的节点或者边构造一个统计模型, 然后利用该统计模型进行链接预测。统计模型构建是该方法的核心, 将直接影响后续链接预测的结果。该方法主要有两个缺点:一是获取节点信息的难度很大, 无法获得足够的先验知识, 因此统计模型构建非常困难;二是算法的复杂性比较高, 因此在实际应用中具有一定难度。

(3) 基于监督学习的链接预测[5,6]。根据已知的网络信息获取链接关系, 并在这些链接关系中提取相关的特征属性构建分类器, 然后根据该分类器对未知网络进行二类划分, 即判断链接关系存在或者不存在。该方法的主要缺点是社会网络中的节点不是简单的统计上的独立采样点, 节点之间存在着联系, 并不满足传统的机器学习条件。

近几年, 研究者对链接预测的研究越来越深入, 并不断加入影响算法的新因素。除实现基本的发现隐藏链接的任务外, 还需要考虑新的细节。例如, 可以考虑时间演化尺度下社会网络中的链接预测。随着时间的推移, 社会网络中节点之间的链接在不断变化, 可能会有新链接的产生, 也可能有旧链接的消亡, 因此链接预测需要考虑时间因素。

2 算法提出

共有邻居相似度算法是一种经典的基于节点相似度的链接预测方法, 该算法利用两个节点共有邻居的多少来确定链接存在的概率, 即共有邻居越多链接存在的概率越高, 反之则越低。例如, 如果两个人之间的学历、爱好和收入都比较相近, 就可以认为他们之间的相似度较高。然而该算法仅考虑共有邻居的数目, 没有考虑其它因素 (例如时间因素) , 显然是不全面的。因此, 本文尝试将时间因素融入到共有邻居相似度算法, 提出了新的节点相似度评价标准。

2.1 问题定义

为简化问题, 只考虑无向社会网络, 首先给出无向社会网络的定义。

定义1:无向社会网络可以定义为G=, 其中V是节点的集合, E是边的集合。

上述定义是基于传统的静态社会网络, 但社会网络是动态变化的。考虑社会网络的时间属性, 提出了基于不同时刻快照的社会网络定义。

定义2:无向社会网络可以定义为由不同时刻的快照所组成的图序列G=, 其中GΔti是时间Δti的网络图, 同时满足1≤i≤n。

然后再给出基于定义2的链接预测定义。

定义3:给定一个社会网络在不同时刻所组成的图序列G=, 可以预测出在下一时刻某两个节点之间存在链接的可能性。

2.2 共有邻居相似度

共有邻居相似度认为如果两个节点拥有越多的共同节点, 则这两个节点越相似。

定义4:对于节点u和节点v, 其共有邻居相似度定义如下:

其中, neighbor (u) 是节点u的邻居, neighbor (v) 是节点v的邻居。

共有邻居相似度算法简单高效, 但是仅仅依靠共有邻居的多少来判断两个节点的相似度显然是不够的, 需要考虑社会网络的时间属性。

2.3 结合时间属性的链接预测算法设计

移动平均线是金融学中用来从短期的噪声数据中提取金融长期发展趋势的一种手段, 它通过求取某指标值在某段时间内的平均值来预测未来发展趋势。这里采用移动平均线的原理来提取平均共有邻居相似度。

定义5:假定有n个时间点的社会网络快照, 对于节点u和节点v, 其平均共有邻居相似度定义如下:

平均共有邻居相似度可以去除一些噪声数据, 从而得到一个较为平滑的长期趋势。

结合时间属性的链接预测算法设计如下:

输入:社会网络G=, 节点u, 节点v

输出:节点u和节点v的相似度

算法描述:

(1) 找出节点u和节点v在所有子图上的共有邻居;

(2) 根据定义5计算节点u和节点v的平均共有邻居相似度。

算法完毕。

3 结语

社会网络链接预测是数据挖掘的一个新的研究方向。链接预测侧重于挖掘社会网络中所隐藏的关系模式, 具有重大的研究意义。考虑节点的时间属性, 采用平均共有邻居相似度来平滑节点的动态变化, 可以有效去除噪声数据。本文将共有邻居相似算法与时间属性相结合, 提出了结合时间属性的链接预测算法。

参考文献

[1]G JEH, J WIDOM.Simrank:a measure of structural-context similarity[C].Proceedings of the eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002:538-543.

[2]张宗宇.社会化网络的链接预测[D].北京:北京邮电大学, 2011.

[3]胡谦谦.Markov逻辑网及其在社会网络中的应用研究[D].北京:北京交通大学, 2010.

[4]V LEROY, B B CAMBAZOGLU, F BONCHI.Cold start link prediction[C].Proceedings of 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010:393-402.

[5]M A HASAN, V CHAOJI, S SALEM M ZAKI.Link prediction using supervised learning[C].SDM Workshop of Link Analysis, 2006.

网络算法篇9

随着信息技术飞速发展, 互联网成为继报纸、广播、电视之后的“第四媒体”, 成为社会舆论传播的主要载体之一[1]。互联网所具有的网络传播技术特点, 使得网络舆论的表达和演化更加快捷、综合信息更加多元、舆论传播的方式也更加多样[2], 但网络舆论与社会转型期各种矛盾和敏感问题结合紧密, 且参与主体成份复杂, 不免会带来一些负面内容并造成消极影响, 若对其监管、引导不力, 将直接影响和危害社会稳定与国家安全[3]。在网络舆论传播过程中, 任何可以娴熟操作网络、个性化表达自己观点、独到参与话题讨论的网络用户, 均有可能成为网络舆论领袖[4,5]。20世纪40年代, “舆论领袖”的概念首先由美国哥伦比亚大学的传播学者保罗拉扎斯菲尔德提出[6]。网络舆论领袖的作用贯穿整个网络舆论的形成过程, 在其引导下, 部分意见可演化为公众舆论[7]。政府对网络舆论进行有效的引导和控制, 化解网络舆论危机, 识别其中的舆论领袖尤其重要, 因此该研究具有重大现实意义, 也引起了国内外学者的广泛关注。

国外对网络舆论领袖的识别研究主要集中于网络营销领域, 以剖析舆论领袖在促销活动中的作用为目的[8,9,10,11,12];国内对网络舆论领袖的识别研究一方面集中在描述性的定性研究, 另一方面则集中在基于社会网络分析的定量研究, 即以网民为节点、网民之间构成的回复关系为边构建社会网络, 再应用出入度、中心度、平均路径长度等指标对节点进行计算排序[13,14,15]。社会网络分析关注的仅仅是网络舆论事件中的舆论主体———人 (即网民参与讨论的行为) , 并未考虑外界信息是如何对网民产生影响、网民发布言论的心理驱动力如何作用等问题。若要更准确识别出网络舆论事件中的舆论领袖并剖析其在事件发生发展过程中的作用, 仅关注舆论主体回复行为是不够的, 还需要明晰舆论事件发生的六要素 (5W1H) , 即事件演变 (when) 、环境地点 (where) 、人物参与 (who) 、事件内容 (what) 、如何发生 (why) 、如何解决 (how) [16]。针对上述问题, 本文拟采用超网络 (Supernetwork) 的思想和方法对网络舆论领袖的识别进行更深层次的研究。

“超网络”最早由Sheff于1985年提出[17], 美国科学家Nagurney则最早明确提出超网络概念, 认为超网络为“高于而又超于现存网络的网络” (“above and beyond networks”) , 即由多种网络构成的网络[18,19]。超网络具有多层性、多级性、多属性、拥塞性和协调性等特征;超网络可用来描述和表示网络之间的相互作用和影响, 它的架构为研究网络之间的相互作用和影响提供了工具[20]。因此, 利用超网络的这些属性和作用可将心理、信息、观点等上升到与舆论主体平行的地位, 更好的刻画网络舆论的形成和演化过程, 在更深层次地识别网络舆论领袖并剖析其作用机理的同时, 也可挖掘出对舆论起主导作用的心理动机和对网民影响最深的环境信息内容等。

本文在建立了集社交、环境、心理和观点四层子网描述的网络舆论超网络模型的基础上, 将由网络舆论主体节点、环境信息节点、心理驱动力节点和观点关键词节点共同作用形成的超边 (SuperEdge) 作为测度对象, 提出了一种新的SuperEdgeRank算法, 对网络舆论超网络模型中的超边进行计算排序, 进而挖掘出网络舆论领袖。最后通过实例分析证明了该方法的可行性, 具有很强的理论指导意义和实际应用价值。

2 超边排序算法

2.1 网络舆论超网络建模

网络舆论超网络模型的构成要素包括舆论主体、环境外驱动力、心理内驱动力和观点关键词, 这四种构成要素的关联关系是:“舆论主体”在“环境外驱动力”和“心理内驱动力”的共同作用下, 发布了“观点关键词”。由以上四种构成要素即可构建网络舆论超网络模型的四层子网, 分别是“社交子网”“环境子网”“心理子网”和“观点子网”。

(1) 社交子网A (Social Network) 表示网络舆论中参与讨论的舆论主体 (即网民) 之间的回复关系;

(2) 环境子网E (Environment Network) 表示信息传播的过程, 一条信息的发布对应于该子网中的一个信息节点;

(3) 心理子网P (Psychological Network) 表示网络舆论主体在发布言论时所具有的心理类型, 不同心理类型之间存在转化关联关系;

(4) 观点子网K (Keyword Network) 表示网民所发布的帖子或博文中的观点 (即关键词) , 关键词节点之间的边表示这两个关键词在同一帖子或博文中出现。

网络舆论超网络模型中四层子网之间通过超边 (SuperEdge, SE) 连接, SE表示实体ai在环境em的外作用力和心理pj的内作用力下, 发表了观点kn (图1左侧) 。在本研究中每条超边只包含一个舆论主体a、一个环境e、一个心理类型p, 但可包含一到多个观点k.

2.2 SuperEdgeRank算法

PageRank算法是一种由搜索引擎根据网页之间相互的超链接计算的技术, 通过网络浩瀚的超链接关系来确定一个页面的等级[21]。把从A页面到B页面的链接解释为A页面给B页面投票, 再根据投票来源 (甚至来源的来源, 即链接到A页面的页面) 和投票目标的等级来决定新的等级。简单的说, 一个高等级的页面可以使其他低等级页面的等级提升。一个页面的PageRank值是由其他页面的PageRank值计算得到, 即表示每个页面重要性的PageRank值不只取决于链接到该页面的数量, 还受到指向该页面的质量和重要程度的影响, 而且该页面的PageRank值也会被平均分配给它链出的页面。经过不断的重复计算, 这些页面的PageRank值会趋向于正常和稳定。

以PageRank算法思想为基础, 本研究提出了网络舆论超网络模型中的SuperEdgeRank算法, 该算法可对超网络中的超边进行排序。在该算法中考虑了不同超边之间所包含的信息的传播影响度、心理类型的转化关系和观点的相似性程度等因素。在环境子网中, 某超边所包含的信息节点的信息传播影响度越高, 则该条超边越容易被“发现”, 即被其它超边链接的概率越大;在心理子网中, 某超边所包含的心理类型与其它超边若心理倾向相同且心理强度相近, 则该超边与其它超边链接获得“分值”越大;在观点子网中, 某超边所包含的观点关键词与其它超边观点关键词相似性越大, 则该超边与其它超边链接获得“分值”也越大。由此, 得出以下SuperEdgeRank算法:

其中, N表示所有超边数, 表示信息的传播影响度, pij表示心理pi与心理pj之间的关联关系, Simij表示超边SEi与超边SEj所包含关键词的相似性;L (SEj) 表示超边SEj的超边连接度。

图1展示了本文的主要研究思想, 首先建立具体舆情事件的网络舆论超网络模型, 然后分别对应环境子网、心理子网和观点子网计算社交子网中各个舆论主体参与形成超边的属性, 基于这些参数的计算, 利用提出的SuperEdgeRank算法对超边进行排序, 最后结合舆论领袖识别机制和超网络模型的属性指标识别出该舆情事件中的网络舆论领袖。下一节详细介绍SuperEdgeRank算法中超边属性的计算过程及舆论领袖的识别机制。

3 网络舆论超网络模型超边属性计算

3.1 网络舆论超网络模型示例

为了更加清晰阐述本文的研究思路和方法, 建立了以下具体网络舆论超网络模型:社交子网A中共包含8个舆论主体节点, 环境子网E中共包含3个信息节点, 心理子网P中共包含5个心理类型节点, 观点子网K中共包含15个关键词节点。表1中列出了四层子网中各层节点的对应关系, 即该网络舆论超网络模型中各条超边的组成;图2展示了该网络舆论超网络模型中某一舆论主体对应形成的两条超边, 其中超边表示社交子网中舆论主体a5在环境子网信息节点e2的外作用力和心理子网心理类型节点p4的内作用力下, 发表了观点子网中关键词节点k7、k12、k13和k14, 超边表示社交子网中舆论主体a5在环境子网信息节点e2的外作用力和心理子网心理类型节点p5的内作用力下, 发表了观点子网中关键词节点k10、k11、k13和k15.

在本文中为识别网络舆论舆论领袖需要, 提出以下两个超网络属性指标:

(1) 节点超度 (Node Superdegree)

超网络中某个节点的节点超度值定义为该节点参与组成的超边数[22]。类似于社会网络分析 (SNA) 中节点的连接度, 即出度值与入度值之和。

如在以上建立的网络舆论具体超网络模型中, 等。

(2) 超边连接度 (SuperEdge Degree)

在超网络中, 若两条超边包含有相同的节点, 就认为这两条超边通过该共同节点相连。超边连接度等于某超边通过其所包含的节点相连的其它超边的数目[23]。

如在以上建立的网络舆论具体超网络模型中, L (SE1) =11, L (SE3) =14, L (SE8) =16等。

3.2 环境子网中信息传播影响度

环境子网E中包含某一网络舆论事件发生和发展过程中所发布的所有信息 (假设共包含n条) , 每一条信息对应于一个信息节点ei (1≤i≤n) 。不同信息对事件的影响程度不同, 定义为信息传播影响度I (ei) 。信息传播影响度取决于两个指标:信息传播广度R (ei) 和信息传播深度D (ei) 。

(1) 信息传播广度R (ei)

信息传播的范围, 可通过信息ei在网络舆论超网络模型中出现的总次数和总超边数来衡量, 即ei共参与组成的超边数与模型中总的超边数比值。

其中, F (ei) 表示信息ei参与形成的超边数, N表示该网络舆论超模型中总的超边数。

(2) 信息传播深度D (ei)

信息被舆论主体传播的深入程度, 可通过该信息ei在超边中出现的总次数和受该条信息ei影响的社交子网中主体个数来衡量。

其中, F (ei) 表示信息ei参与形成的超边数, A (ei) 表示社交子网中与信息ei共同组成超边的舆论主体数, N表示该网络舆论超模型中总的超边数, Na表示社交子网中总的舆论主体数。

基于以上, 信息传播影响度由信息传播深度和信息传播广度共同决定, 其公式为:

建立的网络舆论具体模型在环境子网中共包含三个信息节点, 信息传播影响度计算结果如表2所示。

3.3 心理子网中心理转化关联度

在网络舆论事件发生发展过程中, 发布帖子或博文参与讨论的网民具有不同的心理类型, 不同心理类型具有不同的心理倾向和心理强度, 即网络舆论超网络模型中心理节点具有不同倾向和强度。

通过网络舆论主体所发布的帖子或博文内容来判断其心理类型。将心理类型pi定义为无穷区间 (+∞, -∞) 上的一个具体实数, 心理倾向由pi的正负决定, 心理强度则由pi的绝对值大小决定。

(1) pi<0, 表示心理倾向为负面 (消极) , 且心理强度为|pi|

(2) pi>0, 表示心理倾向为正面 (积极) , 且心理强度为|pi|

(3) pi=0, 表示心理倾向为中立, 且心理强度为|pi|=0

判断完心理子网中各心理节点的类型, 可对不同超边所包含的心理类型之间的转化关联关系进行度量。任取两条超边的心理节点, 若这两个心理节点的心理倾向一致且心理强度相近, 则该两条超边更有可能存在关联;否则, 若这两个心理节点的心理倾向相反且心理强度差值也较大, 则该两条超边存在关联的可能性就小。

从心理类型区间上任取两个心理类型pi和pj, 该两种心理类型所组成的超边之间存在关联关系的可能性定义为pij, 则有:

其中, sign (x) 为符号函数, 当x≥0时, sign (x) =1;当x<0时, sign (x) =-1。

在以上建立的网络舆论具体超网络模型中共有5个心理类型, 假设其中p1和p2心理倾向为消极, 心理强度分别为|p1|=2、|p2|=1;p3心理倾向为中立, 心理强度|p3|=0;p4和p5心理倾向为消极, 心理强度分别为|p4|=1、|p5|=2。由此计算该网络舆论超网络模型中5种心理类型之间的关联关系如表3所示。

3.4 观点子网中观点相似度

(1) 向量空间模型 (VSM)

向量空间模型 (VSM) 是最常用的计算对象相关度的模型[24], 其中使用较多且效果较好的方法是基于空间向量模型的TF-IDF方法, 该方法综合考虑了不同词在所有文本中的出现频率和这个词对不同文本的分辨能力, 被广泛用于计算文本之间的相似度。本文以向量空间模型 (VSM) 为基础, 计算任意两条超边所包含的观点子网中关键词的相似性。设网络舆论超网络模型中共有n条超边, 共包含m个关键词, 模型中的超边SEi (1≤i≤n) 在向量空间模型中可用以下矩阵表示:

矩阵中的元素对应于关键词kj (1≤j≤m) 在超边SEi的权重wij, “0”意味着该关键词不在超边中出现。

(2) 权重计算

观点子网中关键词的权重wij由该关键词TF的词频和逆向文件频率IDF决定。

①TF指某个指定的关键词在超边中出现的次数, 对于在某一特定超边SEi里的关键词kj来说, 它的重要性可以表示为:

其中, nij表示关键词kj在超边SEi中出现的次数, 表示超边中所有关键词出现的次数和。

②IDF指某个关键词在所有超边集合中的分布情况, 在一定程度上体现了该特征项的区分能力:

其中, N表示所有超边数, nj表示关键词kj在所有超边中出现的总次数。

由以上两个指标计算即可得关键词权重值为:

(3) 相似性计算

在网络舆论超网络模型中, 两条不同的超边的关键词相似性用向量之间夹角余弦值表示。如超边SE1和超边SE2的相似度Sim (SE1, SE2) 计算公式为:

其中, w1j、w2j分别表示超边SE1和超边SE2第j个关键词的权重值, 1≤j≤m.

以向量空间模型为基础, 计算所建立的网络舆论超网络模型中所有超边之间关键词相似性结果如表4所示。

4网络舆论领袖识别计算

4.1 SuperEdgeRank排序结果

借助MATLAB编程工具, 利用本研究提出的Super-EdgeRank算法对以上建立的网络舆论具体超网络模型进行计算, 得出该模型中17条超边的分值与排序结果如表5所示。

4.2 舆论领袖识别机制

对所有超边进行排序计算后, 对应找到社交子网中舆论主体ai参与形成的所有超边的分值, 然后结合节点超度, 计算各个舆论主体的平均超边分值, 得分高者即为舆论领袖。

其中:表示节点ai参与形成的超边的分值;表示节点ai的节点超度值。

经过计算, 在建立的网络舆论具体超网络模型中, 得分最高的舆论主体为a5 (Score (a5) =0.3036) , 在该舆论具体超网络模型中舆论领袖为a5, SuperEdgeRank得分最高的超边SE10和SE13均由舆论主体a5组成;得分最高的环境信息为e2, 说明该信息对整个舆论事件的传播发展影响最大;得分较高的心理类型为p4和p5, 说明在该舆论事件中负面消极心理起主导作用。

5 实例应用

5.1 案例简介

2011年3月11日, 日本本州岛附近海域发生里氏9.0级强震并引发海啸, 造成日本核电站发生核泄漏, 大批居民被疏散。核泄漏事件亦引发我国网民极大关注, 从3月16日开始, 中国部分地区开始疯狂抢购食盐, 许多地区的食盐在一天之内被抢光, 期间更有商家趁机抬价, 市场秩序一片混乱。引起抢购的是两条消息:食盐中的碘可以防核辐射;受日本核辐射影响, 国内盐产量将出现短缺。随后环保部与各地盐务管理局发布辟谣信息, 至3月18日, 各地盐价逐渐恢复正常, 抢盐谣言平息。

依据舆情信息监测平台, 从凤凰论坛、天涯社区、人民网强国论坛、新浪、网易等收集关于“日本核泄漏事件”的有效网民帖1019条 (集中在2011.03.17和2011.03.18两日) (图3) , 话题参与者共671人。

5.2 基础数据处理

“日本核泄漏事件”发生后立刻引起我国民众的极大关注, 发展演化至2011.3.17和2011.3.18日达到最高峰, 并引起国民恐慌和抢盐事件, 至2011.3.27日事件逐渐平息。本文截取事件的整个发展演化过程的所有话题参与者为研究对象, 构建话题参与者及其对应的环境、心理、观点共同组成的该事件网络舆论超网络模型, 超网络模型中部分超边如表6所示。表中每一行代表一条超边, 在任意一条超边中包含一位舆论主体ai、一个环境信息ei、一个心理类型pi, 以及该舆论主体在环境信息外作用力和心理类型内作用力共同作用下所发布的所有观点ki.

在“日本核泄漏事件”发展过程中, 共有三个主要环境信息, e1表示“日本地震, 导致核泄漏事件发生”, e2表示“网民发布谣言, 曝日核电站实为核武库, 且污染到达我国, 民众抢购碘盐”, e3表示“环保部以及各地盐务总局发布辟谣消息”;心理倾向分为正面、中立和负面, 心理强度由其对应舆论主体发布的带观点倾向的关键词个数决定;从所有的网民帖中共提取出20种不同的观点关键词, 其中正面观点包括“k1相信中国政府和日本政府均能做好防核辐射工作”“k2不相信日本核武库实验传闻”“k3国内碘盐供应充足, 不听谣言盲目抢盐”;中立观点包括“k4关注日本震后救援情况”“k5就如何防止核泄漏问题的讨论”“k6关注核泄漏污染现状”等;负面观点包括“k14认定日核电站为核武器”“k15对日本地震幸灾乐祸”“k16散布抢盐谣言”等。

注:在观点关键词列中, “1”表示该舆论主体在对应环境信息和心理类型下发布了的观点, “0”表示该舆论主体未发布该观点。

5.3 舆论领袖识别结果

以建立的“日本核泄漏事件”超网络模型为基础, 借助MATLAB工具编程, 利用本研究中提出的SuperEdgeRank算法对该模型中的各条超边进行排序, 并根据舆论领袖识别机制计算各个舆论主体的超边平均分值, 从671位舆论主体中识别出十位主要舆论领袖, 分别为:愤青N01 (0.0151) 、星榜样 (0.0151) 、十八摸 (0.0138) 、社会评论 (0.0131) 、蓝冰说梦 (0.0124) 、波浪鼓007 (0.0110) 、草山铁 (0.0104) 、天堂大补丁 (0.0104) 、多功能钢菜刀 (0.0090) 、快乐88888 (0.0035) , 括号中为该舆论领袖对应的超边平均分值, 表7中列出了该事件中三维舆论领袖超边具体组成, 心理倾向分别为负面、中立和正面。在识别出该事件的主要舆论领袖的同时也通过该算法得出, 在该事件中起主要影响的环境信息为e2 (谣言:曝日核电站实为核武库, 且污染到达我国, 民众抢购碘盐) , 主导整个事件发展的心理类型为负面消极心理。

6 结束语

本文将超网络分析法应用到网络舆论领袖的识别研究中, 并提出了基于超边排序算法的SuperEdgePage算法。首先简要介绍了网络舆论超网络模型的建立, 主要包括四个子网络层:社交子网、环境子网、心理子网和观点子网;然后对建立的网络舆论超网络模型的超边之间关联关系属性进行计算, 分别用到了信息传播影响度、心理类型转化关联关系和观点关键词相似性计算;基于这些属性计算, 提出了一种新的SuperEdgePage算法对网络舆论超网络模型中各条超边进行计算排序, 并通过社交子网中舆论主体参与组成的超边的平均分值排序识别该舆论事件中的主要舆论领袖;最后通过“日本核泄漏事件”实例应用, 证明超网络分析法和SuperEdgePage算法在网络舆论领袖识别研究中的可靠性和创新性。

进一步的工作是在舆情超网络中识别出舆论领袖后如何实施相应的引导和干预策略。目前对网络舆论的管控, 多是通过把关人对负面舆论领袖发言进行删帖、沉帖等, 这种干预策略是不全面的, 甚至有时可能会有激起民愤的反作用。应对网络舆情危机, 要疏堵结合, 如针对某具体舆情事件网民主要心理类型进行网民教育、有意识培养正面舆论领袖, 探索不同倾向舆论领袖之间的博弈关系以及两者对网络舆论传播的作用机理等, 这就需要在舆情超网络中进行更深入的仿真模拟研究。

SENMA网络加权质心定位算法篇10

关键词：移动代理无线传感器网络,RSSI,加权质心定位算法

0引言

文献[1]中提出了一种特殊的无线传感器网络 (WSN) ——移动代理无线传感器网络 (SENMA) 模型。该网络模型不仅与一般的WSN相比有着许多优点, 特别是具有先天的节能优势, 而且针对在战场或其他恶劣环境中进行信息采集有着实际应用意义。

在移动代理传感器网络中进行节点定位需要采用基于距离的定位算法, 而且依据该网络特点基于RSSI测距较为可行。一般基于RSSI测距定位方法首先通过测量接收信号强度, 根据两点间信号传输衰减程度来判断两点间距离;然后再依据所获得的足够多的锚节点位置信息计算未知节点的位置 (二维、三维空间分别需要3个以上、4个以上锚节点信息) 。

通过分析信道RSSI特点, 给出了一种适用于SENMA网络的加权质心定位算法, 并通过仿真进行了算法验证, 其性能优于极大似然估计。

1SENMA网络

SENMA由一般传感器节点和移动代理节点组成。一般传感器节点负责采集信息和被动传输信息, 其具有较低的能量和有限的处理能力、通信能力, 它们可以通过飞机播撒或者其他途径随机分布在一定的地域中, 例如战场或其他恶劣环境中。移动代理节点具有很强的通信能力和数据处理能力, 而且能够在整个传感器网络中移动, 使其通信范围覆盖整个传感器网络。例如可以位于有人或无人驾驶的飞机上。这些移动代理与卫星 (或其他固定中继基站) 之间存在高速率数据连接, 可以及时地将数据发送给远端控制中心。移动代理节点不需要一直出现在传感器网络区域上方, 在需要收集数据或者进行网络控制时它们才开始活动。移动代理无线传感器网络定位模型如图1所示。

SENMA网络具有如下特点:

① 在普通传感器网络中, 节点间的信息沿地表传播, 信号衰落与距离的4次方成正比;而在SENMA网络中, 传感器节点之间基本不通信, 而传感器节点与移动代理通信, 信号在自由空间中传播, 根据信号衰落与传输距离关系可知, 自由空间中信号的衰落与距离的2次方成正比, 从而信道传输环境优于普通传感器网络;

② SENMA是单跳网络, 信息处理和网络维护由移动代理节点进行, 不需要维护路由信息和相邻节点信息, 因而花费在控制上的能量开销要少;

③ SENMA中不需要传感器节点存储转发数据, 接收信息的消耗能量很少;

④ 传感器节点是能量受限的, 但移动节点能量可以补充。

SENMA网络把复杂的数据处理、接入处理、数据转发传输和路由维护等工作由移动代理节点来完成, 减轻传感器网络的能量负担, 从而SENMA 的网络结构有先天的节能优势, 具有更长的生存时间。

SENMA网络中, 一般传感器节点负责采集信息和被动传输信息, 彼此之间几乎不进行通信。与此同时移动代理节点可以充当网络中的锚节点, 在移动中时时发送当前时刻自身位置信息, 传感器节点可以在接收当前时刻移动代理节点位置信息的同时, 采用测距技术测距, 若记录了足够多的移动代理节点位置信息和距离信息后即可估算节点自身位置信息。

目前主要测距方法包括TOA、TDOA和RSSI等。TOA技术需要精准系统时钟同步, TDOA技术需要节点具有超声波发射和接收设备, 并且测距范围有限。移动代理在高空飞行, 一般可以认为与一般传感器节点间属视距通信, 因此研究了基于RSSI测距的SENMA网络定位算法。

2SENMA网络定位算法

2.1SENMA网络定位模型

如图1所示, 可以近似认为传感器节点位于同一平面, 并假设该平面与水平面平行。如果在ti时刻接收到移动代理节点位置信息 (Xi, Yi, Hi) , 并测得当前时刻移动代理节点与节点A的距离Ri, 设移动代理节点在传感器网络所在平面的投影为O (Xi, Yi) , 则OA之间的距离为:

$l_{i} = \sqrt{R_{i}^{2} - Η_{i}^{2}}$ 。 (1)

任务是由 (Xi, Yi, li) 估测节点A的二维坐标 (x, y) 。

2.2RSSI信道模型

RSSI定位是通过测量接收信号强度, 根据两点间信号强度判断两点间距离。无线信号在传播路径中都会产生信号的衰减, 信号接收的强度受到影响, 实际测量值也会因为环境的不同而不同。通过大量的现场测量数据归纳“距离-损耗”模型一般形式为:

$p = p_{0} + 10 n \log [\frac{R + v}{R_{0}}] + X$ dB。 (2)

式中, p为传感器节点接收到由移动代理节点发射信号的接收功率, 单位dB;R0为参考距离, 单位为m;p0表示距离为R0时的接收信号强度, 单位为dB;R为移动代理节点与传感器节点之间的距离;v为移动代理节点的运动速度;X为与传播距离无关的随机变量, 通常可以认为是标准偏差为σ的正态随机变量;n为路径损耗系数即环境因子。

实际上, 由于多径、绕射和障碍物等因素, 无线电传播路径损耗与理论值相比有很大变化。节点到信号源的距离越近, 由RSSI值的偏差产生的绝对距离误差越小, 反之, 产生的绝对距离误差越大。

在X和环境因子已知时, 通过对接收功率的测量可以计算出不同时刻移动代理节点与未知定位节点之间的距离R1、R2、R3。理论上通过接收3个 (二维空间) 已知空间节点的RSSI信息就可用三边测量法决定一个未知节点的位置。但实际应用环境中, 因为RSSI值含有随机分量, 无法精确计算未知节点位置, 所以只能采用质心法或极大似然估计法。

3加权质心定位算法

当一个待定位传感器节点A收到不同时刻移动代理节点的位置信息, 并根据RSSI值确定与空间O、P、Q点距离可以得到l1=LAO、l2=LAP、l3=LAQ。

如图2所示, 由于测距误差, ΔOPQ可能出现以下3种情况:

如图2 (a) 所示, 圆O与圆P相切, 则相切点为A点第1个近似位置 (x1, y1) ;

如图2 (b) 所示, 圆O与圆P相交, 2个交点为A点可能位置A1点和A2点, 计算|LAO-LA1O|和|LAO-LA2O|, 二者小者为A点第1个近似位置 (x1, y1) ;

如图2 (c) 所示, 圆O与圆P相离, 直线OP与圆O、圆P相交于B点、C点, B点、C点中心为A点第1个近似位置 (x1, y1) 。

同理在ΔPQO、ΔQOP中得到A的第2个、第3个近似位置 (x2, y2) 、 (x3, y3) 。计算点 (x1, y1) 、 (x2, y2) 、 (x3, y3) 的质心作为A点估测值。

当节点A收到m个信标节点信号时, 可以构成C $_{m}^{3}$ 个三角形, 每个三角形可产生一个近似的待测传感器节点坐标置位。再次利用质心算法即可求出节点A的最终位置坐标。

前文已经指出由于多径、绕射和障碍物等因素, 无线电传播路径损耗与理论值相比有很大变化。而且随着传感器节点与移动代理节点 (其投影) 的距离越远产生的绝对距离误差越大。由RSSI测距误差会严重影响节点定位精度, 为此设计了加权质心算法:

① 移动代理节点周期性发送自身位置信息, 运动速度等信息;

② 传感器节点在收到信息后, 记录移动代理节点投影位置信息, 测定RSSI, 依据测定RSSI值计算自身节点与观测点投影之间的距离 (式 (1) 、式 (2) ) ;

③ 传感器节点在收到超过阈值m个信标信息后, 对信标节点依RSSI值从大到小排序。采用RSSI值小的前n个移动代理节点投影位置信息进行定位计算;

④ 由n个观测点投影构成C $_{n}^{3}$ 个三角形, 若取n=4, 这些三角形顶点距待测点A的距离为: (l1、l2、l3) 、 (l2、l3、l4) 、 (l3、l4、l1) 、 (l4、l1、l2) , 计算出与之相对应的n个可能位置: (Ax1, Ay1) 、 (Ax2, Ay2) 、……;

⑤ 对n个可能位置加权求质心得到位置信息。n=4加权求质心为式 (3) 、式 (4) 、式 (5) , n>4可依此类推。

4仿真实验

利用Matlab编程进行计算机仿真。移动代理节点距离传感器网络平面为150 m, 有效通信距离为150～250 m。RSSI与距离的关系由式 (2) 决定。因为移动代理无线传感器网络工作与室外环境, 路径损耗较自由空间大, 式 (2) 中的衰减因子n设为3.2, 高斯分布随机变数X的标准方差取为4。为方便计算取R0=1 m。传感区域为400 m×400 m, 移动代理节点均匀地通过传感区域, v=25, 传感器节点数为50, 随机布置于传感区域。算法中选取n个观测点数据进行仿真计算, n分别取5, 10, 15, 20, 25。同时利用加权质心算法和极大似然估计法仿真计算比较。

图3和图4分别为最大误差和平均误差仿真结果, 从图中可以看出加权质心算法定位精度优于极大似然, 特别是在信标节点密度较低的情况下, 优势更加明显。

5结束语

SENMA网络属于立体网络, 进行节点定位采用基于RSSI测距的方法较为可行。由于多径、绕射和障碍物等因素, 传感器节点与移动代理节点的距离越远, 测量RSSI误差越大, 从而影响节点定位精度。为此, 设计了加权质心算法, 利用加权因子体现各观测位置对质心位置的影响程度, 反映了它们之间的内在关系。通过仿真验证了加权质心算法定位精度优于极大似然算法。

参考文献

[1]TONG L, ZHAO Q, ADIREDDY S.Sensor Networks with Mobile Agents[J].Boston:Military Communications Conference, 2003, 10 (1) :688-693.

[2]郑杰比, 唐碧华, 刘元安, 等.移动性无线传感器网络的研究[J].传感器世界, 2006, 7 (12) :32-34.

[3]BAHL P, PADMANNBAN V N.RADAR:An In-building RF-Based User Location and Tracking System[C].Israel:IEEE Computer Society, 2000:775-784.

本文来自 360文秘网(www.360wenmi.com)，转载请保留网址和出处

【网络算法】相关文章：