分层算法范文（精选7篇）
分层算法 第1篇
互联网和 电子商务 的迅猛发 展已经把 人们带入 了一个信 息爆炸的 时代 , 商品种类 和数量的 快速增长 , 使得顾客 花费了大 量的时间 浏览无关 的信息 , 个性化推 荐系统作 为解决信 息过载的 方法应运 而生 , 被广泛的 应用到了 当前的电 子商务系 统[1]。 而基于协 同过滤的 推荐算法 无疑是最 广泛使用 的算法[2], 其主要分 为基于用 户 ( User - based ) 和基于商 品 ( Item - based ) 的推荐算 法[3]。 基于用户 的协同过 滤算法主 要通过计 算用户之 间的相似 性 , 通过对与 目标用户 相似性较 高的用户 对商品的 评价信息 从而推荐 给目标用 户 。 基于项目 的协同过 滤算法则 是查找项 目之间的 相关性 。 但是在电 子商务网 站当中 , 用户评分 数据不会 超过项目 总数的百 分之一[4], 稀疏性以 及实时性 都是急需 解决的问 题 。
针对推荐 实时性问 题 , 文献 [5] 在Hadoop平台上实 现了User-based并行协同过滤推荐算法;文献[6]在Hadoop平台上实 现了Item-based协同过滤 推荐算法 , 其时间复 杂度为O (n2m2) ; 燕存[7]针对其时 间复杂度 过高的问 题 , 提出了一 种改进的Item-based协同过滤 推荐算法 。 针对数据 稀疏性问 题 , 王雪蓉[8]研究了将 用户行为 关联聚类 以实现更 好的推荐 效果 , 任帅[9]基于用户 行为模型 和蚁群聚 类以实现 更合理的 推荐 。 Spark作为一个 新的开源 集群计算 框架 , 其基于内 存计算以 及粗粒度 的RDD机制非常 适合于迭 代型的计 算 。 本文针对 推荐实时 性以及数 据稀疏性 问题 , 基于Spark平台 , 提出一个 分层的协 同过滤推 荐算法 。
1Spark相关技术
Spark作为一个 分布式框 架 , 它支持内 存计算 、 多迭代处 理 、 流处理与 图计算多 种范式 , 非常适合 于各种迭 代算法和 交互式数 据分析 , Spark的核心抽 象模型是RDD ( 弹性分布 式数据集 ) , 基于RDD , Spark提供了一 个非常容 易使用的 编程接口 。
1.1弹性分布式数据集
RDD是不可变 的 , RDD一旦创建 就没有办 法对其进 行更改 , 但是却能 创建出新 的RDD。 其次 , RDD的不可变 性使得Spark提供了高 效的容错 机制 , 由于每个RDD都保留有 计算至当 前数值的 全部历史 记录 , 而且其他 进程无法 对其作出 更改 。 因此 , 当某个节 点丢失数 据时 , 只需要对 该节点的RDD重新计算 即可 , 并不影响 其他节点 的运行 。 RDD机制如图1所示 。
1.2Spark应用程序框架
Spark Application的运行架 构由两部 分组成 : driver program ( Spark Context ) 和executor 。 Spark Application一般都是 在集群中 运行 , 如standalone、yarn、mesos等 。 在这些集 群当中提 供了计算 资源和资 源管理 , 这些资源 即可以给executor执行 , 也可以给driver program运行 。 根据driver program是否在集 群中 , Spark Context又可以分 为cluster与client模式 。 Spark应用程序 框架如图2所示 。
2用户偏好模型
定义1 (用户偏好 集合 ) 将用户在 网站浏览 行为中的 平均访问时间、点击数目、购买数目 、点击收藏比 、点击加入购 物车 、平均收藏 与购买间 隔以及平 均点击与 购买间隔7种特征构 成用户偏 好集和 :IA= { A1, A2, A3, … , A7} 。
为了构建 用户偏好 模型 , 需要为用 户偏好集 合中不同 的特征赋 予不同的 权值 , 以便区分 不同特征 对模型的贡献程度 , 且满足 :如表1。
表1中的7种偏好特 征从不同 程度上代 表了用户 的行为习 惯 , 为每一种 偏好特征 赋予一个 权值 , 从而得出 的用户偏 好模型如 下 :
使用熵权 法[10]来确定每 一个偏好 特征的权 值 , 它通过统 计的方法 处理后获 得权重 。 将用户ui的偏好特 征表示成n×7阶矩阵B= (bij) n × 7, 其中bij表示用户i第j个特征的 值 。 熵权法的 计算过程 如下 :
( 1 ) 标准化数 据处理 , 如式 ( 2 ) 、 式 ( 3 ) :
其中, sij表示用户i第j个特征权值的值, max (bij) 与min ( bij) 分别是第j项特征权 值的最大 值与最小 值 。
( 2 ) 计算各种 偏好特征 的熵值 , 如式 ( 4 ) :
其中 ,
( 3 ) 计算权重 , 如式 ( 5 ) :
通过以上 方法便可 计算出用 户偏好模 型中每一 种偏好特 征的权值 。
3并行化EM算法
期望最大 化 (EM) 算法是在 模型中寻 找参数的 最大似然 估计或者 最大后验 估计的算 法 , 它从一个 最初的假 设开始 , 迭代计算 隐藏变量 的期望值 。 再重新计 算极大似 然估计 , 直到收敛 于一个局 部最大似 然估计 。 算法的实 现过程如 下 :
( 1 ) 估计参数 : 利用式 ( 5 ) 将每个对 象xi指派到对 应的用户 簇中 。
其中 , p (xi| Ck) = N ( μk, E ( xi) ) 服从方差 为E ( xi) 、 期望为 μk的正态分 布 , 参数估计 是对每一 个用户簇 计算对象 的隶属概 率 。
( 2 ) 最大化 : 利用上一 步骤的结 果重新估 计参数以 使针对给 定数据的 分布似然 最大化 。
( 3 ) 重复以上 步骤直到 参数收敛 , 聚类过程 完成 。
为了实现EM算法的并 行化 , 首先将用 户偏好模 型数据划 分到集群 上的每一 个节点 , 即将用户 划分成M个组 :U1, … UM, 每一组用 户为一张 二维关系 表 , 行为用户 实例 , 列为偏好 特征值 , 并行化算 法如下 :
( 1 ) Combine users , 分别在不 同的结点 计算任意 两个用户 的相似度 , 并将相似 度高的两 个类别合 并成一个 类别 ;
( 2 ) Compute similarity , 根据式 ( 6 ) 计算每一 个类别的 相似性 ;
( 3 ) Shufflle , 全局hash划分类别 ;
( 4 ) Checkpoint , 将不同类 别缓存到 内存中 ;
( 5 ) Recycle , 根据式 ( 7 ) 对参数求 精 , 并重复此 过程 , 直到完成 聚类 ;
( 6 ) Clean , 清除中间 数据 , 并将结果 按类别存 储在不同 计算节点 上 。
4并行化协同过滤算法
Item - based协同过滤 将一个用 户所购买 的商品推 荐其匹配 的相似商 品 , 即将所有 用户对购 买的商品 的评价作 为一个向 量 , 通过向量 计算物品 之间的相 似度 。 用U对商品i与商品j共同评价 的用户集 合 , 则它们之 间的相似 度sim (i, j) 可通过Pearson相关系数 计算 :
将用户评 分数据文 件存放在HDFS上 , 每一行数 据代表一 个用户的 历史购买 项目记录 , 详细算法 如下 :
( 1 ) data = sc . text File ( “ hdfs : / / ” ) , 加载数据 , 每行数据 代表一个 用户的历 史购买项 目记录 ;
( 2 ) get Items And Ratings ( data , items , ratings , len ) , 划分数据 , 获取到所 有项目及 评分存入items数组与ratings数组中 ;
( 3 ) ( item_a , item_b ) = zip ( items 1 to len ) , 将项目两 两组成对 ;
( 4 ) ( ratings_a , ratings_b ) = zip ( ratings 1 to len ) ;
( 5 ) shuffle , 全局hash划分数据 , 将相同项 目对划分 到同一个 结点 ;
( 6 ) Compute Pearson ( ) , 由式 ( 8 ) 计算两项 目之间的 相似度 ;
( 7 ) read Item ( key , item1 , item2 ) , 从项目对 中解析出 两个项目 ;
( 8 ) Shuffle , 将包含某 一项目的 所有项目 划分到同 一个结点 中 ;
( 9 ) Cache ( key , value ) , 缓存项目 及其相似 度列表 ;
( 10 ) Prediction ( ) , 预测未购 买商品的 评分 ;
(11) save As Text File () , 输出并存储用户推荐商品列表 。
5基于Spark分层协同过滤推荐算法
在执行算 法之前 , 首先需要 将数据集 加载到HDFS文件系统 中 , 首先Spark会生成一 个SparkContext全局常量 , 将基于Spark Context从HDFS上读取数 据 , text File () 这个函数 有助于从HDFS上读取数 据并形成 一行一行 为基础的RDD。 可以使用cache将数据加 载到内存 以便重复 使用 。 详细算法 实现如下 :
( 1 ) 准备 : 搭建Hadoop与Spark集群 , 并将数据 存放到HDFS;
( 2 ) 由用户行 为计算偏 好特征权 值 ;
( 3 ) 存储用户 偏好特征 数据 ;
( 4 ) 并行EM算法对用 户聚类 ;
( 5 ) 将不同用 户簇存放 不同结点 ;
( 6 ) 将用户 - 评分数据 存入相同 用户结点 , 数据本地 性 ;
( 7 ) 并行运行 协同过滤 算法 ;
( 8 ) 预测用户 - 商品评分 ;
( 9 ) 形成推荐 列表并保 存 。
6实验及分析
在实验集 群当中 , 有一个master节点 、3个slaves节点 , 每个节点 的内存为8 GB, 2核 。 集群当中 安装的是Hadoop2 . 4 . 1与Spark1 . 3 . 0版本 。 程序采用Intelli J集成开发 环境完成 , 本实验主 要实现了 基于Spark的分层协 同过滤算 法并与基 于Map Reduce的并行算 法的对比 。
( 1 ) 准确率 、 时间复杂 度分析
实验一数 据采用阿 里巴巴云 平台的天 池数据 , 总共十万 多条行为 记录 , Map Reduce使用并行Item -based协同过滤 算法 , Spark使用分层 协同过滤 推荐算法 , 实验结果 如表2所示 。
从表1可以看出 , 基于Spark的分层协 同过滤算 法在准确 率上比普 通的协同 过滤算法 更高 , 并且大大 节约了时 间 , 提高了性 能 。
( 2 ) 性能表现
实验二测 试Spark实现的分 层协同过 滤算法的 扩展性 , 分析了在 不同节点 个数上的 性能表现 , 如图3所示 。
从图中可 以看到 , 当节点数 量达到一 定程度以 后 , 其所消耗 的时间并 没有减小 得太厉害 。 接下来将 会测试在 不同大小 的数据集 上算法所 表现出来 的性能 。
7结束语
协同过滤 是推荐算 法中最为 广泛使用 的推荐算 法 , 研究协同 过滤的并 行化算法 也非常多 。 本文在前 人的基础 上 , 提出一种 基于Spark的分层协 同过滤推 荐算法 , 其核心是 把用户按 不同的偏 好特征划 分不同的 用户簇 , 之后针对 不同的用 户簇作协 同过滤推 荐 。 另外 , 在Spark平台上实 现该算法 并与Map Reduce的算法比 较 。 实验结果 表明 , 算法提高 了推荐准 确率与时 间性能 , 并具有一 定的拓展 性 。
参考文献
[1]MALTONI D, MAIO D, JAIN.A handbook of fingerprint recognication[M].Berlin, Springer, 2009.
[2]LINDEN G, SMITH B, YORK J.Amazeon.com recommendations:item-to-item collaborative filtering[J].IEEE Internet Computing, 2003, 7 (1) :76-80.
[3]SCHAFER J B, FRANKOWSKI D, HERLOCKER J, et al.Collaborative filtering recommender systems[M].Berlin Heidelberg:Springer, 2007:291-324.
[4]SUN X H, KONG F S, YE S.A comparison of several algorithms for collaborative filtering in startup stage[C].Proceedings of the 2006 IEEE International Conference on Networking, Sensing and Controlling.Washington, DC:IEEE Computer Society, 2006:25-28.
[5]ZHAO Z D, SHANG M S.User-based collaborative-filtering recommendation algorithms on hadoop[C].Third International Conference on Knowledge Discovery and Data Min ing.Thailang:IEEE, 2010:478-481.
[6]JIANG J, LU J, ZHANG G, et al.Scaling-up item-based collaborative filtering recommendation algorithm based on hadoop[C].2011 IEEE World Congress on Services (SERVICES) .Washington:IEEE, 2011:490-497.
[7]燕存, 吉根林.Item-Based并行协同过滤推荐算法的设计与实现[J].南京师大学报 (自然科学版) , 2014, 37 (1) :71-76.
[8]王雪蓉, 万年红.云模式用户行为关联聚类的协同过滤推荐算法[J].计算机应用, 2011, 31 (9) :2421-2426.
[9]任帅, 王浙明, 王明敏.基于用户行为模型和蚁群聚类的协同过滤推荐算法[J].微型电脑应用, 2014, 30 (3) :5-9.
基于分层结构的WSN路由算法改进 第2篇
一个标准的WSN网络通常由许多传感器节点组成, 这些节点一般都是依靠电池提供能量, 但是经过一段时间的使用之后, 电池的更换一般都很难实现, 除了电能资源稀少珍贵之外, 包括处理能力, 无线通信带宽, 储存空间都十分有限, 所以传感器节点的节能工作就成为延长WSN生命周期最主要的部分。在任何一种网络中, 路由算法的优劣在一定程度上决定了整个网络系统的性能, 一个好的路由算法能够有效地降低网络节点的能耗[2]。
本文旨在通过改进路由算法降低WSN网络的能耗。首先简单分析了基于分层结构的路由算法, 然后重点分析了LEACH算法, 对其中关于簇头选择上的问题提出改进算法, 再针对传感器节点之间的通信模式提出改进方案, 最后在Matlab进行了仿真验证。
1 路由协议
1.1 传统路由协议
经过多年的研究发展人们已经开发出了多种WSN路由协议, 传统路由协议的代表是洪泛法, 这种简单的方法存在很多的问题, 比如信息爆炸和信息重叠, 由于这些原因这种简单的方法也很难被应用于实践[3]。现在人们应用较多的路由协议基本可以分为三大类:平面路由协议, 分层路由协议和基于地理位置的路由协议[4]。平面路由协议的代表为SPIN, DD, Rumor, 基于地理位置的路由协议则以GEAR和GEM为代表。
1.2 基于分层结构的路由协议
在实践中, 人们应用更多的是分层的WSN路由协议, 在这项路由协议中通过簇的划分, 使整个系统的能量消耗得以降低, 并且使能耗分布也更加均匀, 而由于减少了参与运算的传感器节点数, 整个通信的开销也降低了。并且基于簇形成的策略网络, 拓扑结构的变化对于网络的影响也会降低, 使网络整体变得更加稳定。在目前的分层路由算法中, 低功耗自适应集簇分层型协议LEACH (Low Energy Adaptive Clustering Hierarchy) 是最早最成熟的算法, 也是几乎所有分层路由协议的基础。
2 LEACH算法改进
LEACH在执行过程中不停的循环执行簇的重构过程, 一个簇的重构过程可以理解为一个回合, 每个回合可以分为建立阶段和数据传输的稳定阶段。簇的建立过程可分成四个阶段:簇头节点的选择、簇头节点的广播、簇头节点的建立和调度机制的生成[5]。在簇头建立的过程中, 优化簇头节点的选择是重要也是最能有效延长WSN生命周期的手段。
在簇头的选择中, LEACH以轮为周期工作, 在每一轮, 所有的节点都会生成一个介于0到1范围内的随机数, 然后将随机数跟阈值T (n) 做比较[6]:
式中的P是簇头节点占整个节点的比率, r代表轮数, G是在最后的1/P轮中没有成为簇头的节点的集合。如果随机数小于T (n) , 这个节点则成为一个簇头, 产生簇头之后其他的节点会根据距离关系选择加入最近的簇, 在形成的簇内, 非簇头节点将会向簇头发送信息, 由簇头进行数据融合再与基站通信, 到此就完成了簇头的选择过程。对比与其他的路由协议, LEACH在很大程度上提高了效率, 但是它依旧存在一些问题, 在簇头的选择过程中, 由于选择的随机性, 使得簇头节点的分布不均匀, 整个系统的能耗就不均匀, 而剩余能量大的节点不能获得比低能节点更高的概率来成为一个簇头, 这样将会大大地缩短网络的生命周期。所以需要修改原先的阈值T (n) 为[7]:
式中的Ec代表节点的剩余能量, Ei代表节点的初始能量。很明显通过添加这个比值, 高能的节点将获得更高的成为簇头的概率, 而Phead在这里也不再是一个定值, 而是一个随着节点距基站距离变化的值 (通过two-ray模型计算得出) , 具体关系为:
选择了簇头之后, 就进入通信阶段, 在传统的LEACH算法中传感器节点的通信通常为单跳, 这意味着簇头只能直接与基站进行通信, 这就带来了很多问题, 且不说当网络的规模很大时, 节点的传输能力不能达到那样的距离, 就算是可以做到也需要消耗大量的能量, 所以必须要修改路由算法的单跳为多跳, 相比于单跳, 多跳可以降低节点上能量的消耗。在选择了簇头之后, 各个传感器节点会根据地理位置关系选择加入最近的簇 (在这里设定距离基站最近的节点会自动成为簇头) 以TDMA形式完成簇内的通信。
在之后的通信阶段就需要引入一个新的通信模式———基于栅格的多跳模式[8]。这种算法的基本思想是将整个系统区域划分为一个一个的栅格, 并对这些栅格进行标号, 每个栅格内部都有一些传感器节点。现在设定一个通信机制, 先计算节点的数目尽量保证一个栅格内由LEACH算法选出的簇头数目大于等于1, 然后根据剩余能量大小选出一个剩余能量大的传感器节点作为此栅格的簇头, 接着根据地理位置关系和邻居栅格簇头剩余能量大小选择中继来进行多跳传输。实现多跳的方式有很多, 选择栅格的方式可以在网络内部运算上节省大量的开支, 更加便于应用于实践。在实际的操作中可根据经验设定栅格数, 或设定一个最大栅格数, 如果栅格内不存在传感器节点, 再逐步缩小栅格数直至每个栅格内都有传感器节点存在。实现多跳的过程如图1所示, 例如基站位于3号栅格, 则周围2、5、6号栅格成为第一圈栅格, 栅格内能量最大的簇头先进行数据融合再与基站进行通信, 之后的1、4、7、8、9便成为第二圈栅格, 第二圈栅格要与基站通信必须通过第一圈, 且下一跳的栅格为所有邻区栅格内距离基站最近的栅格, 以此类推, 直至与基站通信。
3 算法仿真
在M为100 m的范围内随机放置100个节点, 每个节点的原始能量为0.5 J, 仿真原LEACH算法的p为0.08, 其他功耗数据见表1[9]。
图2表示原LEACH的仿真结果, 以半数节点的消亡轮数和全部节点消亡轮数为参考, 大约在500轮左右有半数的节点耗尽了能量, 而在1 000轮之前几乎所有的节点已经耗尽能量。
图3表示改进簇头选择方式后的仿真结果, 可以看出通过对阈值的改变, 簇头的分布和能耗的分布更加均匀, 大约在1 200轮左右耗尽了一半的节点能量, 而全部节点消亡轮数也达到了2 500轮以上, 比原LEACH提高了1.5倍的网络生存时间。
图4表示基于栅格多跳的改进后算法仿真结果, 这里设定最大栅格数为16, 如果相邻栅格内没有已生成簇头, 则自动减小栅格数直到每个栅格内至少包含一个簇头。由于在图3的基础上添加了基于栅格的多跳之后半数节点消亡轮数增加到了约1 800轮, 全部节点消亡轮数更是达到了5 000轮左右, 相比于单跳提高了近1倍的网络生存时间。
4 结论
改进后的LEACH算法在原算法基础上使得剩余能量高且距离基站近的传感器节点更容易成为一个簇头, 从而使得整个网络能耗分布更加均匀, 提高了网络生存时间。在实际的传感网中由于网络较大造成了过多的网络通信能耗, 将节点通信方式从单跳改为多跳更加节能, 使网络具有更好的扩展性, 使得该算法得以应用在更大的网络里。而基于栅格的多跳相比于其他多跳方式在网络内部运算上开销较小, 更容易应用于实践当中。
摘要：为了延长无线传感网络 (Wireless Sensor Network) 的生命周期, 提出一种基于分层结构的WSN路由算法改进。在著名的LEACH算法基础上, 提出其中关于簇头选择所存在的问题, 将原算法中的簇头节点占比p变为一个随节点与基站距离变化的动态比率 (通过two-ray模型计算得出) , 并通过参考节点剩余能量与原始能量比值优化了簇头选择的阈值;接着修改了路由算法的单跳为多跳, 并且以基于虚拟栅格的路由算法得以实现, 从而使得整个改进算法得以在更大的网络里应用。
关键词：WSN路由算法,分层结构,LEACH,多跳,虚拟栅格
参考文献
[1]尹湘源.无线传感器网络低能耗分簇路由算法关键技术研究[D].上海:华东理工大学, 2014.
[2]尚兴宏.无线传感器网络若干关键技术的研究[D].南京:南京理工大学, 2013.
[3]施家煌, 赵成林.无线传感器网络 (WSN) 路由协议的分析与比较[A].中国通信学会, 2008通信理论与技术新发展——第十三届全国青年通信学术会议论文集 (下) [C].中国通信学会, 2008:4.
[4]赵强利, 蒋艳凰, 徐明.无线传感器网络路由协议的分析与比较[J].计算机科学, 2009 (2) :35-41.
[5]郑顾平, 朱维.基于LEACH协议的安全性改进与建模分析[J].软件导刊, 2014 (7) :131-133.
[6]胡艳华, 张建军.LEACH协议的簇头多跳 (LEACH-M) 改进算法[J].计算机工程与应用, 2009 (34) :107-109.
[7]Xu Jia, Jin Ning, Lou Xizhong, et al.2012 9th Improvement of LEACH Protocol for WSN[C].International Conference on Fuzzy Systems and Knowledge Discovery (FSKD 2012) , 2012.
[8]云春峰, 王培康.基于虚拟栅格的无线传感器网络路由协议[J].计算机应用与软件, 2009 (9) :200-202+218.
分层算法 第3篇
阈值分割法是一种简单有效的图像分割方法, 其特点是计算简单, 速度较快, 其已成为图像分割领域中广泛被采用的方法。但阈值分割法的研究结果表明 (1) , 在实际图像中, 由于噪声干扰等因素的影响, 图像灰度直方图分布不一定出现明显的峰和谷, 当信噪比较低时, 仅利用直方图得到的阈值分割并不能使图像分割得到满意的结果。二维最大熵图像分割正是基于此点, 建立既能反映点灰度分布信息, 又能体现点灰度和其邻域空间度信息的灰度-均值二维直方图, 得到的最佳阈值是能使目标和背景包含最大信息 (即最大熵) 的二维向量, 以此阈值来区分目标背景, 能大大提高一维阈值分割算法的抗噪能力。
分层遗传算法是一种改进的遗传算法, 本文将其引入到二维最大熵图像分割中, 可以加快收敛速度, 减少计算量, 有效避免陷入局部最优解的情况。
2、二维最大熵图像分割
将信息论中Shannon熵概念应用于图像分割, 其依据是使得图像中目标与背景分布的信息量最大, 即通过测量二维图像灰度直方图的熵, 找出最佳阈值。
设图像的大小为MXN, 灰度级为L, Ni, j为图像中点灰度为i, 领域sXs灰度均值为j的像素的个数, pi, j为点灰度-领域灰度均值对 (I, j) 的概率:
图1为其的XOY平面图, 其中f (x, y) 为点灰度, g (x, y) 为邻域均值。阈值 (s, t) 将图像分成A、B、C、D四个区域, 沿对角线分布的A区和B区分别代表目标和背景, 远离对角线的C区和D区代表边界和噪声, 由于C区和D区包含关于噪声和边缘信息, 概率很小, 所以在计算时将其忽略不计。
其中目标所占面积为
背景所占面积为
则与每个分布有关的熵分别为:
图像的总熵为:H (s, t) =HA (s, t) +HB (s, t) 公式 (1)
根据信息论中最大熵原理, 最佳阈值向量满足:
3、基于分层遗传算法的二维最大熵图像分割
遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型, 由Michigan大学的J.Holland教授于1975年首先提出。它将"适者生存"的进化理论引入串结构, 并且在串之间进行有组织但有随机的信息交换。通过遗传操作, 使优良品质被不断保留、组合, 从而不断产生出更佳的个体。子代个体中包含父代个体的大量信息, 并在总体熵胜过父代个体, 从而使种群向前进化发展, 即不断接近最优解 (2) 。
分层遗传算法模拟生物进化过程中的基因隔离和基因迁移, 将一个大的种群分为若干子种群进行低层遗传算法, 多个低层遗传算法中的每一个在经过一段时间后均可以获得位于个体串上的一些特定位置的优良模式, 再通过高层遗传算法, 利用该算法可以增大搜索范围, 加快收敛速度, 较好地客服标准遗传算法收敛速度慢, 易于陷入局部最优解的缺点。流程图如图2。
其算法步骤为:
(1) 低层遗传过程
a) 编码与解码:采用16位二进制码串表示染色体, 前8位表示点灰度阈值s, 后8位表示领域灰度均值阈值t, 随机产生4个种群;
b) 种群规模:种群规模15, 最大繁殖代数30;
c) 适应度函数:将公式 (1) 作为适应度函数;
d) 选择:选择转轮法作为选择方法。它是一种正比选择策略, 能够根据与适应度值成正比的概率选出新的种群。
e) 交叉:采用双点交叉, 两个交叉点分别位于前8位和后8位。子种群1-4交叉概率为0.7
f) 变异:采用取反变异算子, 即将0变成1, 1变成0.子种群1-4的变异概率分别设置为, 0.006, 0.007, 0.008, 0009。
g) 终止条件:在每个子种群运行各自遗传算法到最大代数后, 将其结果种群记录在R[1…4, 1…15]中, 同时将平均适应度值记录到数组A[1…4]中。
(2) 高层遗传过程。高层遗传算法与普通遗传算法的操作相类似, 也可分成下面三个步骤:
a) 选择:基于数组A[1…4], 即4个遗传算法的平均适应度值, 采用轮盘赌选择机制, 对数组R代表的结果种群进行选择操作, 一些结果种群由于它们的平均适应度值高而被复制多次;另一些结果种群由于它们的种群平均适应度值低而被淘汰。
b) 交叉:如果R[I, 1…15]和R[j, 1…15]被随机地匹配到一起, 而且从位置x进行交叉 (1≤I, j≤4:1≤x≤14) , 则R[I, x+1, …15]和R[j, x+1, …15]相互交换相应的部分。这一步骤相当与交换GAi和GAj中结果种群的n-x个个体。
c) 变异:以极小概率0.004将少量的随机生成的新个体替换R[1…4, 1…15]中随机抽取的个体。
至此, 高层遗传算法的第一轮运行结束。4个遗传算法GA可以从相应于新的R[1…4, 1…15]种群继续各自的操作。在4个GA再次运行到一定代数后, 再次更新数组R[1…4, 1…15]和A[1…4], 并开始高层遗传算法的第二轮运行。如此继续循环操作, 直至得到满意的结果。
4、实验
图3为标准256X256的Lena图像, 分别将标准遗传算法 (算法1) 和分层遗传算法 (算法2) 应用于二维最大熵图像分割算法对图3进行图像分割。算法1的参数设置为:种群大小为30、遗传代数50、交叉概率为0.8、变异概率0.05;算法2的参数设置如第3节。
图4、图5分别为利用算法1、算法2分割出的效果图, 表1为10次运用该算法程序所得的平均阈值和平均运行时间。可以看出这两种算法分割效果相近, 这两种算法均考虑了灰度点和邻域平均灰度信息, 分割出来的图像比较细致, 有效地排除了噪声的干扰。从分割处理时间来看, 本文算法运行时间更短, 提高了运算速度。
5 结论
二维最大熵图像分割综合运用点灰度和区域灰度信息, 使图像分割抗噪性更强, 精确度更高。分层遗传算法是一种并行优化算法, 全局搜索能力强, 据有较强的寻优能力, 通过实验证明, 将其引入到二维最大熵图像分割中, 大大缩短了寻找阈值的时间, 提高了运算速度, 具有较强的稳定性和较好的分割效果。
摘要：基于二维最大熵的图像分割算法充分考虑了点灰度和邻域灰度均值, 较好地克服了图像中噪声带来的影响, 将分层遗传算法引入到此图像分割算法中, 加快了阈值搜索的收敛进度, 大大提高了计算速度, 有效地避免了局部最优解的情况, 是一种实用有效的图像分割算法。
关键词：二维最大熵,分层遗传算法,图像分割
参考文献
[1].Lee S U.chung S Y.A comparntive performance study of several global thresholding techniques for segmentation.Computer Vision, Graphics andImage Processing.1990, 52:171-190
[2].王小平, 曹立明.遗传算法-理论、应用与软件实现, 2002.1, 西安交通大学出版社
[3].冈萨雷斯.数字图像处理, 2003.3, 电子工业出版社
[4].郭明山, 刘秉瀚.基于混沌遗传算法的二维最大熵图像分割, 2008.8, 计算机技术与发展
分层算法 第4篇
在有关时间-费用的优化问题已经有了大量的研究,且已被学者证明该优化问题是一个NP-Hard问题[4]。Buyya等[5,6]基于不同deadline/budget约束提出求解独立任务调度的启发式算法。文献[7]对截止期约束进行分解求解策略DTL。将截止期分解成为各层的截止期。文献[8]针对其不足提出了逆向分层算法(DBL),DBL算法使得工作流的执行费用有了大幅度的降低。DBL算法对当全局截止期大于逆向分层最小完成时间(δn>BLmin)时而产生逆向分层浮差(Tws),在各层上进行分配。在这个过程中产生了大量的时间碎片[9],阻碍了工作流执行费用的近一步优化。
本文在DBL(Deadline Bottom Level)的算法的基础之上,提出一种改进算法DBL-LC(Deadline Bottom Level-Lower Cost)。改进算法对δn>BLmin时所产生的逆向分层浮差(Tws=δn-BLmin),根据各层的层扩展时间LETi(Level extend time)进行重新合理分配。在时间碎片[9]方面,改进算法在内容上进行了丰富,将时间碎片分为任务时间碎片(STt)与流时间碎片(STf)。改进算法(DBL-LC)凭借减少流时间碎片(STf)进一步优化工作流执行费用。实验证明,在相同的截止(δn),DBL-LC算法在DBL算法的基础上,使得工作流的执行费用平均降低了14.52%。
1 DBL算法的描述
网格中的大型任务往往可以由许多小规模的子任务协同来完成。子任务及子任务间的制约与依赖关系可以模型化为一个工作流。在有向无环图记作G={V,E}中,V表示所有子任务;E是有向边集合,表示子任务间的制约与依赖关系。假设i,j是子任务编号,当i
在给定的时间限制下,对坌i∈V都有一组可以完成该子任务的服务,这一组服务称为i的服务集,记为P(i)。这个集中的元素个数记为L(i);Sik表示能完成子任务i的第k个服务;(cik,tik)表示子任务i在服务Sik的执行费用和执行时间,则表1给出了图1中各子任务的服务集实例。
用户给出工作流截止期δn后,希望在截止期的限制下其任务以最小的费用被执行完成。如果每个子任务在其的服务集中都选择最小费用执行时,则工作流的执行费用即为最小。
在关键路径上的任意子任务都选择最快的服务,其总的执行时间称为工作流下界完成时间(LCT)。并依据关键路径法计算子任务i的最早开始时间ESi,用βi表示子任务i的所允许的最早开始时间,δi表示子任务i的最晚完成时间。形式表示为[8]:
DBL算法是通过将工作流截止时间δn分解为各个子任务的截止时间δi,子任务的开始时间由其前驱子任务来确定。在时间区间[βi,δi]约束下子任务选择最小费用的服务,其时间约束为[8]:
在有向图DAG中,将子任务i到出口子任务n的最长路径定义为逆向深度BD(i)。再将深度值相同的子任务划为一组,这就构成对DAG逆向分层的BL(i)分组[8]。
第k组所包含的子任务为
当每个子任务以最快服务执行时,则BL分组的截止时间与子任务的βi和δi按下式计算得出[8]。
当δn≥BLmin时,DBL算法对Tws采用在各层平均分配的方法从而产生各层的层逆向分差(TLS)。TLS(层浮差)=Tws/(GL-2)(虚子任务除外),公式如下[8]。
DBL算法的基本思想是首先初始化各子任务并查找到相应的资源集,计算出LCT,划分BL分组和求出BLmin。然后根据用户截止期(δn≥LCT)的大小来选择确定子任务时间区间[βi,δi]的方法:当δn
2 改进算法DBL-LC(Deadline Bottom Level-Lower Cost)
DBL算法将Tws平均分配到BLi各层中,而实际每个子任务的服务集所提供的服务的个数不同,而且每个服务的执行时间也不同。考虑工作流时间费用的约束时,应当将有限的逆向分层浮差(Tws)进行合理的分配使各层最大限度的降低费用,从而使得全局费用得到进一步的优化。
定义1:在BLmin条件下,子任务i所选取的服务k称为子任务i的标准服务Siks(standard),时间属性值称为标准时间,记为Tiks(standard);费用属性值称为标准费用,记为Ciks(standard)。
定义2:在子任务i的服务集中,时间属性最大者称为子任务i最大执行时间,记为Tikm(max),则该服务对应的费用属性称为子任务i最小费用,记为Cikm(min)(服务的时间属性值与费用属性值成反比,即服务时间越长其费用值越小)。
定义3:在BLi层中,第层子任务集中各子任务的Tikm与各子任务的Tiks的差值的最大者称为第i层的层扩展时间,记为LETi(Level extend time)。
公式为:
定义4:在BLi层中,第i层子任务集中各子任务的标准费用(Ciks)与其最小费用(Cikm)的差值总和与该层的层扩展时间的比值称为BLi层中第i层的单位时间费用降低值,记为Ri。
公式为:
定义5:工作流中每个子任务都选取服务集中执行时间最短的服务,则在DBL算法下可得出一个最小执行费用的预测执行时间,记为TDBL;在DBL-LC算法下可得出一个工作流最小执行费用的预测执行时间,记为TDBL-LC。
定义6:在算法中(DBL与DBL-LC),某个子任务执行完至它的任一后继子任务开始执行的时间区间称为任务时间碎片,记为STt(Shattering Time of Task)。
如图1中的子任务14有多个前驱子任务(5、8、10、11),在子任务5执行完成后不能立即执行子任务14,这一时间区间即为任务时间碎片。
定义7:在算法中(DBL与DBL-LC),依据算法工作流完成时间小于工作流截止期(此处的工作流截止期小于工作流最小费用的预测完成时间)的那部分时间区间称为流时间碎片,记为STf(Shattering Time Of Flow)。
假定用户给定的截止期为100,在这个时间约束下要使得工作流的执行费用最小。算法是尽最大努力使用这100个时间单位,但在实际执行时却只使用了90个时间单位(些时工作流的执行费用并不是最小费用),那么剩余的10个时间单位即为流时间碎片。
改进算法(DBL-LC)就是针对DBL算法中产生的大量流时间碎片(STf)而做改进。改进算法(DBL-LC)通过减少流时间碎片,使得工作流的执行费用进一步得到优化。
DBL-LC算法在对Tws分配上抛弃了DBL算法的平均分配的方法,而是按照各层的单位时间费用降低值(Ri)的大小来确定其获得分配时间的优先级,然后根据其优先级来确定是否给该层分配时间。单位时间费用降低值(Ri)越大的层被赋予越高的优先级,使其优先从Tws中获得该层的层扩展时间(LETi)的时间需求。当高优先级的层获得了时间分配后,再给具有低优先级的层分配时间,依次类推直至Tws的剩余时间小于任一未获时间分配的层护展时间(LETi)或各层都已获得时间分配为止。(当分配至第i层时,Tws或Tws的剩余时间小于该层的LETi时,则跳过该层给相邻级别低的层分配时间。当Rj=Rj+1时,层扩展时间(LETi)大者具有较高优先级)。从而得到一个按Ri值降序的序列。
公式(6)改进为公式(9)
其中,XR(i)为布尔变量,其值为1表示BLi层获得了时间分配,否则为0;
如果在BLi层中的各层都获得了各自层的层扩展时间,则工作流的完成时间即为TDBL-LC。
改进算法(DBL-LC):
1)初始化及各子任务的服务集p(i)i∈V;
2)计算求出LCT(最小完成时间);
3)求出各子任务的逆向深度,并划分BL分组;
4)计算出最小完成时间BLmin及工作流的最小费用完成时间TDBL-LC;
5)在截止期有效范围内(TDBL-LC≥δn≥LCT)输入截止期;
6)当LCTδn
7)当δn≥BLmin时,根据公式(7)求出各层的层扩展时间(LETi);
8)求出各层的Ri,而后按Ri值降序生成一个序列OrderBye(Ri)={RmRn};
9)将逆向分层浮差(Tws)按OrderBye(Ri)依次分配给各层,并得到各层相应的布尔变量XR(i);
10)用公式(9)确定任务的βi和δi;
11)获取就绪子任务队列RL;
12)若RL不空,子任务在约束(2)下从其服务集中选择费用最小服务;否则转步14);
13)子任务在分配资源上执行;
14)等待子任务完成事件;
15)查询是否有还子任务未被调度,有则转步11),否则转步16);
16)汇总各子任务的费用,求出工作流所需总费用Ctotal;
17)输出结果;
3 实例与仿真实验分析
以图1给出的工作流为例。表2是对工作流进行了BL分组,计算出R(i)与XR(i)LETi。
其中,BLi(层子任务集)由公式(3)和公式(4)得出。LETi由DBL-LC算法的定义1,2,3及公式(7)得出。由公式(8)求出各层的Ri值。依据Ri值得出各层获得Tws分配时间的优先级顺序:OrderBy(Ri)={R6,R3,R2,R1,R4,R7,R5}。
由DBL-LC(等同DBL)算法得到的DBLmin=62,逆向分层浮差Tws=38,按优先级排序并得出各层的布尔变量(在本例中,除XR(5)=0外,其余均为1),最后得到XR(i)LETi。
分别计算出DBL与DBL-LC的执行时间与执行费用及其它相关参数,如表3所示。
DBL-LC算法执行中各子任务的开始时间、截止时间及服务集中的服务选择如表4所示。
用DBL-LC算法对实例进行求解中,对用户截止期(δn)使用的更加充分。大大减少了流时间碎片(STf)。在DBL算法中有17个时间单位的流时间碎片,而在DBL-LC算法中流时间碎片减少为1个时间单位。
本例中由于R5(子任务7)的优先级最小,所以子任务7没有获得Tws的时间分配,但在相同的截止期(δn=100)下,工作流执行费用却进一步的降低,Ctotal=448,费用降低率为15.947%。
如果要使整个工作流中的各个子任务都以最低费用执行,则总执行时间为工作流的最小费用执行时间。如果为了使工作流以最小费用的执行,则在不同的算法下,产生预期最低费用的执行时间不同,本例在DBL算法下TDBL=167(62+15*7),才能使得工作流以最小费用被执行,而在DBL-LC算法下TDBL-LC=104(即再满足子任务7的时间需求)。
为了验证改进算法(DBL-LC)的有效性,本文对改进算法进行了实验仿真和性能分析。实验中工作流采用不同的子任务数随机生成有向图进行模拟,服务集中提供服务的时间属性与费用属性成反比。截止期以BLmin为下界,TDBL-LC为上界,在这之间随机取十个值作为截止期,最后求出费用平均值。
从表5列出的数据所示,在相同的δn下DBL-LC算法比DBL算法在费用上有了进一步的降低,其平均降低率为14.52%。
用户给定的工作流有效截止期(δn)影响着工作流实际执行费用。在一般情况下,截止期越大则其工作流的费用也就越小,随着有效截止期的变化对不同的算法产生不同的影响。图2是含有200个子任务的工作流实例,其显示了DBL-LC算法与DBL算法随有效截止期的变化其费用相应发生变化的情况。
从图2可以看出,当有效截止期大于BLmin时,随着截止期(δn)的增大,DBL与DBL-LC算法的执行费用都相应的降低,但在相同的δn下,DBL-LC算法的费用降低的幅度大于DBL算法。尤其是在δn≥BLmin的初始阶段,DBL-LC算法的费用降低幅度明显优于DBL算法,随后费用降低幅度逐惭减小(降低幅度仍然优于DBL)。其原因是当δn≥BLmin时DBL-LC算法是按其单位时间费用降低值(Ri)的优先级来分配Tws,Ri值大的层优先获得时间分配。
5 结束语
基于逆向分层算法(DBL)在对逆向分层浮差(Tws)分配的不足之处,提出了层的扩展时间(LETi)概念,并依据其各层具有的不同优先级来确定那些层在Tws中获得时间分配。由此而产生了一种改进算法(DBL-LC),改进算法使得在相同的截止期(δn)下,其执行费用较DBL算法有了进一步的降低。
然而,DBL-LC算法仍有许多不足之处。如在减少大量流时间碎片的同时没有减少任务时间碎片,甚至还增大了个别子任务的任务时间碎片。又如在实际工作中,服务池中服务的可靠度也应作为一个重要的参数在本算法中进行研究。
(n=200,BLmin=359,TDBL=769,TDBL-LC=663)
参考文献
[1]Foster I,Kesselman C,Tuecke S.The Anatomy of the Grid:Enabling Scal-able Virtual Organizations[J].International J.Supercomputer Application,2001,15(3):200-222.
[2]Foster I,Kesselman C.The Grid:Blueprint for a Future Computing Infras-tructure[M].USA:Morgan Kaufmann Publishers,1999.
[3]Foster I,Kesselman C,Nick J M,et al.Grid service for distributed system integration[J].IEEE Computer,2002,35(6):37-46.
[4]Blythe J,jain S,Deelman E,et al.Task scheduling strategies for workflow-based applications in grids//proceedings of the IEEE International Sym-posium on Cluster Computing and Grid[M].Cardiff,Wales,UK,2005:759-767
[5]Buyya R,Abramson D,Giddy J,et al.Economic models for resource man-agement and scheduling in grid computing[J].Concurrency and Computa-tion:Practice and Experience Journal(Special Issue on Grid Computing Environments),2002,14(13-15):1507-1542.
[6]Abramson D,Buyya R,Giddy J.A computational economy for grid comput-ing and its Implementation in the Nimrod-G resource broker[J].Future Gendration Computer Systems(FGCS)Journal,2002,18(8):1061-1074.
[7]Yu J,Buyya R,Tham C K.Cost-based Scheduling of work-flow applications on utility grids//Proceedings of the1st IEEE International Conference on e-Sceence and Grid Computing[M].Melbourne,Australia:IEEE press,2005:140-147.
[8]苑迎春,李小平,王茜,等.基于逆向分层的网格工作流调度算法[J].计算机学报,2008(2).
基于分层思想的配电网负荷转供算法 第5篇
恢复供电的原则是在配电网发生故障后,尽可能迅速地通过网络结构调整。在保证系统不产生安全越限的条件下,多且快地对非故障失电负荷恢复供电[1]。这对保证配电网安全经济运行有着重要的意义。
典型的配电网负荷转供算法包含以下几类:(1)使用遗传算法来进行负荷转供计算[2]。(2)以启发式搜索为基础,并经数值计算确定可行解或优选解来寻找恢复方案 [3,4,5,6]。(3)使用模糊数学方法进行模糊规划来寻找优化的供电恢复方案[7]。(4)专家系统方法。
为了保证配电网中没有环网,即保持辐射状,在解决该问题发现了开关对现象,即合上一个联络开关的同时需要打开一个分段开关[8]。文献[9]利用非故障停电区网络保持辐射状的特点,把复杂的开关对组合优化问题转化为以联络开关为中心的待恢复树切割问题,在考虑电网安全运行的约束条件下,求出可行解的同时保持了电网辐射状[9]。但该算法也有自身的局限性,对网络拓扑依赖性较大,且若联络开关过多,会影响整体效率。
本文的算法将分层供电树思想和分离计算方法同时引入到恢复树切割算法中,然后根据故障信息,利用恢复树思想对失电区进行供电恢复方案计算和检验,最终给出有效方案。
1问题的模型
1.1相关指标定义
a.分段开关:首端和末端均位于带(停)电区的常闭开关;
b.联络开关:连接停电区和带电区域的常开开关;
c.支持馈线:可以通过联络开关对失电区域进行供电恢复的馈线(图1中F2,F3都是支持馈线);
d负荷裕量:联络开关的负荷裕量是指该联络开关相连的支持馈线的额定负荷与当时的实际负荷之间的差额;
e备用容量:联络开关的备用容量计算方法如下,假设某个联络开关i所在的供电路径为Pi,在Pi上有n个电力设备(包括变压器、馈线和分段开关),联络开关的备用容量为:Im,si=min(I1,max-I1,cur,I2.max-I2,cur,In,max-In,cur)[10]。
f 供电树与待恢复树: 由于配电网开环运行的特点,进行网络拓扑分析时,可以把每个电源供电环节看成是以电源馈线为根的树状结构。非故障失电区在没有转移负荷之前还是原来的树状结构,这就是待恢复树,如图2所示。
1.2目标与约束
负荷转供的主要目标是安全;高效;低成本。
我国配电网经改造后一般形成闭环设计, 开环运行结构。为保网络呈辐射状,在恢复供电时,采用从联络开关出发对失电区进行企切割搜索,能够保证电网的辐射状接线。
所以本算法的总体目标按优先级排序如下:①尽可能多地恢复负荷供电; ②没有过载元件;③恢复后的系统网损尽量小;④开关操作次数尽量少。可给出多个结果供优选。
1.3潮流计算策略
供电恢复方案是否满足网络运行约束必须由潮流计算验证,因此,配电网供电恢复系统的执行效率除了与采用的搜索策略有关外,还与潮流计算密切相关[11]。本文中采用适合配电网特点的前推回代算法[12]。
2算法描述
本算法流程图如图3。
根据流程图可以看出,该算法由两部分组成,第一部分是离线计算部分,第二部分是在线恢复部分。这样可以在离线部分做好前期的计算准备,减少在线计算量和计算时间。
2.1分层供电树的处理(离线计算部分)
我国配电网正常都是闭环设计,开环运行结构。拓扑结构上可以看成是以电源点为根节点树状结构,这些树通过树枝尖端的联络开关相连构成了配电网的复杂结构。所以配电网正常运行时,可以分解成多个以电源点为跟节点的分层供电树。
取某一供电树分析,以电源端为跟节点,正常运行时情况下供电半径最长的馈线为树干,其余馈线为树枝。树枝端点处于断开状态的为联络开关。然后利用深度优先搜索方法对供电树树干进行分层,按每个开关到跟节点的电气距离远近进行层号排序[13],并计算每层所带的负荷,与本层相连的树枝视为同一层(包括联络开关)。
然后根据前面公式(3)计算每个联络开关的电气距离∑rj。
2.2失电区供电恢复算法(在线计算部分)
2.2.1 失电区处理
根据故障信息,对失电区进行处理。如果只有一个故障点,则根据因故障而打开的分段开关位置,取出相应的供电树的非故障失电区,计算出该失电区的总负荷量Ilost,并根据前面给出的联络开关备用容量公式计算与该失电区相连的各联络开关的备用容量。
由于该区需要通过树枝末端的联络开关进行供电恢复,为保证供电恢复后网络任呈辐射状,该区必须断开相应个数的分段开关,而有些开关断开后将导致部分符合不能恢复,这类开关称为不可开断开关。
若有多个失电区,先按照重要负载的占有比例将失电区进行排序,再对排在前面的失电区进行上面的处理。
2.2.2 供电恢复计算
进行供电恢复计算部分,首先进行判断能否自馈线恢复,如果可以则进行自馈线恢复供电,否则执行下面的恢复计算。故障开关上游的负荷仍然由原电源进行供电,而对故障开关下游的失电区由有备用容量的联络开关进行分区转带。具体步骤如下:
1)判断待恢复负荷总量是否小于联络开关备用容量之和,如果Ilost<∑Im,si,进行下面供电恢复,否则进入步骤5)。
2)将含有联络开关层的该层负荷总量Ilost,i与联络开关容量Im,si进行比较,将Im,si<Ilost,i的层号放入集合C,其余有备用容量的联络开关放入集合O中。
3)以集合C中的联络开关先对该层树枝进行供电恢复,并将剩余的待恢复树取出。若C为空则直接进入步骤4。
4)利用集合O中的联络开关对剩余失电区进行供电恢复。
(a)以某一联络开关i为起始点逐层向失电区进行恢复搜索,假设搜索到第k层,其前后后面开关分别为S(k-1)-(k)和S(k)-(k+1)。判断第k层后面开关S(k)-(k+1)是否为可开断开关。
(b)如果S(k)-(k+1)为可开断开关,设第k层的总负荷为P+jQ或者为Ilost,k。经潮流计算(用前推回代方法计算)得到电压为Vk,其近视电流为Ik=(P+jQ)/Vk判断该条供电路径上电流电压是否越限(假设此时已转移的负荷的总的电流为Iload,判断Im,si>Iload+Ik;|Vk-1|5%)。如果不越限则继续向下搜索供电,否则转入(d)。
(c)如果S(k)-(k+1)为可不开断开关,则将第k层以后的各层负荷累加至第k层,总负荷为∑[(P+jQ)]。判断该供电路径上电流电压是否越限。如果不越限,则换方向搜索。否则转入(d)。
(d)打开第k层前面的开关S(k-1)-(k),本次恢复切割结束。
(e)若本失电区负荷全部转移,本失电区供电恢复结束,否则转入5)。
5)若集合O中联络开关全部参与供电恢复时仍然有负荷未被转移,则考虑向二级馈线先转移一部分负荷再进行恢复计算。
6)若全部搜索计算结束,发现仍然有负荷没有转移,则认为是不可转移的负荷。转移结束,最后计算本次转移的附加网损、开关操作次数和转移的负荷总量等指标。
集合O中联络开关不同的排序对应着本算法形成的不同的供电恢复策略,最后将这些策略,按照前面目标函数进行比较选择当前最合适的供电恢复策略。
3算例分析
本文先利用文献【6】中的算例进行计算分析该算法的可行性,然后再以某城市的配电网进行实测分析。
文献算例如图4所示。
根据算法思想,首先判断L4层L7层能否给本层树枝供电,发现都可以,而且还有余量。则将L4层,L7层和L9层的联络开关均放入集合O中,然后通过不同的次序对待恢复树进行恢复供电计算,结果如图5所示。
然后在根据不同的恢复策略计算各自增加的损耗,开关次数,供电恢复率等指标的综合比较来判断获取当前最合适的转供方案。
实测算例如图6所示。
图6中1到5号节点是电源母线,其余为负荷节点,假设3号母线故障,通过分段开关321隔离故障区,则红框内剩余部分为非故障失电区,根据本算法进行计算,最终得到以下3个优选方案如表2。
通过结果分析可以看出本文的方法与文献[8]的算法相比,有所改进,本文结合了分层供电树思想,将同一层上的负荷进行整体处理,且将整个计算过程分为离线计算和在线计算两部分,大大减少了在线计算量,提高了计算效率。
但是本文在最终结果的优选策略上只是以简单的优先级排序来确定,而实际上开关动作次数,网损,负荷转带率,用时等的优先程度往往视具体情况而定,使用怎样一个标准,怎么去综合考虑这些限制条件而最终得到更理想的效果还需进一步探讨研究。
4结语
(1)将分层供电树思想引进到负荷转供的恢复树切割算法中,降低了后期恢复树搜索空间和问题的复杂度。
(2)具体实现时将算法分为离线计算和在线计算两个部分,并利用负荷矩思想进行网损计算,减少了在线计算量,整体提高了转供算法的计算效率。
(3)利用待恢复树切割思想对失电区进行分区恢复,并加以改进,较以往的恢复树切割算法更为简洁和快速。
摘要：配电网供电恢复的主要目的是在保证支路不过载、电压不越限、电网呈辐射状这三个约束条件下以较少的开关操作尽可能多地恢复失电负荷,并尽量使网损最小。在分层供电树基础上,结合恢复切割思想,提出一种实时算法;该算法将整个计算过程分为离线和在线计算两个部分。首先在离线计算部分中做好相应的准备工作,即对系统进行拓扑分层,并计算一阶负荷矩,然后再根据故障信息进行在线计算。通过分层树的切割方法计算得出非故障失电区的负荷转带方案。最后根据各个方案的负荷转移量、开关操作次数和网损等指标进行方案的优选比较。通过研究和算例分析可以看出将整个算法过程分为离线和在线计算两个部分可以提高算法的在线计算效率,能有效地满足负荷转供的实时性。
分层算法 第6篇
在保证准确性前提下, 以相对较简单通用的方式将单载波的系统模型描述为:
其中:
随机相位模型的因子图后对随机相位模型的相邻相位之间的关系因子图进行分析计算, 有如下复杂的似然函数来估计相位偏移。
从算式 (2) 和 (3) 可看出, 对于这两种模型, 使用既有的NI算法处理相位估计, 每一次量化后的相位值都要求等量计算, 因此相位的量化阶数直接决定了算法的计算量, 而为减小量化噪声的影响, 量化阶数也不能过低。因此无论针对哪种模型, NI算法的精度与计算量都不可兼得。
2分层量化的相位估计NI算法
(3) 在缩小后的取值范围上, 再做一次量化步长小于上次粗量化步长的均匀细量化。
如果要获得更高精度的相位偏移估计, 必要时可以重复步骤 (1) ~ (2) , 从而进行多次迭代。在本文旨在说明原理, 只以一次分层量化的情况做举例说明。据上述过程执行的量化结果如图1所示。
图1中, 三角符号为实际的相位偏转值, 圆形符号为分层量化计算估计的结果。量化阶数如图, 第一次取值为10, 第二次取值为8。从上图对比结果可知, 第二次进行细量化之后, 与第一次粗量化的结果相比, 相位估计计算结果更加接近实际值。
3 分层量化 NI 算法的计算量
设第一次粗量化的阶数为N1, 其原始取值范围为R, 第二次细量化阶数为N2, 其取值范围为原始取值范围R的S倍, S<1。
因此, 在公式 (4) 成立的前提下, 只要保证量化阶数和取值范围的选取满足以下公式:
相位偏移估计计算量就可以得到有效降低。
4分层量化NI算法仿真对比
在MATLAB 6.5平台上, 利用数字基带系统的蒙特卡罗方法, 使用最小均方误差 (MSE) 曲线对原NI算法和分层量化的NI算法进行精度性能分析。利用随机数产生信源信号, 经QPSK调制后, 通过加性复高斯白噪声信道传输。接收端一次处理的数据长度L为10。仿真实验在WindowsXP系统下完成。
在恒定相位模型和随机相位模型下, 均采用以下分层方案进行仿真。
再将分层NI算法的MSE性能与既有NI算法进行对比:
在恒定相位模型下, 对两种不同的分层量化NI算法和与之等价的原NI算法进行了仿真, 得到如图2所示的三条MSE性能曲线。
由上图可见, 三种方案对应的MSE曲线基本重合, 即使用分层量化NI算法不会引入算法的精度性能损失;但是在原NI算法能够得到足够准确相位估计结果的前提下, 使用分层方式进行小范围量化, 也不会显著提升相位偏移估计的在精度性能。
在随机相位模型下, 仿真MSE性能曲线如图3所示。
由上图中的几条MSE曲线可以看出, 相对于原始NI算法, 分层量化NI算法的MSE有性能提高, 数值约2d B;而且, 细量化选取的S值越小, MSE性能越好。原因在于选取的S较小时, 仿真处理集中在较小的范围内完成, 可得到更准确的估计结果。
5 结语
结合上述计算量和精度分析, 以及MSE仿真结果来看, 分层量化NI算法是一种能在不损失算法精度性能的前提下减小计算量的方法, 在实际应用方面具有较高价值。
参考文献
[1]Lee D.Analysis of Jitter in Phase-locked Loops[J].IEEE Transactions on Circuits and Systems II:Analog and Digital Signal Processing.2002, Nov.vol49, no.11:704-711.
[2]Berrou C, Glavieux A, and Thitimajshima P.Near Shannon limit error-correcting coding and decoding:turbo codes[C].ICC 93, IEEE International Conference on Communications.1993.
[3]Loeliger H-A.An Introduction to Factor Graphs[J].IEEE Signal Processing Magzine.2004, Jan.:28-41.
分层算法 第7篇
LTE定位协议[1]中定义了3种定位方法:辅助全球导航卫星系统 (Assisted Global Navigation Satellite System, A-GNSS) 、增强型小区ID (Enhanced Cell ID, E-CID) 和可观测到达时间差 (Observed Time Difference of Arrival, OTDOA) 。OTDOA是LTE系统中使用最多的定位技术, 相比A-GNSS无需改动终端, 且较E-CID定位精度高。LTE协议规定, OTDOA技术中利用服务基站到终端的距离作为参考距离, 与其他基站的距离相减构成相应的双曲线模型实现终端定位。
Chan提出一种经典的OTDOA定位算法———Chan算法[2], 该算法在视距环境下定位精度高, 计算复杂度低, 但在非视距环境下, Chan算法定位精度将大大降低。为了消除NLOS误差的影响, Gentner C提出了基于粒子滤波器和卡尔曼滤波器的定位方法, 能实现对动态用户的跟踪和定位, 终端位置估计的均方根误差 (RMSE) 明显降低[3]。阎龙等提出一种适用于NLOS环境下的LTE终端迭代定位算法, 算法无需信道先验信息, 并可通过简单的分层细化来降低计算复杂度[4]。Yu K等提出了一种基于Taylor级数展开算法的二次线性规划算法来抑制NLOS误差的影响, 但计算复杂度较高[5]。周康磊等提出利用残差值对定位结果进行加权以降低NLOS误差的影响, 但计算复杂度高[6]。崔玮等提出利用高斯混合模型对含非视距误差的距离测量信息进行训练, 并结合残差加权算法来降低NLOS误差的影响[7]。赵军辉等将点到点的距离转化为点到线的距离估计, 但定位精度低[8]。Hara S等将摄动法引入终端定位算法中, 在NLOS环境下可有效提高定位精度, 但计算复杂度较高[9]。Kay S等基于最大似然估计算法提出一种新的最小加权二乘定位技术以消除NLOS误差带来的影响, 但OTDOA先验信息难以估计[10]。在实际中, OTDOA误差先验信息未知, 因此以上算法的应用存在局限性。为了解决这一问题, 本文提出一种抑制非视距误差的LTE终端分层协同定位算法。首先对非视距误差进行鉴别, 再根据残差加权法估计OTDOA值的先验信息, 从而改进Chan算法和Taylor级数展开算法, 将二者联合起来对LTE终端进行分层协同定位。在仿真中, 将两种经典定位算法与其改进算法以及本文所提出的分层协同定位算法进行了对比。仿真结果表明, HCLA算法能有效鉴别出含非视距误差传播的基站, 且其抑制非视距误差的能力强。
1 基于OTDOA的双曲线定位模型
设 (x, y) 为LTE终端坐标, (Xi, Yi) 为第i个基站的已知位置, LTE终端到各基站距离为
式中:i=1, 2, …, N, N为基站个数, 则
式中:c为电波传播速度;τi, 1为OTDOA测量值;Ri, 1为LTE终端到基站i和到服务基站1的距离差。将Ri2= (Ri, 1+R1) 2展开并化简得
式中:Ki=Xi2+Yi2, Xi, 1=Xi-X1, Yi, 1=Yi-Y1。
式 (2) 中由于NLOS误差的存在, 使得含非视距误差的基站所在双曲线远离真实位置, 形成一条新的双曲线, 如图1所示。
设基站3含NLOS误差, 其余基站均为LOS传播, 则由于非视距误差的影响, 将基站3所在双曲线H3推移至H3', 使得双曲线H2与H3'形成交点A, 以及H4与H3'形成交点B, 均远离LTE终端真实位置。因此, 有必要鉴别和抑制NLOS误差。
2 HCLA算法
2.1 非视距误差的鉴别
根据式 (2) , OTDOA残差[6]定义为
NLOS传播鉴别步骤如下:
1) 假设LTE终端和服务基站间为LOS传播, 其余基站中有一个是NLOS传播, 从N个基站中选取L (3≤L≤N) 个基站来定位, 共有CNL--11种组合 (每个组合必包括服务基站) ;
2) 每种基站组合分别计算出终端的估计位置作为其参考位置, 利用式 (4) 计算OTDOA的残差, 作为权值赋给组合内的每个基站;
3) 将每个基站从各个组合得到的权值相累加, 得到各基站的总权值;
4) 对每个基站的总权值排序, 总权值最大的基站即为含NLOS误差的基站。
2.2 非视距误差的抑制
2.2.1 残差加权算法
从式 (3) 中所构成的N-1个方程组中任选两个构成二元一次线性方程组, 求出每种基站组合下的LTE终端位置中间结果, 分别记为 (xk, yk) , k=1, 2, …, M, 其中M=C2N-1, 每种组合必含服务基站。如eNodB1, eNodeB2和eNodeB3组合, 得LTE终端位置 (x1, y1) 的矩阵表示形式
定义残差函数为
所有残差平方和为
对所有的 (xk, yk) 按下式加权得位置估计值
2.2.2 改进的Chan算法
在传统Chan算法中, OTDOA协方差矩阵通常假设为单位矩阵I, 对非视距误差没有抑制作用, 故在此提出将式 (8) 估计的初始值 (xRW, yRW) 代入式 (6) 得每个方程的残差, 令
其中, Q为OTDOA协方差矩阵。
从式 (3) 中求得的具有OTDOA测量噪声的误差矢量为
由Ri0=Ri0, 1+R10, 得噪声的误差矢量
式中:B=diag{R20, R30, …, RN0}, 噪声矢量n服从近似的正态分布, ⊙表示Schur乘积, 误差矢量ψ具有以下协方差矩阵
式中:Q为OTDOA协方差矩阵。假设Za中的各元素相互独立, 对Za进行第一次加权最小二乘 (WLS) 求解
Za的协方差矩阵为cov (Za) = (Ga0Tφ-1Ga0) -1。再利用x, y与R1的关系来改进定位估计, 重新构造误差矢量
ψ'的协方差矩阵为
式中:B'=diag{x0-X1, y0-Y1, R10}。
进行第二次WLS估计
最终LTE终端的定位计算结果为
在传统Chan算法中, 由于B未知, 利用Za= (GaTQ-1Ga) -1GaTQ-1h近似得到的Za来计算B所得出的结果误差很大, 故可利用式 (9) 给出的残差加权值函数矩阵来计算B。且式 (15) 中 (x0, y0) 可用初始值 (xRW, yRW) 近似代替, 这样便使Chan算法得到了改进。
2.2.3 改进的Taylor级数展开算法
传统的Taylor级数展开算法中, 由于Q未知, 可采用类似式 (9) 的方法来构造Q矩阵。
将式 (2) 进行泰勒级数展开, 可得误差矢量
采用WLS算法对式 (18) 求解得
式中:Q为OTDOA的协方差矩阵。Ri可由Ri2= (Xi-x) 2+ (Yi-y) 2中令x=x0, y=y0计算出。在下一次递归中, 令x'0=x0+Δx, y'0=y0+Δy。重复以上过程, 直到Δx和Δy足够小, 满足预先设定的一个门限值ε, 即
此时的 (x, y) 即为LTE终端位置估计值。
Taylor级数展开后是否收敛取决于初始值 (x0, y0) , 可将改进的Chan算法估计的结果 (xc, yc) 作为其初始值展开, 这样便得到改进的Taylor级数展开算法。
2.2.4 分层协同定位算法
为了更好地抑制非视距误差, 将改进的Chan算法和Taylor级数展开算法联合起来进行分层协同定位, 其流程如图2所示。
首先利用残差分析判决法对含NLOS误差的基站进行鉴别, 然后采用残差加权法估计Q矩阵和位置初值, 将Q矩阵和初值代入改进的Chan算法进行位置粗估计, 更新Q值, 再将粗估计值和更新的Q矩阵作为初始值代入Taylor级数展开算法中进行展开, 得OTDOA测量误差的局部LS解, 改进估计位置, 然后继续代入改进的Chan算法进行位置估计, 并更新Q矩阵, 进行第i次Taylor迭代, 直到OTDOA测量误差的局部LS解满足其设定的门限ε。
3 算法仿真及分析
为了检验HCLA算法的实际定位性能, 本文将HCLA算法和几种典型的定位算法在不同非视距误差、不同信道环境[11] (远郊, 郊区, 一般市区B, 一般市区A, 闹市区) 下进行仿真对比。假设LTE网络拓扑为经典的7基站, 正六边形蜂窝网结构, 小区半径为3 km, 收敛门限为1 m, OTDOA测量误差服从均值为零, 标准差为30 m的理想高斯分布, 非视距误差分别为确定值 (大小为视距传播距离的0～10%) 和服从COST259信道模型两种情况。其中一个基站 (非服务基站) 含非视距误差, 且所有基站均不提供OTDOA测量值先验信息。参与比较的算法为Chan算法、Taylor级数展开算法和残差加权算法, 改进的Chan算法, 改进的Taylor级数展开算法以及HCLA算法, 用均方根误差 (RMSE) 和误差累计分布 (CDF) 表示定位精度, 以上几种定位算法在NLOS误差传播环境下进行3 000次Monte-Carlo仿真。
非视距误差鉴别的仿真结果如图3所示。
从图3中可以清晰看出, 基站3的总加权值最大, 故判定基站3含NLOS误差, 与初始设定相符。
其次对各算法的定位性能进行仿真对比, 实验结果如图4和图5所示。
由图4可知, 当NLOS误差超过一定程度, HCLA算法的均方根误差最小, 且非视距误差越大, 越能有效地抑制非视距误差对LTE节点定位精度的影响。由图5可知, HCLA算法在70%的概率下定位精度为50 m左右, 在95%的概率下定位精度为100 m左右, 优于其他典型定位算法的定位精度。
最后对各个定位算法在不同信道环境下的定位性能进行仿真对比, 如图6所示。
从图6可以看出, 随信道环境的恶化, HCLA算法抑制NLOS误差的能力变得显著, 特别是在闹市区环境下。可见, HCLA算法在恶劣的信道环境下抑制NLOS误差的能力较强。
根据实验结果, 算法的定位精度和迭代次数对比结果分别如表1和表2所示。
%
注:算法1为Taylor算法, 算法2为改进的Taylor算法, 算法3为HCLA算法。
%
注:算法1为Taylor算法, 算法2为改进的Taylor算法, 算法3为HCLA算法。
由表1、2可知, HCLA算法达到门限值时所需迭代次数较大, 故与其他几种定位算法相比, 计算复杂度较高, 但其可以提高LTE终端的定位精度, 因此综合考虑计算复杂度与定位精度间的关系, 本改进算法具有更好的性能。
4 小结
本文对非视距误差的鉴别算法进行了改进, 同时提出了一种无需OTDOA误差先验信息的分层协同定位算法 (HCLA) , 先鉴别出含NLOS误差的基站, 再基于改进的Chan算法和Taylor级数展开算法对LTE终端位置进行分层协同定位。经过仿真分析, 本算法能准确鉴别出含非视距误差的基站, 且HCLA算法与几种典型的定位算法在同等条件下相比, 对NLOS误差的抑制能力更强, 定位精度更高, 具有实际的应用价值。
参考文献
[1]3GPP TS 36.355 v9.0.0, 3rd generation partnership project;technical specification group radio access network;E-UTRA;LTE positioning protocol[S].2009.
[2]CHAN Y T, HO K C.A simple and efficient estimator for hyperbolic location[J].IEEE Trans.Signal Processing, 1994, 42 (8) :1905-1915.
[3]GENTNER C, MUNOZ E, KHIDER M, et al.Particle filter based positioning with 3GPP-LTE in indoor environments[C]//Proc.Position Location and Navigation Symposium (PLANS) .Myrtle Beach, SC:IEEE Press, 2012:301-308.
[4]阎龙, 高泽华, 高峰, 等.一种适用于NLOS环境的LTE终端迭代定位算法[J].计算机应用研究, 2014, 31 (3) :876-878.
[5]YU K, GUO Y J.Improved positioning algorithms for non-line-ofsight environments[J].IEEE Trans.Vehicular Technology, 2008, 57 (4) :2342-2353.
[6]周康磊, 毛永毅.基于残差加权的Taylor级数展开TDOA无线定位算法[J].西安邮电学院学报, 2010 (3) :10-13.
[7]崔玮, 吴成东, 张云洲, 等.基于高斯混合模型的非视距定位算法[J].通信学报, 2014 (1) :99-106.
[8]赵军辉, 张雪雪, 曾龙基.提高NLOS环境下室内定位精度的新方法[J].北京邮电大学学报, 2012 (6) :38-43.
[9]HARA S, ANZAI D, YABU T, et al.A perturbation analysis on the performance of TOA and TDOA localization in mixed LOS/NLOS environments[J].IEEE Trans.Communications, 2013, 61 (2) :679-689.
[10]KAY S, VANKAYALAPATI N.Improvement of TDOA position fixing using the likelihood curvature[J].IEEE Trans.Signal Processing, 2013, 61 (8) :1910-1914.
