自组织算法论文

2024-06-21

自组织算法论文（共8篇）

自组织算法论文篇1

摘要：针对神经网络逼近非线性函数问题,提出一种在线的自组织小脑神经网络,其不需要预先确定存储空间的大小。该网络可以根据输入数据自适应地改变神经网络节点数和相对应的权值,具有良好的智能性;针对挠性卫星姿态控制,将自组织小脑神经网络用于不确定项的补偿中,提高系统的鲁棒性。仿真结果表明,该方法神经网络性能良好,实现了卫星姿态控制。

关键词：自组织小脑神经网络,非线性逼近,卫星姿态控制

0 引言

传统的小脑神经网络计算速度快,应用越来越广泛。但是其基函数为常数0或者1,只能记忆静态信息,泛化能力差,精度不高。Chiang 和Lin [1]研究一种高斯基函数的小脑神经网络,输入信号根据输入状态空间的范围划分高斯基函数的中心,将输入信号与基函数相关联的对应地址空间里的相应权激活,经过加权得到输出。但是上述神经网络高斯基函数中心点的选取和输入的最大最小值有关,在实际应用中,在线学习不确定时很难预测最大最小值,这样的网络存储空间的大小很难确定,结构不能自动获得,影响学习和控制的性能,因此一些能够自适应地改变神经网络结构的网络受到重视。

Hu和Pratt[2]研究了可以根据输入数据来改变自身结构的方法,但是这种方法运用了不可微分的阶梯性质的基函数,并且只研究了结构增加的方法,没有研究减少结构的方法。C.M.Chen[3]提出了一种自组织的遗传算法的小脑神经网络,运用了信息熵结合黄金分割的方法来决定结构的增加和减少,这种方法的缺点是结构过于复杂,缺乏在线的学习能力。

该文研究了一种自组织小脑神经网络在线逼近非线性函数,这种网络不需要预先确定存储空间的大小,可以根据输入数据自适应地改变神经网络节点数和相对应的权值,具有良好的智能性,并且可以达到全局收敛。针对挠性卫星姿态实例,采用变结构控制,并用神经网络补偿系统不确定性。

1 自组织小脑神经网络算法研究

自组织小脑神经网络是在高斯基小脑神经网络的基础上提出的。如图1为高斯基函数神经网络,输入x是n维空间,输出为:

$y_{s} = \sum_{j = 1}^{Ν_{h}} a_{s}^{Τ} w_{j} (x_{s})$ , (1)

式中,as为基函数的选择矢量,有C个单元等于1,其余视为0,相当于以输入数据为中心,以C作为边长,作了一个超立方体。其中:

wj(xs)=vjbj(xs), (2)

式中,vj为权值,bj(x)为径向基函数,基函数中心点和方差是在已知每维输入空间大小情况下选取的。写成矢量形式:

但上述的高斯基函数的小脑神经网络前提是已知了输入X的范围,在实际应用中多数不知道范围大小,在这种情况下,自组织小脑神经网络根据输入大小来增加或者减少节点数。此时:

$y_{s} = \sum_{j = 1}^{Ν_{h}} w_{j} (x_{s})$ 。

1.1 增加节点数

已经存在的节点可以叫做族。如果一个新的输入量的值在这个族的范围内,则自组织小脑神经网络不会再产生新的节点,只是改变权值[5,6]。

在联想存储空间中定义:

MDk(xs)=‖xs-uk‖2k=1,…,nk, (4)

式中,uk= $[\begin{matrix} u_{1 k} & \dots & u_{i k} & \dots & u_{n k} \end{matrix}]$ 是网络中已经存在的节点。用如下理论来确定节点数的增加。找到:

$\hat{k} = \arg \min_{1 \leq k \leq Ν_{j k}} Μ D_{k} (x_{s})$ ,

如果满足MDk(xs)>Kg,Kg是预定好的最低限度,则产生一个新的节点。这意味着对于一个新的输入数据,如果这个数据跟与族里面的已经存在的节点的中心距离都大于一个设定值,即表示现有的族太小,则需要产生一个新的节点。产生如下的节点:

nk(t+1)=nk(t)+1, (5)

这里的nk(t)是已经存在的节点数目,新产生的节点的中心和方差设置为:

1.2 减少节点数

考虑第j个输出,定义:比例

$Μ Μ_{j k} (x) = \frac{v_{j k} (x)}{y_{j} (x)}$ , (7)

式中,yj(x)是第j维输出,vjk(x)是输入数据与第k个中心节点的权值,MMjk(x)表示这个输入数据与第k个节点的权值在整个输出的比例。可以找到第j个输出中最小的比例,即:

$\tilde{k} = \arg \min_{1 \leq k \leq Ν_{j k}} Μ Μ_{j k} (x)$ 。 (8)

设Kc是预定的上限,如果满足: $Μ Μ_{\tilde{j k}} (x) \leq Κ_{c}$ ,则第k个节点应该删除。这意味着,对于一个输出数据,如果某个节点对于输出的贡献小于一个设定的值,则这个节点应该被删除。

定义误差函数 $E = (\hat{y}_{s} - y_{s})^{2} / 2$ ,使得E最小,则权值修正如下:

$\begin{array}{l} Δ v_{k} = - x i t e \frac{\partial E}{\partial v_{k}} = - x i t e \frac{\partial E}{\partial w_{k}} \frac{\partial w_{k}}{\partial v_{k}} = \\ x i t e (\hat{y}_{s} - y_{s}) a_{s, k} b_{k} (x_{s}) ‚ (9) \end{array}$

vi(k+1)=vi(k)+Δvi(k)+alfa(vi(k)-vi(k-1))。 (10)

2 应用实例

该文将自组织小脑神经网络应用于挠性卫星姿态控制中。挠性卫星姿态控制系统状态方程为:

取状态向量 $x = [x_{1}, x_{2}] = [θ, \dot{θ}]^{Τ}$ ,式(11)写成状态方程形式[7]:

式中, $Τ_{t} = F_{s} \cdot 2 ξ_{s} Ω_{s} \dot{η}_{s} + F_{s} Ω_{s}^{2} η_{s} + Τ_{d}$ ;定义期望状态向量 $x_{d} = [θ_{r}, \dot{θ}_{r}]^{Τ}$ ,则误差向量e=xd-x=[e,e1]T,式(12)转换成误差模型:

选取滑面 $s = k_{c} e + e_{1} = k_{c} e + \dot{e} ‚$ 对s求导,令 $\dot{s} = 0$ ,即 $\dot{s} = k_{c} \dot{e} - (Ι_{s} - F_{s} F_{s}^{Τ})^{- 1} Τ_{c} - (Ι_{s} - F_{s} F_{s}^{Τ})^{- 1} Τ_{t} + \ddot{θ}_{r} = 0$ ,得到等价的控制力矩:

$\begin{array}{l} Τ_{e q} = (Ι_{s} - F_{s} F_{s}^{Τ}) k_{c} e_{1} - Τ_{t} - (Ι_{s} - F_{s} F_{s}^{Τ}) \ddot{θ}_{r} = \\ (Ι_{s} - F_{s} F_{s}^{Τ}) (k_{c} e_{1} - \ddot{θ}_{r}) - Τ_{t} 。 (14) \end{array}$

变结构控制选择为:

式中,Tf为常数,δ为消颤因子。卫星的姿态控制律为:

Tc=Teq-Tvsc, (16)

由于参数ηs、 $\dot{η}_{s}$ 和Is有摄动现象,外界扰动Td未知,因此变结构的鲁棒性不能保证。此时可以用神经网络逼近特性来估计不确定性Tt,设Tnn为神经网络输出,以Tt与Tnn之间的差值来更新神经网络的权值,通过调节权值,实现对干扰力矩的补偿。则等价控制力矩变成:

$Τ_{e q} = (Ι_{s} - F_{s} F_{s}^{Τ}) (k_{c} e_{1} - \dot{θ}_{r}) - Τ_{n n}$ 。 (17)

系统的总控制力矩为:

$Τ_{c} = (Ι_{s} - F_{s} F_{s}^{Τ}) (k_{c} e_{1} - \ddot{θ}_{r}) - Τ_{n n} - Τ_{v s c}$ 。 (18)

神经网络与变结构控制相结合,使控制器既具有变结构控制对扰动不敏感的特点,又具有神经网络在线学习的能力,可加快系统响应速度,提高系统的抗干扰能力。

3 仿真分析

该文设计的姿态机动角度为70°,挠性卫星模态为4阶,执行机构为飞轮,控制力矩带有饱和特性。

变结构控制中边界层厚度δ为0.08,滑模面系数kc为0.4,边界层参数Tf为30,神经网络参数xite为0.2,alfa为0.08,加节点的时候Kg为0.001,减节点的时候Kc为0.000 01。

经过仿真,发现在有外加干扰Td=sin(t)时,用滑模控制,不用神经网络补偿时,如图2所示,角度和角速度波动比较大,精度不高。

用自组织小脑神经网络补偿干扰,如图3、图4和图5所示,在80 s角度和角速度达到要求精度,模态幅值为±0.003之间振动,可见神经网络提高了系统的鲁棒性。通过仿真发现,在未知干扰大小的情况下,小脑神经网络收敛速度快,误差小,网络的节点数随着输入的变化而变化,做到了自适应调节节点的目的,最后收敛于一个固定值,而且避免了局部极小的现象。

4 结束语

该文设计一种自组织小脑神经网络,这种网络计算速度快,可以根据输入自适应增加或者删除节点。针对挠性卫星姿态机动控制,由于外加力矩Td在实际中是未知的,而且变化剧烈,采用自组织小脑神经网络对不确定性进行补偿,得到了良好的控制效果。

参考文献

[1]CHIANG C T,LIN C S.CMAC with General BasisFunctions[J].Neural Networks.1996,9(7):1199-1211.

[2]HU J,PRATT F.Self-organizing CMAC Neural Networksand Adaptive Dynamic Control[J].IEEE IntelligentControl,1999:259-265.

[3]LEE H M,CHEN C M,LU Y F.A Self-organizingHCMAC Neural-network Classifier[J].IEEE Trans.,2003,14(14):15-27.

[4]LIN Chin-min,CHEN Te-yu.Self-Organizing CMACControl for a Class of MIMO Uncertain Nonlinear Systems[J].IEEE Transactions on Neural Networks,2009,20:1377-1384.

[5]ALEXANDRIDIS A,SARIMVEIS H,BAFAS G.A NewAlgorithm for Online Structure and Parameter Adaptation ofRBF Networks[J].Neural Networks,2003:1003-1017.

[6]QIN Ting,CHEN Zong-hai,ZHANG Hai-tao,et al.ALearning Algorithm of CMAC Based on RLS[J].NeuralProcessing Leters.2004,19(3):49-6l.

[7]李广兴,周军,周凤岐.挠性卫星高精度智能控制及物理仿真实验研究[J].中国空间科学技术,2007,1:9-13.

自组织算法论文篇2

多维优化问题的一个自适应两点步长算法

给出了克服牛顿算法缺陷的自适应两点步长的.算法.利用拟牛顿性质得到包含前两个迭代点有关信息的迭代步长因子解析表达式,无论初始迭代点与最优解之间是否存在Hesse矩阵不正定点、鞍点和广义拐点,迭代点列自动快速逼近最优解,该算法具有自适应性且仍具有二阶收敛速度;证明了算法的收敛性,并给出了算例,利用Mathematics数学软件验证了算法的有效性.

作者：尹忠海李炳杰作者单位：空军工程大学,电讯工程学院基础部,陕西,西安,710077刊名：西安电子科技大学学报(自然科学版) ISTIC EI PKU英文刊名：JOURNAL OF XIDIAN UNIVERSITY年，卷(期)：29(6)分类号：O221关键词：牛顿算法 Hesse矩阵步长因子二阶收敛

自组织算法论文篇3

物联网即物物相连的互联网, 它主要通过射频识别、红外感应器、全球定位系统、激光扫描器等信息传感设备, 按约定的协议, 把任何物品与互联网连接起来, 进行信息的交换和通讯, 以实现智能化识别、定位、跟踪、控制和管理的一种网络。所以, 从结构上, 物联网可以简单理解为互联网与传感器网络 (Sensor Network) 或者个人区域网 (Personal Area Network) 的互联与融合。

无线传感器网络 (Wireless Sensor Network, WSN) 作为一种全新的信息获取和处理模式, 集成了传感技术、嵌入式计算技术、分布式信息处理和无线通信技术, 可广泛应用于国防军事、科学研究、工农业生产、医疗护理等领域, 已成为国内外研究热点。作为其核心技术之一, 无线传感器网络路由协议更是目前研究的热点。

由于传感器往往需要放置在一些环境复杂、布线难度大以及移动的区域, 所以研究无线传感器网络的能耗问题是目前传感器网络研究的核心问题之一。射频模块是节点中最大的耗能部件, 而MAC (Media Access Control) 协议直接控制射频模块, 它是优化的主要目标。早期提出的MAC协议, 如Pico Radio, SMACS等, 大多采用多信道。多信道模式增加了节点复杂性、成本和功耗。目前常用的节点, 例如Xbow公司的Mica系列只有一个射频模块, 并且只用一个频率工作, 因此, 提出的MAC协议都采用单一信道。比较有代表性的几个协议有MAC、T-MAC、wise MAC、B-MAC、BMA、D-MAC和IEEE802.15.4等[2]。

分簇算法是指在网络规划初期通过完全分布式算法将网络划分成为簇首节点与成员节点。无线传感器网络中分簇的概念最早是在分组无线网中提出的, 当时主要用于层次型路由。随着研究的不断深入, 迄今为止, 己经提出了大量的分簇算法来构造和维护分簇网络结构。基于分簇的无线传感器网络, 能完成路由功能, 减少路由算法的开销, 方便地管理移动节点, 控制信道接入, 对信息进行压缩和融合, 从而有效减少网络负荷, 提高网络资源的使用效率, 延长网络寿命[3~4]。

无线传感器网络路由协议的分类基本上延续了传统Ad hoe网络的分类方法, 根据不同角度可以进行不同的分类。根据网络管理的逻辑结构可分为平面路由和层次结构路由两类[5]。

1 平面结构路由

平面结构路由的优点是网络中没有特殊的节点, 各节点在网络中的地位平等, 并且网络流量均匀地分散在网络中, 路由算法也易于实现。缺点在于这种路由策略使得网络不具备可扩展性, 且缺乏对通信资源的优化管理, 在一定程度上限制了网络规模。

2 层次结构路由

分层路由协议包括成簇协议、簇维护协议、簇内路由协议三个部分。成簇协议解决如何在动态分布式网络环境下使移动节点高效地聚集成簇, 它是分层路由协议的关键。簇维护协议解决在节点移动过程中的簇结构维护, 其中包括节点退簇和入簇, 簇的产生和消亡等功能。层次路由协议比较适合于无线传感器网络。

为了满足无线传感器网络数据传输及低能耗长寿命的独特需求, MIT的Heinzel man等人提出低功耗自适应分簇路由协议 (Low Energy Adaptive Clustering Hierarchy, 简称LEACH) 路由协议。它是无线传感器网络最早提出的一种自组织自适应分簇路由协议。其主要出发点是考虑一簇内能量消耗的问题, 目的是为了延长节点的工作时间, 并且实现节点的能耗平衡。与一般的基于平面结构的路由协议和静态的基于多簇结构的路由协议相比, LEACH可以将网络整体生存时间延长15%。

笔者曾在硕士研究阶段做过相应的研究, 提出过无线传感器网络分布式节能分簇算法 (Distributed Energy-efficient clustering, 简称DEEC) 正是基于LEACH算法。DEEC首先对网络的分簇结构进行了改进, 增加了聚集节点aggregator和发送节点sender, 使簇内成员分工进一步细化, 避免了数据融合和数据发送都集中在簇首head上, 降低了簇首的能耗, 均衡了整个网络的能耗;其次, 引入平均能量估算方法, 使网络在分簇过程中选择簇首的时候以平均能量为参考, 将节点的剩余能量与之作比较, 将节点剩余能量与簇首选举的概率联系起来, 这样就能使能量高的节点更容易成为簇首, 而剩余能量越小的节点越不容易成为本轮簇首, 平衡了网络能量, 进而可以达到延长网络寿命目的;最后, 在稳定运行阶段, 可采用多跳路由传送数据达到节省节点剩余能量的目的, 该算法同时考虑了链路的通信开销和中间节点的能量, 是对网络整体能耗和节点负载均衡的一种折衷方法。

总结以上内容, 可以得到DEEC算法主要分为三步: (1) 根据节点剩余能量确定成员节点当选为簇首节点的概率。 (2) 根据成员节点距离簇首节点最近的原则进行分簇。 (3) 确定簇内汇聚节点aggregator进行数据融合处理, 确定信息发送节点sender, 通过多跳路由方式给Sink传输数据。

通过用MATLAB软件对三种路由协议算法的仿真, 从网络节点生存寿命和数据通信能力两个方面对仿真结果进行对比、分析, 结果表明, 与LEACH及LEACH-C相比, 改进的DEEC算法有效地降低了无线传感器网路系统的整体能耗, 网络寿命明显延长, 数据通信能力极大增强, 并具有更好的网络规模扩展性。

随着各种通信技术的深入研究和发展, 目前4G技术LTE已经在国内部分城市大规模试验, 人类社会将进入一个新的信息化时代, 将实现智能家居和工业智能化, 相信物联网在各种传感器网络技术的发展下将在不久的将来得以实现。

摘要：随着各种通信技术的发展, 物联网将在下一代通信网络得到长足的发展和大规模的应用, 其中无线传感器网络是组成物联网的一个重要部分, 对无线传感器网络的研究, 特别是对无线传感器网络能耗方面的研究是目前的一项研究热点。本文提出的一种面向能耗控制的自组织算法DEEC就是解决无线传感器网络能耗问题, 提高网络寿命的一种算法。

关键词：物联网,无线传感器网络,自组织算法,DEEC

参考文献

[1]王承恕.通信网新技术[M].北京:人民邮电出版社, 2006 (1) .

[2]孙天.无线传感器网络LEACH协议的探讨及改进[J].传感器世界, 2005, 11 (1) .

[3]邓鳌.无线传感器网络路由协议研究与仿真[D].武汉:武汉理工大学, 2007.

[4]朱洪雷.无线传感器网络LEACH分簇路由算法研究[D].广州:广东工业大学, 2009.

自组织算法论文篇4

自组织竞争网络是一种无导师学习的人工神经网络, 通过竞争机制自动地寻找样本中的内在规律与本质属性, 自组织自适应的改变网络参数。其基本思路是网络竞争层各神经元竞争对输入模式的响应机会, 最后的只有一个神经元成为竞争的胜利者。并对那些与获胜神经元有关的各连接权一同朝着更有利于它竞争的方向调整。获胜的神经元就表示对输入模式的分类。除了竞争方式外, 还可以通过抑制方式、侧抑制方式获胜[1]。

基本的自组织竞争网络由输入层和竞争层组成。可假设竞争层有m个神经元, 输入层有n个神经元, 网络拓扑结构如下图1-1所示。

所对应的网络权值为:

自组织竞争网络具有较好的动态性能, 能够自我学习, 并根据所记忆的学习方式对输入模式进行最接近的分类, 即以竞争层获胜神经元表示分类结果。

2 基于迭代算法的改进神经网络

2.1 算法提出

本文将描述输入模式的变量定义为特征变量。根据1, 自组织竞争网络能够通过自我学习进行模式分类, 在特征变量充足且所有输入模式类别未知的情况下可以得到唯一且较为准确的分类结果。经MATLAB仿真试验, 在部分模式类别已知的情况下训练自组织竞争网络, 可能出现分类结果无法复现的情况 (即两次或多次分类结果不一致) , 故该情况下会得到失准的分类结果。

为弥补这一缺陷, 本文将引入迭代算法对部分模式类别已知情况下的分类结果进行校准。

2.2 算法描述

定义未知类别的模式为未知模式, 已知类别的模式为已知模式。改进算法的基本思路是为每一个未知模式赋一个随机的初始类别, 并与已知模式混合进行第一次分类。若分类结果与初始分类结果不一致, 则将已知模式的类别还原后重新进行一次分类;不断重复分类过程, 直至所有模式的类别不在发生改变。此时得到最终的模式分类结果。

定义Si, k为第i号模式在第k次迭代中的类别。以将n个输入模式分成t类为例, 则Si, k满足下列约束条件:

根据上述描述可知, 得到最终分类结果的充要条件是迭代收敛。迭代收敛的条件方程为:

引入迭代算法, 可使自组织竞争网络自我校准, 满足收敛条件方程, 得到唯一而可靠的分类结果。

2.3 仿真结果

验证迭代自组织神经网络算法的分类功能。

以我国南方某城市为例, 共3个城区, 分别为L区、O区、W区, 为城市中的小学划定所属区域可便于教育管理与辖区入学。已知3所小学的分区情况, 根据经纬度坐标为其余9所学校划定所属区域。

分别采用自组织竞争网络与迭代自组织神经网络进行分区, 得到MATLAB仿真结果如下。

(1) 已知分区:

L区:西山小学O区:塘下小学W区:新川小学

(2) 自组织神经网络分类结果:

L区:西山小学, 广场小学, 东方小学, 实验小学;

O区:塘下小学, 曲溪小学, 源口村小学, 南汇小学, 茶山小学;

W区:新川小学, 光明小学, 桥头小学。

仿真时间:4.5秒

(3) 迭代自组织神经网络分类结果:

L区:西山小学, 广场小学, 实验小学, 南汇小学;

O区:塘下小学, 曲溪小学, 源口村小学, 东方小学;

W区:茶山小学, 新川小学, 光明小学, 桥头小学。

仿真时间:25分30秒

结果显示, 迭代自组织神经网络给出了更为准确的分区结果, 但耗时较长。说明引入迭代算法在提高模式分类准确度的同时, 将很大程度的降低程序运行速度。

3 迭代自组织神经网络算法应用分析

根据2, 迭代自组织神经网络算法适用于已知部分输入模式类别情况下的模式分类。故可利用该算法识别未知模式的类别, 进而应用于电气工程、环境工程等领域。下面将以电气工程为例, 分析迭代自组织神经网络算法在变压器故障检测中应用的可能性。

电力变压器是电网中的主要元件之一, 其安全运行是电网可靠运作的必要条件。变压器油溶解气体的色谱分析是变压器故障诊断的一种重要方法[2]。为提高故障诊断的准确度, 可尝试引入迭代自组织神经网络算法。

以油中5中特征气体 (H2、CH4、C2H2、C2H4、C2H6) 的体积含量作为特征变量。根据长期运行经验, 可得到某型号变压器在正常运行及故障运行时的检测数据, 作为已知模式。同时, 以实时监测数据作为未知模式。采用迭代自组织神经网络法可进行检测数据的模式分类, 得到实时监测数据所属类别, 进而得到变压器故障检测结果。

同理, 迭代自组织神经网络算法也可试用于水质检测、人脸识别等方面。

4 总结

迭代自组织神经网络算法可以在分类过程中进行自我校准, 适用于已知部分输入模式类别情况下的模式分类。改进算法有效提高了模式分类的准确度, 具有应用于电气工程、环境工程等领域的可能性。但本文仅局限于算法的提出和算法应用思路的分析, 具体工程应用及算法速度问题的解决有待于后继研究来实现。

摘要：本文在自组织竞争网络的基础上, 结合迭代算法, 提出了一种改进的神经网络算法, 即迭代自组织神经网络算法。改进算法可有效提高模式分类的准确度, 但会很大程度降低程序的运行速度。本文最后, 将简要分析该改进算法在电力、环境工程等领域推广与应用的可能性。

关键词：自组织竞争网络,迭代算法,模式分类

参考文献

[1]汪海波, 张海臣, 段雪丽.基于MATLAB的自组织竞争神经网络聚类研究[J].邢台技术学院学报, 2005 (1) :46-47.

自组织算法论文篇5

关键词：自组织网络,位置信息,路由算法

0 引言

与传统无线单跳通信网络不同,无线自组织网络[1](W-ireless Ad hoc Network)是一种多跳网络(Multi-Hop)。无线单跳蜂窝通信网络需要固定的网络基础设施,例如基站的支持才能进行数据转发,而无线自组织网络却不需要任何基础设施的支持,其中的节点既可作为终端进行数据收发,也可作为路由器实行数据转发,并通过多跳转发实现数据传输。正是由于无线自组织网络引入的一些新特性,而使得传统的路由算法在变化的形势下已不再适用,因此近年来,无线自组织网络路由算法的相关研究已成为探索的重点和热点之一。

利用位置信息转发数据的路由算法,其最初源起于上世纪80年代由美国先进研究计划署所提出的无线自组织网络—分组无线网络PRNet(Packet Radio Networks)。近年来,随着小型化、低成本和低能耗的全球定位系统(GPS:Global Positioning System)的广泛应用,以及自组织网络中自配置定位算法的有效发展,基于位置信息的路由算法已然成为自组织网络路由算法的一个主要研究方向。而基于位置信息的路由算法又因其可为网络提供一个具有高度可扩展性的高效解决方案,在当前的移动自组网(MANETs),车载自组网(VANETs),无线混合网(WMNs),以及传感器网络(WSNs)中均获得了广泛的应用。

与基于拓扑信息的路由算法相比,基于位置信息的路由算法是利用节点的真实位置信息或者虚拟相对位置信息来逐跳转发直至最终目的节点。现今,已有的基于位置信息的路由算法多属于单播路由算法,即由一个源节点发送至一个目的节点。本文对现有单播路由算法给出了简要介绍,并对其两种主要操作模式进行了阐述,同时讨论了每种模式所采用转发策略的最新进展。另外,除单播路由外,也总结了其它方面的最新研究成果,如基于位置信息的多播路由(Multicast),地理区域广播路由(Geo Cast)算法[2]。

本文主要从以下几部分展开。第一部分讨论了基于位置信息路由算法的研究背景,第二部分介绍了基于位置信息的单播路由算法,第三部分简述了多播算法的发展,最后对基于位置信息的路由算法进行了总结和展望。

1 基于位置信息路由算法背景

由于自组织网络中没有固定基础设施,每个节点仅在通讯范围内与其它节点通讯,因此网络中任意节点对间的通讯只能借助多个节点的转发,即多跳路由。根据路由算法利用的信息可将其分为两类:基于位置信息的路由算法和基于拓扑信息的路由算法。下面逐一介绍。

基于拓扑信息的路由算法主要是利用网络拓扑的链路连通信息来建立和维护源节点到目的节点的完整路径。而此类算法还可以在实现方式上进一步划分为主动式路由算法(表驱动路由算法)、被动式路由算法(按需路由算法)以及混合式路由。最早的基于位置信息路由算法,就是在利用已有的基于拓扑信息的路由算法基础上,再综合目的节点位置信息来减小路由开销,如LAR及DREAM算法。

基于位置信息的路由算法则主要根据节点的位置信息进行转发。与初期仅利用目的节点位置信息的方式有所不同,现有的基于位置信息的路由算法既需要目的节点位置信息,也需要节点自身及一跳邻居节点位置信息,而在此基础上,中间节点还可以自主选择下一跳转发节点。因此,节点不需要维护到目的节点的路径,也不需要发送控制包来更新路径状态。由于网络拓扑变化对于节点选择下一跳的影响仅限于当前节点的一跳范围内,所以网络拓扑变化对基于位置信息的路由算法的影响远比对基于拓扑信息路由算法的影响要小。而且,基于位置信息的路由算法都会具有较高的局域性,采用此类路由算法的网络则将具有较好的扩展性。

2 基于位置信息的单播路由算法

单播路由算法可构造由唯一源节点到唯一目的节点的一条连通路径。当源节点需要向目的节点发送数据时,从一跳邻居节点中采用某种算法选择一个节点作为下一跳。中间节点将重复执行此算法,直至到达目的节点。贪婪转发[3]就是一种高效简单的算法,正为目前众多基于位置信息的路由算法所采用。然而,贪婪转发只有在网络密度足够高的情况下才能成功转发数据包,而在实际网络部署中,网络局部存在不连通区域则是在所难免的。当到达不连通区域时,贪婪转发会因局部最小化问题(Local minimum)而发生失效,导致贪婪转发失效的不连通区域即称作通讯空洞(Communication void)。贪婪转发算法在遇到空洞时需要由其它算法,如空洞处理算法,来接替转发任务,进而完成路由任务。因此,一个完整的路由协议将同时包含贪婪转发算法和空洞处理算法。下面分别对这两种算法进行介绍。

2.1 贪婪转发算法

贪婪转发算法仅利用当前节点的邻居位置信息以及目的节点的位置信息并按照某种标准选择局部最优的下一跳节点,所有中间节点重复采用相同转发算法直至到达目的节点。目前已提出了多种贪婪转发算法,其主要区别就在于这些算法都是按何种标准来选择下一跳节点,以实现最终靠近目的节点。

早期标准是按照几何计算结果来选择下一跳。选择示意如图1所示,当S代表当前节点,D代表目地节点时,选择标准不同,选择得到的下一跳节点也会不同,对贪婪转发的各种形式综合并总结如下。

(1)随机转发(Random selection)

在随机转发中,当前节点可从距离目的节点更近的邻居节点中随机选取一个作为下一跳节点。如图1所示,在节点S的邻居节点中A、B、C、E、F节点距离目的节点都比S更近,因此S可从其中随机选择一个节点作为下一跳。

(2)最近方向转发(Closest-direction-based)

在最近方向转发中,当前节点在距离目的节点更近的邻居节点中,可根据当前节点与目的节点的连线方向,来选择与此方向最近的节点作为下一跳节点。如图1所示,按其含义,节点S将选择节点C作为下一跳节点转发。

(3)MFR转发(Most Forward Within Radius)

在MFR转发中,将邻居节点在当前节点与目的节点的连线上的正交投影定义为节点前进值。当前节点可在邻居中选择具有最大正向前进值的节点作为下一跳节点。如图1中,A节点在SD连线上的投影具有最大值,因此A节点将作为下一跳节点。

(4)NFP转发(Nearest with Forward Progress)

在NFP转发中,具有最小正向前进值的邻居节点将作为下一跳节点。如图1中,节点G在节点S的邻居节点中具有最小正向前进值。因此,节点G将成为下一跳节点。

(5)MAR(Most Advance Within Radius)

在MAR转发中,当前节点在距离目的节点更近的邻居节点中选择距离目的节点最近的邻居作为下一跳节点。在图1中,节点E距离目的节点D最近,因此当前节点S将选择E作为下一跳节点。

(6)NC(Nearest Closer)

在NC转发中,当前节点在距离目的节点更近的邻居节点中选择距离自身最近的节点作为下一跳节点。如图1中,由于节点B比当前节点距离目的节点更近,且与节点S间距离最小,因此节点B将作为下一跳节点。

2.2 空洞处理算法

贪婪转发失效后,空洞处理算法将继续转发数据包,直至贪婪转发算法能够恢复运行。贪婪转发失效示意图如图2所示。

在图2中,由于当前节点S没有比其距离目的节点更近的邻居节点,贪婪转发无法选择下一跳节点,因此仅使用贪婪转发则无法成功将数据包发送到目的节点D。然而实际上,从节点S至目的节点D存在一条拓扑连通路径S-A-B-C-E-D。

下面将介绍五种采用不同策略的空洞处理算法。这五种算法分别是,基于拓扑的空洞处理算法,基于平面图的空洞处理算法,基于几何特性的空洞处理算法,基于链路反转的空洞处理算法,混合式的空洞处理算法。

(1)基于拓扑的空洞处理算法

该算法利用拓扑信息来处理空洞问题。严格来说,采用这一类空洞处理算法的路由协议并不是纯粹的基于位置信息的路由协议。

基于拓扑的空洞处理算法是利用泛洪来使数据包从贪婪转发失效的节点发送到目的节点。全网泛洪可以在全网范围内找到拓扑连通的路径,但开销较高。One-hop flooding[4]及Cartesian Routing[5]将泛洪限制在包含目的节点的某个方向内。在On-demand Geographic Forwarding(OGF)[6]及Geographic Routing Algorithm(GRA)[7]中,为减小泛洪开销,并不查找直到目的节点的路径,而是查询到达某一一个贪婪转发能够恢复的节点的路径。

(2)基于平面图的空洞处理算法

该算法利用平面图的特性来发送数据包,由于网络平面图算法的局部性,这类算法能以较低的开销处理贪婪转发失效。在图论中,平面图则定义为一种能够嵌入在平面的非自交图。目前的算法主要利用RNG和GG方式对网络进行平面化处理。在网络平面化处理后,再根据转发策略从空洞边缘进行转发。该类算法的典型代表主要有Original face routing[8]、the face-2 algorithm[9]、GOAFR+[10]以及Greedy Perimeter Stateless Routing(GPSR)[11]。

(3)基于几何特性的空洞处理算法

该算法主要利用网络拓扑的几何特性来发送数据包。作为此类路由算法的代表,BOUDNHOLE算法[12]通过使用TENT规则来判定某节点能否使贪婪转发成功实现数据发送,如果不能,就将其定义为Stuck节点,并寻找同一空洞的其它Stuck节点;在获取同一空洞的所有Stuck节点后,将数据包沿Stuck节点发送,直至贪婪转发恢复。同类算法中,其它的还有Coordinate Depth Forwarding(CDF)[13],Void Resolution-Forwarding(VRF)[14]。

(4)基于链路反转的空洞处理算法

在一些特定网络,如传感器网络中,网络中的节点通常需要向几个固定的目的节点发送数据。而在该类网络节点中若采用相同的贪婪转发,将不会产生路由环路,因此,可在将链路赋值后,再将此类网络抽象为DAG(Directed A-cyclic Graph)。这一类的算法主要有Partial-partition Avoiding Geographic Routing-Mobile(PAGER-M)[15]。

(5)混合式空洞处理算法

该算法可同时利用两种以上空洞处理策略来转发数据。通常在以下两种情况中,即需要采用此类算法,一种情况是当一类空洞处理算法无法达到所需的性能时,另一种则是只采用一种空洞处理算法无法处理网络中存在的所有类型的空洞。这种类型的算法主要有BOUNDHOLE与restricted flooding的混合算法[12],PSR与passive participation的混合算法[6],active exploration与passive participation混合算法[16]。

3 基于位置信息的多播路由算法

本节主要介绍基于位置信息的多播路由以及地理区域广播(GeoCast)算法。这两类算法产生时间相对较近,下面主要介绍其面临的问题及解决方案。

3.1 基于位置信息的多播路由

多播路由是将数据包从单个源节点发送到多个目的节点的路由算法。可通过两种方式达到此目标:一种是利用广播算法在全网进行泛洪,另一种是利用单播算法向多目标发送数据。由于采用这两种方法可能导致路径出现相同链路,所以并不高效。现有的多播路由算法正追求实现冗余链路的避免,借此来减小网络资源消耗。

基于拓扑信息的多播路由算法可分为基于树(Treebased)的多播算法和基于网(Mesh-based)的多播算法。这些多播算法的实现方式通常是由一个派生自源节点的多播树来构造多播路径,而且这两种算法都需要维护网络拓扑状态信息,并通过周期性的泛洪来更新网络状态,因而其网络开销均较大。

基于位置信息的多播算法是通过利用位置信息获取网络结构及预测节点移动等来减小开销。利用位置信息的多播算法通常需要解决两个问题。一个问题是在何时产生多个数据包副本。由于要向多个目的节点发送数据包,就决定了要在中间节点产生多个相同的数据包。而在不同中间节点产生这多个数据包副本也会相应带来不同的开销,因此,如何决定复制数据包的节点就成为首要解决的问题。另一个问题是如何调整空洞处理算法以更好地适应多目的节点的存在。由于目的节点有多个,一些空洞边界节点对于某个目的节点可能会导致贪婪转发失效,而对另外一些目的节点却没有影响。因而需要有效解决这一方面问题。PositionBased Multicast Routing(PBM)[17]是基于位置信息的多播路由算法的典型代表,主要在GPSR的基础上改进来适应多目的节点。Geographic Multicast Routing(GMR)[18]则在PBM基础上更进一步地减小了开销。

3.2 地理区域广播路由GeoCast

本质上,GeoCast也是一种多播路由算法,但与3.1节所介绍的基于位置信息的多播路由算法不同,其目的节点并非确定节点而是通过地理区域来定义的[17]。在GeoCast中,一个源节点发送数据包至目标区域中的所有节点。但由于源节点并不需要将目标区域的所有节点位置信息均放入数据包内,因而目标区域的节点数目并不影响GeoCast的开销。很显然,全网泛洪及多播路由都可以用来构造GeoCast算法。但这样得到的算法却由于没有利用目标节点处地理区域定义的特性,其算法效率实际上并不高。

GeoCast通常由两部分组成。一部分是将数据从源节点转发至目标区域的任一节点。另一部分则是将数据从区域中的节点转发至整个区域的其它节点。

根据第一部分采用的转发策略,可将现有的GeoCast算法分为两类:基于泛洪的和基于单播的GeoCast。基于泛洪的GeoCast主要有Location-Based Multicast algorithm(LBM)[19]、GeoGRID[20]。这类方法是利用限制泛洪来实现数据从源节点至目标区域的转发。尽管对泛洪采取了限制措施,但接入竞争以及冲突问题仍然存在。基于单播的GeoCast,主要有GeoTORA[21],Geographic Forwarding Perimeter Geocast(GFPG)[22]。这一类算法是通过路由控制包来构造自源节点到目标区域的一条或多条路径,而后再经过所构造路径来发送数据。基于单播的GeoCast的优势在于其开销较低,不足之处却是其路由控制包将会造成的延时。

4 结束语

自组织算法论文篇6

为了解决远程教育不可避免地产生的“孤独”学习者的问题, 把具有相同学习兴趣的学习者组织到同一个学习社区中, 以帮助他们进行协作式学习。社区对应于英文单词“community”, 社区是指生活在一定地理区域内, 具有共同意识和共同利益的社会群体, 具有共同兴趣的一群人。当社区所属的物理空间变成了网络空间, 便成为所谓的虚拟社区。虚拟社区由具有共同兴趣的参与者组成, 参与者通过网络进行互动交流, 寻找到一群彼此兴趣相投的伙伴, 并能够共同讨论一定程度和意义的主题。

目前国内外对教育虚拟社区的研究主要集中在基础研究, 探索虚拟社区的基本原理, 包括虚拟社区的概念、定义、原理和模式, 如Hope N.Tillman提出了教育虚拟社区的定义、特征、类型、社区服务、创建策略和交往发生等问题[1]; Amy Jokim博士 (2000) 提出建立社区的九大策略[2]。而对虚拟社区技术发展研究以支撑虚拟社区的成长, 包括在虚拟社区使用的工具及其技术潜力, 探讨如何构建虚拟社区方面的研究较少。本文讨论的则是对于网络上的学习者如何构建兴趣型的学习社区, 让学习者在社区内进行协同学习。建立兴趣型的学习社区的基本思想是首先根据学习者的相关数据计算学习者的兴趣向量, 即根据兴趣的隐性表示获取对应的显式表示, 然后根据学习者的兴趣向量计算两两学习者之间的兴趣匹配度, 并计算学习者的匹配浓度, 最后按照一定的方法建立学习社区。本文通过对学习社区特性的具体分析, 提出了基于本体的向量空间模型, 并根据兴趣相似度的思想, 提出了一种基于学习者兴趣相似匹配度和学习者兴趣相似匹配浓度的学习社区的自组织算法。最后的算例分析表明该模型算法具有较高的效率和良好的扩展性。

向量空间模型在当今文本处理、文本挖掘领域占有重要的地位。向量空间模型可以用在文档空间的相似比较也可以用在段落空间的比较以及句与句间的比较[3]。许多的搜索引擎都曾使用这种模型来分类网络文档。传统的向量空间模型有术语间语义相关性被忽略的不足, 许多学者将概念间的语义相关性考虑进来, 例如潜在语义索引法[4,5], 语言概念化法, 基于辞典或分类[6]等方法, 但是这些方法中考虑的概念关系简单而稀少。我们采用语义网络技术为信息提取提供共享的知识背景, 也就是本体, 在本体的支持下, 兴趣描述信息项中语义相关的术语不再被孤立地看成关键词, 而是彼此间有了一定的语义联系, 通过有限本体图计算概念间的语义相关度, 克服了传统的向量空间模型中术语间语义相关性被忽略的缺点, 这种考虑了术语间潜在语义联系的方法能够提高兴趣相似性比较的精确程度。基于本体的信息提取系统, 其向量空间的维数依赖于本体中实体的数量。随着本体概念的增加, 向量空间的高维数带来计算上的难度与复杂性。现有的解决方法包括随机映射 (RP) [7,8], 隐含语义分析 (LSA) [9,10], 概念索引 (CI) 降维[11]等等。本文将概念索引降维法改进运用于兴趣特征降维, 对兴趣特征矩阵进行合理的降维处理, 然后进行匹配计算, 大大降低运算量, 提高算法效率。下面将详细介绍相关概念和算法。

2 基于本体的向量空间模型

2.1 定义

本体最早是一个哲学上的概念, 近年来, 本体被人工智能领域的学者借用, 来表示更高层次的概念, 尽管不存在本体的精确定义, 但是从内涵上来看, 不同研究者对于本体的认识是统一的, 都把本体看成概念化的语义, 为人、机器间进行交流提供语义基础, 即本体提供一种明确定义的共享知识, 目标是让机器自动处理、整合网络信息。

网络上获得的信息 (网络文档、段落、句子、自然语言查询语句等) 组成信息对象集合D={di|1≤i≤M}, M为信息对象的总数。根据向量空间模型, 每条信息di都可以用一个特征向量v (s) =[s1, s2, …, sN]来表示。si与本体中的概念ci对应, 表示某个信息对象中术语ci的权重。所有的信息对象表示成的特征向量就构成了向量空间V={v1 (s) , v2 (s) , …, vM (s) }。向量空间的维数等于本体构成的知识论域空间的维数N.

2.2 有限本体图

本体表示的是结构化的知识, 具有自然的层次结构, 从图论的角度, 本体可以表示成一张图G={V, Edg}, 节点集合V对应于本体中实体的集合{c1, c2, …, cN}, 并且节点与实体存在着一对一的映射关系:vi∈V↔ci, i=1, 2, …, N, 因此可以使用V (ci) 表示图的节点vi.边edgi= (u, v) 连接节点u∈V和节点v∈V, 边集合Edg对应于本体中的关系集合R:edg↔ri∈Ri, i=1, 2, …, N, 因此可以用edg (V (ci) , V (cj) ) 表示图中的边。将上面的图形定义为本体图。

通过对本体图进行约束, 例如对关系的约束, 获得有限本体图。通过适当的约束, 使我们能够抛开次要问题, 集中解决主要问题。基于本体的向量空间模型中的术语对应于本体中的概念, 本体中的概念的语义相关性度量, 通过基于有限本体图的语义距离计算获得。本体可以表示成有限本体图, 有限本体图是有向无环图, 其拓扑有序, 表现出层次结构。所以按照层次遍历的“Breadth-First”算法 (类似于树图中的广度优先的遍历方法) 扫描有限本体图, 建立本体中的概念的索引表。概念索引表层次关系明显, 高层次的概念索引号在低层次的概念索引号的前面, 并且相连的兄弟概念排列在一起, 利用这样的特征能够简化语义距离的计算方法, 不需多次扫描概念图, 便于基于本体的自然语言文本的处理。

2.3 语义距离和语义相关度

语义距离是一种度量对象 (概念、词汇和句子) 间语义相似程度的概念, 其数值表示形式通常是[0, ∞]间的实数。语义距离的定义要根据系统模型来确定, 尚不存在具有普适性的语义距离的定义, 每个人都可以根据实际应用的需要定义语义距离, 由此出现了很多的语义距离定义方法, 如虚拟距离法、层次距离法等。语义距离与语义相关度成反比关系, 例如两个概念间的语义距离越大, 它们的语义相关度越低, 反之, 距离越小, 相关度越大。语义相关度是一个强主观性的概念, 与具体的应用相关, 因此也很难获得一个统一的定义。考虑到本体可以表示成有限本体图, 我们将基于图形最短路径法计算语义距离。

有限本体图上的节点与本体中的类/概念一一对应, 对于本体中概念的集合Oc={c1, c2, …, cn}, 语义距离函数d:Oc×Oc→R是一个二元映射, 并且满足:①非负性:d (cx, cy) ≥0;②同一性:d (cx, cy) =0当且仅当cx≡cy;③对称性:d (cx, cy) =d (cy, cx) ;④三角不等性:d (cx, cy) ≤d (cx, cz) +d (cz, cy) 。所以语义距离空间构成度量空间, 称d是Oc上的度量函数记为 (Oc, d) 。通过语义距离矩阵描述该度量空间。

定义1 对于有限本体空间图上的任意节点V (cx) 到其自身的语义距离为0, d (V (cx) , V (cx) ) =0。

定义2 对于有限本体图上的任意节点V (cx) 和节点V (cy) , 如果存在通路, 那么定义语义距离为两节点间的最短路径长度d (V (cx) , V (cy) ) =min (pathLengthi (V (cx) , V (cy) ) ) 。

定义3 对于有限本体图上的任意节点V (cx) 和节点V (cy) , 存在直接的连接 (即∃edg (V (cx) , V (cy) ) ) , 如果两者间的关系是父子关系 (SubClassOf) , 那么定义语义距离为d (V (cx) , V (cy) ) =1;如果两者间的关系是对象属性关系 (ObjectProperty) , 那么定义语义距离为d (V (cx) , V (cy) ) =2。

根据前面基于图形的语义距离的计算方法, 将本体概念间的语义距离用矩阵表示, 获得语义距离矩阵:

$D i s Μ (Ο_{c}) = [\begin{matrix} 0 & d (c_{1}, c_{2}) & \dots & d (c_{1}, c_{Ν}) \\ d (c_{2}, c_{1}) & 0 & \dots & d (c_{2}, c_{Ν}) \\ \dots \\ d (c_{Ν}, c_{1}) & d (c_{Ν}, c_{2}) & \dots & 0 \end{matrix}] (1)$

语义距离矩阵的维数N对应于本体中的类概念数, 元素d (ci, cj) 表示术语ci到术语cj的语义距离。

语义距离与语义相关程度间存在着逆关系, 即语义距离越大, 相关程度越小。给出由语义距离计算语义相关度的公式r (ci, cj) =e-α·d (ci, cj) , 其中d (ci, cj) 对应于式 (1) 中概念ci和cj间的语义距离值, α表示陡度系数。此公式满足语义距离与语义相关程度间的对应关系:①两个对象语义距离为0时, 其语义相关度为1;②两个对象语义距离为无穷大时, 其语义相关度为0;③两个对象语义距离越大, 其语义相关度越小 (单调下降) 。

根据语义相关度的计算公式, 可以将语义距离矩阵DisM (Oc) 转化成语义相关矩阵R (Oc) 。

$R (Ο_{c}) = [\begin{matrix} 1 & r (c_{1}, c_{2}) & \dots & r (c_{1}, c_{Ν}) \\ r (c_{2}, c_{1}) & 1 & \dots & r (c_{2}, c_{Ν}) \\ \dots \\ r (c_{Ν}, c_{1}) & r (c_{Ν}, c_{2}) & \dots & 1 \end{matrix}] (2)$

3 基于本体用户兴趣特征向量的量化系统设计

本文提出基于本体的向量空间模型计算学习者的兴趣特征向量, 设计了基于本体的用户兴趣特征向量量化系统, 它是一种考虑了术语间语义相关性的计算模型, 根据学习者描述的兴趣信息, 以学习者共同的知识背景——本体为基础, 经过预处理和特征量化两个功能模块处理, 将文本信息表示成统一尺度的特征向量后, 以便计算向量间的相关度, 例如采用余弦法, 来进行信息的匹配与提取。

3.1 预处理模块

预处理模块主要功能是从描述信息中分辨出一个句子里面的词, 将属于知识论域中的术语提取出来, 重构成本体实例。分散的学习者用户发布的兴趣信息描述中潜在地包含了用户个人的知识背景, 以及对知识的理解程度, 因此我们可以从描述的信息中提取出分散用户的局部的知识。这些局部的知识片断可以看成是本体的实例, 本体刻画了领域知识, 可以表示成本体图, 那么作为本体实例的用户的局部知识, 也可以采用局部概念图来表示。

定义4 根据基于本体的向量空间模型, 用户特征局部向量v (s) =[s1, s2, …, sN], si与本体中的概念ci对应,

$s_{i} = {\begin{cases} e^{- α D i s (e_{i}, r o o t)} \\ 0 \end{cases} (3)$

如果对应的概念ci出现在概念图中, 则与之对应的si为e-αDis (ei, root) ;反之, si为0值。其中Dis (ei, root) 表示了局部概念图中概念ei∈Oc到root的语义距离, si∈[0, 1], 其计算方法也是基于图形的最短路径的计算方法;α表示陡度估量, 因为e-7≈0, 在模糊建模中通常选择其值为-7/MAX (Dis) 。

重构本体实例的具体步骤:①以本体的概念作为向量空间的术语项, 对信息项内容中包含的术语进行提取。如果一个提取的概念在本体中找不到对应项, 但却是本体中某些复合词的一部分, 那么将所有相关的复合词都添加进来。②将提取的概念组成局部概念图, 局部概念图表示的是用户的知识片断, 作为本体的实例, 它具有与有限本体图一致的特征, 即为有向无环图。重构本体实例依从的规则为:以整条信息项所涵盖的知识集合为根节点;提取的概念间的相对关系与本体图中的相对关系保持一致, 即上下位关系不变, 旁支关系不变。我们假设, 社区的学习者用户具有共同的领域知识, 用户虽然表达用语具有随意性, 但是用语间潜在的结构关系应该符合领域知识内部概念间的相对关系。将知识片断提取出来, 并对其进行重构, 将本体实例保存到知识库中。预处理的结果成为系统核心模块——量化处理模块的输入, 然后获得表示用户局部知识的特征向量。

3.2 信息的度量统一

从局部知识图 (本体实例图) 可知因为学习者用户用语的随意性, 以及主观认定性, 导致局部知识的术语关系是依赖用户的相对关系。由此获得的特征向量是相对于个体局部知识结构的量化。另一方面, 同一领域的概念间并不是孤立的, 相互间具有一定的语义相关性, 用户表明的本体实例中使用的概念往往隐含地包含了与之相连的概念的信息。为了能够统一地度量分散的特征向量, 需要将局部知识转化到统一度量的空间中。本文采用模糊推理, 基于概念间的相关性, 将局部特征向量转化为统一度量尺度下的特征向量, 以便后续的匹配比较。计算公式为:

$V (s) ˚ R (o) \Rightarrow \bar{V} (s) (4)$

V (s) =[s1, s2, …, sN]表示局部知识的特征向量, 根据式 (3) 计算, 模糊关系矩阵R (o) 已通过前面式 (2) 计算获得。R (o) 中每个元素rij反映了术语间的相近程度。这样那些在兴趣描述中没有显式地出现过的术语的语义关系也将被考虑。公式中的“。”表示模糊关系中的内积, 代表MAX-MIN操作。经模糊推理将分散的特征向量转化为统一度量空间中的特征向量,

$s_{i} = \max (\min (s_{1}, r (1, i)), \min (s_{2}, r (2, i)), \dots, \min (s_{Ν}, r (Ν, i))) (5)$

上式计算获得的si是统一度量空间中特征向量 $\bar{V}$ (s) 的元素。经过上面的计算, 来自学习者用户的个人兴趣描述信息都被转化成考虑语义后统一度量的特征向量。对于具有统一尺度的特征向量, 可以进行比较匹配。匹配功能可以通过对语义特征向量进行计算厢似度实现。参考向量空间模型中, 目前向量相似性函数的计算方法包括: 内积法 (Cosine函数) 、最近邻法 (Max) 、Minkowski距离、Euclidean距离等。其中最直观有效的方法为内积法。

将用户1的特征向量表示为空间向量v (d1) ={x11, x12, …, x1n}, 将用户2的特征向量表示为空间向量v (d2) ={x21, x22, …, x2n}。那么通过计算两向量v (d1) 和v (d2) 的夹角 (内积) 来度量向量间的接近程度。内积越大, 两向量间的夹角越小。相似度量的计算公式如下: $s i m (d_{1}, d_{2}) = \frac{v (d_{1}) \cdot v (d_{2})}{| v (d_{1}) | | v (d_{2}) |}$ 。

本文基于内积法 (Cosine) , 计算特征向量的相似性。代表用户i的兴趣特征向量vi=[si1, si2, …, siN], 代表用户j的兴趣特征向量vj=[sj1, sj2, …, sjN], 根据Cosine法计算向量间的匹配度为:

$Μ a t c h D e g r e e (i, j) = \frac{| v_{i} \land v_{j} |}{| v_{i} | \cdot | v_{j} |} (6)$

通过计算两个向量vi和vj的内积来度量向量间的接近程度, 内积越大, 两个向量间的夹角越小, 两个兴趣越接近。

3.3 概念索引 (CI) 降维

基于本体的信息提取系统, 采用向量空间模型来表达兴趣信息的文本特征, 表现出巨大的维数, 从而导致处理过程计算复杂, 为此, 需要先对特征矩阵进行合理的降维处理。概念索引 (CI) 是一种有效的降维方法:v (s) =[s1, s2, …, sN]表示学习者用户兴趣信息的局部知识特征向量, 设W为M×N矩阵, 其中, M为用户的数目, N为本体构成的知识论域空间的维数, v1 (s) =[s11, s12, …, s1N], W=[v1 (s) , v2 (s) , …, vM (s) ]′, W的第i行为第i个用户的兴趣向量空间表示Wi, 再设r为要降至的维数。概念索引先采用某种简单的聚类算法 (k-means或层次算法等) 对W作r路聚类, 将特征向量集分成r个互不相交的子集S1, S2, …, Sr, 然后, 对每个集合Si分别计算质心点向量Ci, 并将它们规格化为单位向量C′i, 将每一个单位质心向量C′i作为降维空间的一个坐标轴, 形成一个r维子空间, 每个用户的r维向量表示可通过将其映射到这个r维子空间得到, 因此, 降维后的兴趣向量空间W′可通过式 (7) 的矩阵运算得到:

$W^{'}_{m \times r} = W_{m \times n} \times C_{n \times r} (7)$

其中, Cn×r= (C′1, C′2, …, C′r) 。 W′m×r为降维后的用户兴趣局部特征向量构成的矩阵, 第i行表示第i个用户的兴趣局部特征向量, 局部特征向量由原来的N维降到r维。可以大大简化后面的计算量。

4 学习社区的自组织算法

社区应该是一组具有相同或相似兴趣学习者组成的团体, 因此社区的建立应该尽可能的将兴趣相似度大的学习者放在同一个社区中。在此思想的指导下, 我们提出如下的社区建立流程。

第一步: 兴趣特征向量降维后, 根据式 (6) 计算两两学习者之间的兴趣匹配度。

第二步: 设定阈值T1, 计算每个学习者的匹配浓度 (由与该学习者兴趣匹配度较高的学习者数目的多少来决定浓度的高低) 。假设某高校网络学习者为m个, 学习者i的浓度θi计算公式为: $θ_{i} = \frac{\sum_{i = 1}^{m} a_{i j}}{m}$ , 其中,

$a_{i j} = {\begin{cases} 1, Μ a t c h D e g r e e (i, j) \geq Τ_{1} \\ 0, 否则 \end{cases}, Τ_{1}$

为预先假定的阈值。

第三步: 选出匹配浓度最高的学习者, 作为社区中心学习者来建立社区。预先设定一个阈值T2, 与中心学习者的兴趣匹配度高于阈值的学习者进入该社区。

第四步: 对剩下的学习者按照第一步至第三步的顺序, 重新计算, 直到学习者的最高浓度低于一个阈值T0为止。对于浓度低于T0的学习者, 计算他与各社区中心学习者的相似度, 进入最相近的社区学习。

5 实例分析

本文提出了一种基于本体兴趣向量空间模型的学习社区构建算法, 将具有相似爱好的学习者自动有效地组织成一个个的学习者社区, 帮助其共享资源, 进行协行式学习。实验结果证明, 该算法具有较高的分组效率和良好的可扩展性。

5.1 算法实验步骤描述

①采用语义距离的计算方法, 获得本体中概念间的语义距离, 可以使用语义矩阵表示。

基于专家支持建立程序员研发的领域本体, 为社区网络中分布的学习者用户提供共享的知识背景。考虑了概念层次树的深度、密度的语义距离, 认为路径长度相同的两个结点, 如果位于概念层次的越底层, 其语义距离较小, 如果位于概念层次树中高密度区域, 其语义距离应小于位于低密度区域。故概念层次离根部越近距离权值越大。使用对领域知识进行编码, 生成的本体概念关系图如下所示。

从本体图上可以清晰地看出, 知识可以分等级地表示, 本体中的概念相互间存在着一定的语义相关性。本体中的概念以数字标号的形式表示, 有限本体图是有向无环图, 按照层次遍历的“Breadth-First”算法进行解析, 与本体图2对应的概念索引表为:

{ 0 Computer Programmer-Related-Technology, |1 NETWORK, 2 software, |3 Network Protocol, 4 WEB Designing, 5 Operation-system, 6 Programming-language, 7 database, |8 SNMP, 9 ATM, 10 DSN, 11 APR/RAPR, 12 UDP, 13 TCP/IP, 14 HTML, 15 PHP, 16 JSP, 17 Ruby, 18 Ajax, 19 Java Script, 20 UI, 21 Embedded-operation-system, 22 Macintosh-operation-system, 23 windows, 24 DOS, 25 Developer, 26 .NET, 27 Assembly-language, 28 Oracle, 29 DB2, 30 MS-SQL, 31 MySQL, |32 WinCE, 33 VxWorks, 34 ucLinux, 35 Linux, 36 C, 37 MFC, 38 VB, 39 C++, 40 JAVA, 41 Delphi, 42 ASP.NET, 43 C#, 44 VB.NET, 45 VC.NET}。

索引列表中的竖直线用来示意有限本体图中的概念的层次划分。这里, 概念对应的标号并非随机指定的, 而是与概念所在的层次排列密切相关, 图中的标号对应于概念索引的序列号。考虑到本体可以表示成有限本体图, 那么我们将基于图形最短路径法计算语义距离。根据语义距离矩阵的定义, 可以获得如图3所示的46×46语义距离矩阵。可以看出, 语义距离矩阵是个对称矩阵, 灰度度量了实体间语义距离的大小。X、Y轴的标号对应于本体概念索引表中的标号。

②学生用户兴趣描述信息的局部知识数值化, 并经过模糊推理转化成统一度量下的特征向量。

假如学生用户甲描述自己的兴趣信息项为“Software Engineer, experiences in C language, .NET such as VC.NET, C#, interested in WEB designing with Ruby”, 依据前面3.1的方法从中提取出的知识空间内的术语为“Software, C, .NET, VC.NET, C#, WEB designing, Ruby”, 根据术语在知识空间内的相对结构, 上面信息中提取的知识片断可以表示成概念图4。用户乙描述的兴趣信息项提取出的知识空间内术语为 “Operation System, EmbeddedOperationSystem, Linux, Database, MySQL”, 同样的方法可以解析成本体实例, 转化成概念图5。

甲乙学习者用户兴趣描述信息的局部知识数值化为用户特征局部向量如下:

v1 (s) :[0, 0, e-α, 0, e-α, 0, …, e-2α, 0, …, e-2α, 0, 0, 0, e-3α, 0, …]

v2 (s) :[0, 0, 0, 0, 0, e-α, 0, e-α, 0, …, e-2α, 0, …e-2α, 0, 0, 0, e-3α, 0, …]

特征向量中的元素对应于概念索引表中的项。现假设有M=12个学习者希望能够通过自己声明的兴趣, 为其发现适合自己的学习社区。同样的方法, 从学习者用户的兴趣信息描述中提取出兴趣特征术语, 并对其进行重构, 由此获得的其他学习者用户兴趣描述信息项的局部知识向量为:

v3 (s) :[0, 0, e-α, 0, e-α, 0, …, e-2α, 0, …, e-2α, 0, …, e-2α, 0, 0, 0, 0, 0]

v4 (s) :[0, 0, 0, e-α, e-α, 0, …, e-2α, 0, …, e-3α, 0, …, 0]

v5 (s) :[0, 0, e-α, 0, …, 0, e-α, e-α, 0, …, e-2α, e-2α, 0, …, 0]

……

③经过模糊推理, 学习者用户的局部知识被转化成统一度量下的特征向量。然后按照用户设置的维数采用CI法计算降维的兴趣特征向量。

假设用户设置的维数r=3, M=12个学生的兴趣局部知识向量可以表示成M×N矩阵 (其中, M为用户的数目, M=12, N为本体构成的知识论域空间的维数, N=46)

$W^{'}_{12 \times 3} = W_{12 \times 46} \times C_{46 \times 3} (7)$

其中, C46×3= (C′1, C′2, C′3) 。W′12×3为降维后的用户兴趣局部特征向量构成的矩阵, 第i行表示第i个用户的兴趣局部特征向量, 局部特征向量由原来的N=46维降到r=3维。可以大大简化后面的计算量。

④根据特征向量间的相似度, 自组织学习社区。根据式 (6) 计算出M=12个学生用户之间的匹配程度, 使用矩阵表示为

$\begin{matrix} u s e r 1 \\ u s e r 2 \\ u s e r 3 \\ u s e r 4 \\ u s e r 5 \\ u s e r 6 \\ u s e r 7 \\ u s e r 8 \\ u s e r 9 \\ u s e r 10 \\ u s e r 11 \\ u s e r 12 \end{matrix} [\begin{matrix} 1 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.69647 & 0.64377 & 0.65392 & 0.46811 & 0.22933 \\ 0.22933 & 1 & 0.29816 & 0.24005 & 0.69939 & 0.69939 & 0.29816 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.69939 \\ 0.22933 & 0.29816 & 1 & 0.24005 & 0.29816 & 0.29816 & 0.57877 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.29816 \\ 0.22933 & 0.24005 & 0.24005 & 1 & 0.24005 & 0.24005 & 0.24005 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.24005 \\ 0.22933 & 0.69939 & 0.29816 & 0.24005 & 1 & 0.70074 & 0.29816 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.70074 \\ 0.22933 & 0.69939 & 0.29816 & 0.24005 & 0.70074 & 1 & 0.29816 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.74846 \\ 0.22933 & 0.29816 & 0.57877 & 0.24005 & 0.29816 & 0.29816 & 1 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.29816 \\ 0.69647 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 1 & 0.64377 & 0.65392 & 0.46811 & 0.22933 \\ 0.64377 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.64377 & 1 & 0.64377 & 0.46811 & 0.22933 \\ 0.65392 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.65392 & 0.64377 & 1 & 0.46811 & 0.22933 \\ 0.46811 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 0.46811 & 0.46811 & 0.46811 & 1 & 0.22933 \\ 0.22933 & 0.69939 & 0.29816 & 0.24005 & 0.70074 & 0.74846 & 0.29816 & 0.22933 & 0.22933 & 0.22933 & 0.22933 & 1 \end{matrix}]$

输入阈值0.3, 在原来的模糊矩阵中, 模糊系数大于给定阈值的将被置成1, 小于阈值的将被置成0,

$\begin{matrix} u s e r 1 \\ u s e r 2 \\ u s e r 3 \\ u s e r 4 \\ u s e r 5 \\ u s e r 6 \\ u s e r 7 \\ u s e r 8 \\ u s e r 9 \\ u s e r 10 \\ u s e r 11 \\ u s e r 12 \end{matrix} [\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}]$

最后第4节介绍的匹配浓度法自组织学习社区。user1、user8、user9、user10、user11进入社区1学习, user2、user5、user6、user12进入社区2学习, user3、user5、user7进入社区3学习, user4进入社区4学习。

5.2 结果分析

①特征向量降维时, 设置的维数r越小, 对应的概念数N越小, 算法的复杂度就越小。没有采用CI特征降维设置时, 默认情况下的计算复杂度依赖于本体中概念的数量, 当用CI降维后, 计算复杂度将直接受用户设置维数的影响。

②根据学生用户之间的兴趣匹配度, 设定阈值T1, 计算每个学习者的匹配浓度, 求出1值最多者 (即浓度最高者) , 然后以此为中心组建社区。阈值过小, 社区数较少, 每个社区的学习者人数越多, 会将兴趣不同的学习都归入同一社区。反之, 阈值过大, 会使社区数目增多, 会使兴趣相近的学习都分到不同社区学习。故阈值的大小要根据经验取值, 不宜过大或过小。

③采用基于本体的向量空间模型, 考虑了概念相关性, 本文以同济大学网络教育学院学生为实验对象, 实验表明, 兴趣社区自组织算法具有较高的划准率和划全率。定义划准率和划全率的计算公式为:

$\begin{array}{l} 划准率 = \frac{社区学生认同数}{社区学生总数} \\ 划全率 = \frac{社区学生总数}{参与学生总数} \end{array}$

划准率的计算采用人工判断返回信息项的方法计算, 例如对20名学生进行社区划分后, 人工地判断与学生用户期望一致得到肯定的信息项数为n, 那么划准率为p=n/20, 采用本节算法, 分别对学生人数M为20、50和100时进行了实验, 在M=20时, 平均的划准率=83%;M=50时, 平均的划准率=95%;M=100时, 平均的划准率=98%。实验表明, 实验对象越多, 划准率越高。对于算法中浓度低于T0的学习者, 计算他与各社区中心学习者的相似度, 进入最相近的社区学习, 故该算法划全率达到近100%。学生能根据自己描述的兴趣进入最适合自己的社区进行学习。

6 结语

基于本体的向量空间模型计算学习者的兴趣特征向量, 它是一种考虑了术语间语义相关性的计算模型, 根据学习者描述的兴趣信息, 以学习者共同的知识背景——本体为基础, 根据兴趣的隐性表示获取对应的显式表示 (即兴趣向量) , 通过有限本体图计算概念间的语义相关度, 克服了传统的向量空间模型中术语间语义相关性被忽略的缺点, 能够提高兴趣相似性比较的精确程度。并根据兴趣相似度的思想, 提出了一种基于学习者兴趣相似匹配度和学习者相似匹配浓度的学习社区的自组织算法。针对基于本体的向量空间模型使用本体中的概念构造向量空间表现出的巨大维数, 把概念索引降维法改进运用于兴趣特征降维, 对兴趣特征矩阵进行合理的降维处理, 然后进行匹配计算, 大大降低运算量和计算的复杂度, 提高算法效率。

摘要：为了解决远程教育不可避免地产生的“孤独”学习者的问题, 把具有相同学习兴趣的学习者组织到同一个学习社区中进行协作式学习。学习社区建立的重点和难点在于学习者之间相似关系的判定和计算, 针对传统的向量空间模型中术语间语义相关性被忽略的不足, 提出基于本体的向量空间模型来计算学习者的兴趣特征向量, 根据兴趣的隐性表示获取对应的显式表示, 此计算模型提高了兴趣相似性比较的精确程度。同时提出了一种基于学习者兴趣相似匹配度和学习者兴趣匹配浓度的学习社区的自组织算法。针对基于本体的向量空间模型使用本体中的概念构造向量空间表现出的巨大维数, 运用概念索引降维法对兴趣特征矩阵进行合理降维, 大大减少了计算的复杂性。最后, 以网络学习案例来进行实验分析, 验证该模型算法具有较高的效率和良好的扩展性。

关键词：本体,兴趣特征向量空间模型,概念索引降维,兴趣相似匹配度,兴趣匹配浓度

参考文献

[1]Tillman H N.Virtual community building using in-ternet tools[OL].Http://www.Hopetillman.com/i100/vc.htm, 2004-10-16.

[2]JoKim A著.张署, 胡蓉, 赵明译.网络社区建设——设计策略揭密[M].北京:清华大学出版社, 2001.

[3]Baeza-Yates R, Ribeiro-Neto B.Modern informationretrieval[M].ACM Press, 1999.

[4]Dumais S T.Using LSI for information retrieval, information filtering and other things[Z].Talk atCognitive Technology Workshop, April 4~5, 1997.

[5]Letsche T A, Berry M W.Large-scale informationretrieval with latent semantic indexing[J].Informa-tion Sciences-Applications, 1997, 100 (1~4) :105~137.

[6]Gauch S, Chaffee J, Pretschner A.Ontology-basedpersonalized search and browsing[J].Web Intelli-gence and Agent Systems, 2003, 1 (3~4) :219~234.

[7]Lin J, Gunopulos D.Dimensionality reduction byrandom projection and latent semantic indexing[A].Text mining workshop, at the 3rd SIAM Interna-tional Conference on Data Mining[C].2003.

[8]Kaski S.Dimensionality reduction by random map-ping:fast similarity computation for clustering[A].Proceedings of international joint conference on neu-ral networks (IJCNN’98) [C].IEEE Service Center, Piscataway, NJ, 1998:413~418.

[9]Fodor I K.A survey of dimension reduction tech-niques[R].LLNL technical report, UCRL-ID-148494, http;//www.llnl.gov/CASC/sapphire/pubs.html, 2002.

[10]Dumais S, et al.Using latent semantic analysis toimprove access to textual information[A].Proceed-ings of the conference on human factors in comput-ing systems CHI’88[C].Washington, D.C., USA, 1988.

自组织算法论文篇7

定位信息已逐渐成为未来商业、公共服务和军事网络的重要特征之一。近几年发展起来的自组织网络(Ad Hoc network)因具有灵活、无中心、自组织和抗毁性强等优势,具有广阔的应用前景。节点动态和精确的定位技术是无线自组织网络的主要技术之一。节点精确的位置估计能降低组网成本,同时提升网络的通信性能。此外,精确的位置估计能扩大网络的应用范围,使其应用于存货管理、入侵检测和交通监测等领域[1—3]。

具有定位能力的自组织网络要求网络为成对的节点提供距离估计。在三维(二维)空间中,目标节点需要知道自身和至少四(三)个参考节点的距离信息以及这些参考节点的位置信息才能确定自己的位置[4]。但对于Ad Hoc网络中的节点而言,通常无法直接和足够多的参考节点进行通信。为此,本文提出一种协作定位(CP,Cooperative Positioning)算法。在目标节点通信范围内只有少量参考节点的情况下,协作定位算法通过和其通信范围内非参考节点的协作,实现目标节点的定位。

估计发送节点和接收节点之间的距离的过程称为测距。测距是定位的前提。目标节点和参考节点的距离信息可以通过接收信号强度指示(RS-SI,Received Signal Strength)法或到达时间(TOA,Time of Arrival)法获得。超宽带(UWB,Ultra Wide Band)技术以其带宽宽和抗多径等特点,具有精确的测距能力。在视距传输(LOS,Line-of-Sight)场景中,基于TOA的超宽带测距技术可达几十厘米的精度。然而,在多径效应比较严重的环境中,节点间的视距传输路径可能被阻隔,从而无法得到精确的距离信息。非视距(NLOS,non-LOS)环境严重降低了节点的测距精度。在这种情况下,节点即使能够和足够多的参考节点进行通信,但由NLOS测距信息计算得到的位置信息也会产生很大偏差[1]。如果节点放弃非视距通信的参考节点的测距信息,则会因为缺少足够的参考节点而无法完成定位。利用本文提出的协作定位算法,目标节点可以放弃非视距参考节点,而通过和邻居非参考节点的协作实现精确定位。

1算法描述

1.1网络模型

首先考虑LOS情况下的定位。假设目标节点的位置表示为p=[x y]T,LOS参考节点的位置表示为pLj=[xLjyLj]T,其中j=1,2,…,mL。对于二维空间,要确定目标节点的位置,要求mL≥3,如图1所示。

假设目标节点到参考节点的真实距离和测量距离分别表示为RLj和rLj,j=1,2,…,mL,由文献[1]知

rLj=RLj+nLj,j=1,2,…,mL (1)

式(1)中nLj表示测距误差,且nLj服从零均值高斯分布,即nLj～N(0,σLj2),并且σ $_{L_{j}}^{2}$ =KER $_{L_{j}}^{β_{L j}}$ ,其中σLj是LOS路径损耗指数,而KE依赖于发送功率和接收机的背景噪声。

节点的定位误差定义为 $∥ p - \hat{p} ∥$ ,式中 $\hat{p}$ 表示位置估计值[1]。

目标节点的位置p可由下列方程组得到

‖p-pLj‖=R $_{L_{j}}^{2}$ ;j=1,2,…,mL (2)

测距误差的存在导致节点间非理想的距离估计,使得式(2)可能不成立[4]。在测距过程中产生的误差对定位精度的影响可以通过采用最小化过程比如LS(Least Square)算法[1]来减小。

1.2 协作定位算法CP

对于Ad Hoc网络中的节点而言,通常无法直接和足够多的参考节点进行通信。如图2所示,目标节点T1的通信范围内只有两个参考节点L1、L2,以及一个非参考节点T2。T1可以获得L1和L2的位置信息pL1=[xL1yL1]T和pL2=[xL2yL2]T,以及和它们之间的测距信息rT1L1和rT1L2。由于T2是非参考节点,T2的位置信息p2=[x2y2]T未知。但T2可以获得自身通信范围内参考节点L3的位置pL3=[xL3yL3]T和它们之间的测距信息rT2L3。通过和T2的通信,T1可以得到T1和T2之间的距离估计r $_{Τ 1 Τ 2}^{[4]}$ ,并且获得pL3=[xL3yL3]T和rT2L3。通过解下列方程T1可计算出自己的位置:

${\begin{cases} (x_{Τ_{1}} - x_{L_{1}})^{2} + (y_{Τ_{1}} - y_{L_{1}})^{2} = r_{Τ_{1} L_{1}}^{2} \\ (x_{Τ_{1}} - x_{L_{2}})^{2} + (y_{Τ_{1}} - y_{L_{2}})^{2} = r_{Τ_{1} L_{2}}^{2} \\ (x_{Τ_{1}} - x_{Τ_{2}})^{2} + (y_{Τ_{1}} - y_{Τ_{2}})^{2} = r_{Τ_{1} Τ_{2}}^{2} \\ (x_{Τ_{2}} - x_{L_{3}})^{2} + (y_{Τ_{2}} - y_{L_{3}})^{2} = r_{Τ_{2} L_{3}}^{2} \end{cases} (3)$

注意式(3)仅能确定T1的位置,无法确定T2的位置。

下面我们用仿真实验来验证CP算法的性能,用LS算法和CP算法分别对图1和图2的场景进行仿真。取β=2和KE∈[0,0.1][1],仿真结果如图3所示。由图3可知CP算法的性能较优。

2 NLOS的影响

NLOS测距估计可表示如下:

rNj=RNj+nNj+bNj (4)

式(4)中RNj为目标节点和参考节点之间的实际距离,nNj～N(0, σNj2),σ $_{Ν_{j}}^{2}$ =KER $_{Ν_{j}}^{β_{Ν}}$ ,βN是NLOS环境下的路径损耗指数,bNj为NLOS造成的测距误差,并且bNj服从平均分布:bNj～U(0,Bmax),其中Bmax表示最大可能误差,且Bmax≫σNj[1]。

NLOS参考节点的存在会导致定位精度的下降,通过协作定位算法,目标节点可以放弃NLOS参考节点,而选择非参考节点进行定位。仿真结果如图4所示,由图4可知协作定位算法的性能远远优于NLOS存在时的LS算法的性能。

3 结束语

本文提出了一种基于超宽带无线自组织网络的协作定位算法。该算法能在目标节点通信范围内的参考节点数较少或者存在NLOS参考节点时,通过和非参考节点的协作对目标节点进行精确定位。仿真结果验证了该算法的有效性。

参考文献

[1] Venkatesh S,Buehrer R M.NLOS mitigation using linear program-ming in ultrawideband location-aware networks.IEEE/Transactionson Vehicular Technology,2007;56(5):3181—3198

[2] Cheng Xiuzhen,Shu Haining,Liang Qilian,et al.Silent positioningin underwater acoustic sensor networks.IEEE/Transactions on Vehic-ular Technology,2008;57(3):1756—1766

[3]黄毅,胡爱群.无线传感器网络定位算法综述.电信科学,2010;(7):69—75

自组织算法论文篇8

由于网络拓扑的动态变化在传输数据时具有挑战性,车载自组织网络(Vehicular Ad Hoc Network,VENET)受到工业界和学术界的高度关注[1,2,3,4]。分簇技术由于控制信息仅需在簇内传输可以合理分配资源,减少对带宽的占用和通信的开销,还可以有效改善广播信道的特性,成为研究重点。

Peng F[6]等人则在WCA[5](Weighted Clustering Algorithm)基础上,提出了适合车载网络的加权分簇策略,增加了交通信息,修改平均速度v权重来适应车辆移动环境;基于最高节点度改进的HD[7](Higher Connectivityand Lower ID Cluster Algorithm)分簇策略则通过结合节点的连接度数(connectivity degree)和最小ID来作为分簇的依据,算法通过维护邻居表的信息,选择连接度最优的节点作为簇头。该方法方法简单有效,能够保证网络中簇的数目较少,分组投递时延降低。

本文分别考虑路段区域(Segment)和路口区域(Intersection)的连接度和链路连通时间并结合传统综合权重的WCA[5]分簇算法,实现不同道路模型下簇头的推举和基于网络区域位置的分簇维护,有效的提高了网络分簇的稳定性和环境适应性。

1 基于区域自适应的动态分簇算法

1 .1 连通度的计算

为了描述车载自组织网络的连通性,做如下定义:

(1)车载自组织网络的网络拓扑结构可以看做是由节点和链路构成的无向图,记做G(V,E),V为车辆节点集合,E为通信链路边集合。

(2)节点连通度

节点连通度Na(t)为t时刻车辆节点a周围所存在的可连通邻居节点数目的总和,计算如式(1),其中,Dai(t)表示在t时刻节点a与节点i之间的距离,Dth为网络设定的距离阈值,满足Dth≤r,其中r为车辆的通信半径。

(3)节点平均连通强度

节点连通强度Qa(t)为t时刻节点a与邻居节点i链路连通的平均时长值。计算如式(2),式中Tai(t)为t时刻节点a与i预测的所能保持的链路连通时间,m为当前时刻的节点连通度Na(t)。

(4)区域连通度

区域连通度Cz(t)为t时刻网络区域Z内节点的平均连通度,有效的表征节点所处区域的网络连通状况。计算如式(3),式中i为区域Z内的节点,Ni(t)为节点i的连通度,n为网络区域Z内的节点数目。

1.2连通时间Tab(t)的确定

将道路划分为路段模型(Segment Model)和路口模型(Intersection Model)分别计算节点的链路连通时间。

(1)路段的连通预测

在路段模型下,车辆之间的位置关系则近似在一条直线上,车辆之间的移动分为同向和相向两种。当t时刻节点A和B处于连通状态时,在t时刻A与B所能保持的连通时间Tab(t)满足条件式(4),Dth为距离阈值,满足Dth≤r。其中,pa(x,y)为节点A在t时刻的位置坐标,xa(t)和ya(t)分别为节点A的横纵坐标,va(t)为节点A在t时刻的速度矢量,r为节点通信半径。在t+Δt时刻路段上节点A与节点B的距离用Dab(t+Δt)来表示,计算如式(5):

其中,α为t时刻节点A与B之间与道路方向的夹角,满足0°≤α<180°;ΔVab为节点A与节点

B在Δt内的平均相对速度,其中车辆间的距离Dab满足式(6)的关系条件,其中d为节点A、B之间的垂直于道路方向上的距离。在路段环境下,当A和B在相同车道上时d近似为0,在相邻车道上时d近似等于dr,其中dr为路段Segement(x,y)的宽度。

如图1右所示,进一步分析距离d与节点A和B坐标满足式(7),其中θ为路段与水平方向的夹角,满足0°≤θ≤90°。

结合式(7)、(6)、(5)、(4)、化简得到t时刻A与B所能保持的链路连通时间Tab(t)的计算如式(8):

(2)路口的连通预测

如图2所示,灰色的区域定义为路口区域,通过对路口车辆的运动状态的分析,定义如下:ab

1当车辆A和B同时位于路口Intersection(x,y)时,若A与B的移动方向分别由路口指向不同的路段时,若A和B之间的距离Dab(t)满足式(9),则Tab(t)=0,如图所示车辆节点C与D。其中li、wi分别为路口Intersection(x,y)区域的长度和宽度。

2若车辆A和B的移动方向不在同一路段,且不满足上述状态,车辆连通时间预测如下。在t+Δt时刻车辆A和B之间距离Dab(t+Δt)满足式(10)。

在t+Δt时刻,节点A的位置坐标计算如式(11)和式(12)所示。

其中θ为节点A所在路段方向与水平方向的夹角,满足0°≤θ≤90°,如图2右示。同理可得节点B的位置坐标如式(13)和式(14),其中ω为路口模型下节点A与B分处的两条路段Segement(x,y)之间的夹角,满足0°≤ω<180°。如图2左示意图。

因此,将上式代入条件式(4)并化简,在满足距离小于等于Dth的条件下,t时刻A与B所能保持的链路连通时间Tab(t)的计算如式(15):

其中Δvx和Δvy的分别为Δt内节点A和B速度在坐标水平分量和垂直分量的差值,Δx和Δy则分别为t时刻节点A和B的坐标水平分量和垂直分量的差值。

1.3 优先级的选取

在簇头的选举机制上本文采用基于加权分簇WCA的改进方案,对不同权重进行加权计算,区分节点当前所在道路环境,计算所得的综合权重值最大则性能最优,优先推选为簇头节点,节点的综合连通度权重值计算如式(16):

其中Ni为节点连通度,Nth是系统连通度阈值,其大小取决于网络规模和车辆数量,w1,w2,w3,w4分别为权重因子。Δq(i)为节点i连通强度归一化值,表征了当前节点与邻居节点连通强度的相对大小,Δv(i)表征了当前车辆节点i的运动状态,满足Δv(i) ≤1,计算如式(17)、(18),满足Δq(i)≤1。其中Qi为节点i连通强度,Qj为邻居节点j的连通强度,N为节点i的邻居节点数目。vmax为最大行驶速度,vi为节点i当前行驶速度,δ(i,t)为节点i在(t,t-Δt)时间段内速度方差值,并定义车辆i速度在[0,1]区间时,Δv(i)=1。N为节点i的邻居数目,Nc为运动方向与Wcon(i),并开始执行网络区域分簇ZACA算法。簇形成的流程图如图3所示:

节点i一致的邻居节点数目。

在路口Intersection(x,y)下,车辆的连通强度越高,行驶速度越低则综合权重值Wcon越高,节点在成为簇头后,分簇的稳定性越高,簇的存活时间越长分簇自适应维护。

1.4 簇的形成过程

在网络初始化阶段,节点获取位置信息p(x,y)、节点速度v、方向d,并将位置信息填充至BM包的相应字段中,广播给邻居节点。节点收到邻居节点BM消息包后,创建更新邻居表。通过遍历邻居表,计算当前节点的连接度Ni,连通强度Qi,区域连通度Cz,当前的连通度综合权值Wcon(i),并开始执行网络区域分簇ZACA算法。簇形成的流程图如图3所示:

1.5 簇的维护过程

本文针对车辆节点在不同的道路环境下进行自适应的维护。

(1)加入与离开的簇维护流程图如图4所示:

(2)簇的合并与拆分

由于车辆节点的移动,分簇的通信半径相互覆盖。为了降低簇的叠加度和分簇冗余,簇合并的流程图如图5所示:

2 基于区域的分簇算法性能仿真

2.1 仿真环境

本文从簇头数目、单位时间节点平均转移次数和单位时间簇头控制集更新次数三个方面来对比基于节点连接度HD算法和区域自适应ZACA分簇算法的性能。本文仿真区域大小为1900m×1200m,针对不同仿真场景,车辆的数目分别设置为[50,100,150,200,250, 300],车辆的速度随机取值[0-25]m/s,节点的移动模型采用基于智能车道选择模型IDM_IC的扩展模型。节点在路口的等待时间随机取值[0-20]s,节点初始位置为随机分布,系统模拟运行时间为600s,每个场景仿真10次,取平均值。系统参数的设置则通过对仿真的反复模拟得出的最优值,对于路段环境(Segment)下的w1、w2、w3、w4权重因子分别为0.24,0.26,0.16,0.34,而路口环境 (Intersection)下的w1、w2、w3、w4权重因子分别为0.26,0.32,0.30,0.12。簇头切换比例参数η为2.5,簇成员数目最大阈值Mmax为15,距离阈值Dth为135。

2.2 仿真结果

从子图6可以看出,随着车辆的移动,ZACA分簇算法簇头的数目则稳定在22-31范围,而HD分簇算法则表现出较大幅度的摆动,其簇头数目的平均值也高于的ZACA分簇算法。如图7可以看出随着车辆数目的不断增加,与HD算法相比ZACA算法节点的平均转移次数能保持较低的增速。图8可以看出显示相比于HD分簇算法,基于区域的ZACA分簇算法在网络节点数目增加的情况下,单位时间内分簇集的更新次数低于HD分簇算法,且次数的增速平缓。仿真结果显示,ZACA能够较好地适应城市环境,并且具有较高的稳定性。综合可得出区域自适应ZACA分簇算法优于基于节点连接度HD算法。

3 结语

本文鉴于以往提出网络节点的分簇算法的种种局限性,提出了一种新的基于区域的车载自组织网络节点分簇算法。并通过仿真与基于节点连接度HD算法进行比对。仿真结果证明本文ZACA分簇算法能有效提高分簇的稳定性、环境的适应性、并减低开销。

参考文献

[1] Boukerche A,Oliveira H A B F,Nakamura E F,et al.Vehicularadhoc networks:A new challenge for localization-based systems[J].Computer communications,2008,31(12):2838-2849.

[2] L Fan,W Yu.Routing in vehicular ad hoc networks:A survey[J].IEEE Veh.Technol.Mag.2007,2(2):12-22.

[3] KAUR M.Vehicular ad hoc networks[J].Journal of Global Research in Computer Science,2012,3(3):61-64.

[4] Villas L A,Ramos H S,Boukerche A,et al.An efficient and robust data dissemination protocol for vehicular ad hoc networks[C].Proc of the 9th ACM symposium on Performance evaluation of wireless ad hoc,sensor,and ubiquitous networks.ACM,2012:39-46.

[5] Chatterjee M,Das S K,Turgut D.WCA:A weighted clustering algorithm for mobile ad hoc networks[J].Cluster Computing,2002,5(2):193-204.

[6] Fan P,Haran J,Dillenburg J,et al.Traffic model for clustering algorithms in vehicular ad-hoc networks[C].Proc.of CCNC.2006:168-172.

[7] Nocetti F G,Gonzalez J S,Stojmenovic I.Connectivity basedk-hopclus teringin wireless networks[J].Telecommunication systems,2003,22(1-4):205-220.

【自组织算法论文】推荐阅读：

自编码算法07-01

自适应算法09-02

RLS自适应算法08-26