基于量子粒子群优化算法的无线传感器网络节点优化
- 格式：pdf
- 大小：226.52 KB
- 文档页数：3
1 传感器节点优 化部署 假设监测区域可被 划分为很 多网格 , 每 个网格 用其 中 间的网格点表示 , 这样 , 整个监测区域就可以离散化为网 格 点的集合。网格的 粒度 ( 网 格大小 ) 需 要 根据 目标 检测 的 具体应用确定 , 以满足其 精度要 求。传感器 节点可 以部 署 在任意网格点之上 , 以监 测感知 范围内的 所有网 格点。 为 了便于讨论 , 目标 检测系统中的传感器使用 0 /1 检 测模型 , 即当某一网格点在传 感器节 点的感知 范围之 内时 , 就一 定 可以检测到 , 而当 其在传感器节点的感知范围之外时 , 就 一 定检测不到 . 如果监测区域 的任何 网格点 都可以 至少被 一 个传感器节点的感知 范围所 覆盖 , 则称此 区域是 完全覆 盖 的 [ 4, 5] 。在这样的系 统中 , 出 现在 任何 网 格点 上的 目标 都 能够被检测到。图 1 就是一个完全覆盖的监测区域。为 了 便于表述 , 可用检测向量来 描述某 一网格 点被传 感器节 点 覆盖的情况 , 检测向量的每一位分别对应一个传感器 , 其值
传统的 PSO 的运行轨迹由下列方程给出 v i ( t+ 1 ) = v i ( t) +
[ 2]
。
因而 , QPSO 算法的全 局搜 索能力 远远 优于 经典 的 PSO 算 法 [ 3] 。 本文针对无线传 感器网络感知节点的分布优化问题进 行了研究 , 提 出了 一种 基 于 QPSO 算法 的 分 布优 化 机制。 仿真实验结 果表 明 : QPSO 算法 在优 化性 能上 优于 传统 遗 传算法 ( GA ) 和量 子遗 传算 法 ( QGA ), 能 够有 效提 高网 络 整体的感知能力。
2. 1 传统 PSO 描述
在 d 维空间中 , 粒 子 i 的位置 向量 和速度 向量 分别 表 示为 xi ( t) = [ x i1 ( t) , xi 2 ( t), v i ( t) = [ v i1 ( t), vi2 ( t), , x id d ( t) ]
T
,
( 1) ( 2)
, v id ( t) ] T .
32
传 感器与微系统 ( T ransducer and M ic rosyste m T echno log ies)
2010 年 第 29 卷 第 2 期
基于量子粒子群优化算法的无线传感器网络节点优化
王艳萍 , 张惠敏 , 刘新贵
1 1 2
( 1. 郑州铁路职业技术学院 信息工程系 , 河南 郑州 450052; 2. 解放军信息工程大学 测绘学院 , 河南 郑州 450052 ) 摘 要 : 针对无线传 感器网络感 知节点 的分 布优化 问题 进行 了研 究 , 提出 了一 种基 于量 子粒 子群 优化
[7 , 8]
2. 2 QPSO 模型
Jun Sun 等 人根 据量子 D e lta势 阱提 出了 QPSO 算法 , 其基本思想是假定在一个量子场中运动的微粒将最 后收敛 到一个势能无穷大的极小的区域中。该模型在一些测试 函 数上的性能要优于传 统的优 化模型 , 在求 解多目 标优化 问 题时 , 也 采用此 模型。 Q PSO 算 法与 传统 方 法的 主要 不 同 点是取消了速度更新的概念 , 因为在量子时空框架中 , 粒 子 的状态是用波函数 的波函数为 | | 2 dx dy dz = Q dx dy dz . ( 5) ( x, t)来描述的 , 如在三维 空间中粒 子
其中 , g 为算 法 中 需 要调 整 的 变 量 , 一 般 大 于 ln 2, u 为一个介于 ( 0, 1 )之间 呈正 态分布 的随 机数 , 正、 负号 各 依 50% 的概率 取得。
图 1 基于网格点的传感器节点部署 F ig 1 Sensor node deploym ent based on grid po int
1 1 2
( 1. Depar t m en t of Information Engineerin g , Zhengzhou R ailway V ocationa& l T echn ica l College , Z hen gzh ou 450052, Ch ina ; 2. Institu te of Surveying and M app ing , PLA Information Engineering Un iversity , Zh engzhou 450052, Ch ina) Abstract : T he distr ibution op ti m ization proble m s o f node aw are o f w ire less sensor netw orks are studied. A d istributed opti m ization m echan ism is presented based on quantum particle sw ar m opti m ization ( QPSO ) algorithm. S i m ulation results show that QPSO a lgor ithm is super ior to the trad itiona l genetic a lgor ithm ( GA ) and quantum genetic a lgor ithm( QGA ) , can effec tive ly i m prove net w ork capacity o f the ov era ll perception. T he m ethod used to opti m ize the dep loym ent o f sensor nodes is feas ible . K ey w ords : w ire less sensor networks ( W SN s ); opti m ization( Q PSO ) 0 引 言 node ; opti m iza tion ; dep loy m ent ; quantum partic le swa r m
%
i1
M
Pi , 1 M
i= 1
%P
i= 1
,
%
M
P ij,
,
i= 1
1 M
%
M
P id ,
( 9)
i= 1
PP i j ( t) = rand 1 j ( ) p ij ( t) + ( 1- rand 1j ( ) ) pgj ( t) , ( 10) xi j ( t + 1 ) = PP ij ( t) # ! |mB estj ( t) x ij ( t) | ln ( 1 /rand 2j ( ) ) . ( 11) 其中 , rand 1j ( ), rand 2j ( ) 是 0~ 1 之 间的 随机 数 , mBest 是粒子群 pBest 的中间位置向量 , PP ij为 p ij和 pgj之间的随 机 点。 u 为 QPSO 的收敛系数。 QPSO 的算法流程为 : 1) 初始化每个粒子的位置向量 ; 2) 计算每个粒子的目标函数值 ; 3) 更新每个粒子的局部最优位置 p ij与相关变量 ; 4 )更新全局最优位置 pgj和其他相关变量 ; 5 )根据式 ( 9 )计算 mBest; 6 )根据式 ( 10 )计算 PP ij; 7 )根据式 ( 11 )计算 x ij; 8) 重复步骤 ( 2)~ ( 7), 直到满足迭 代的次数。
2. 3 算法流程
把式 ( 1 ), 式 ( 2) 改换成下式 mBest = = 1 M 1 M
M
2 QPSO 算法 Q PSO 算法是将量子计算与 粒子群 算法相 结合的 一种 新的优化方法 , 量子算法 中融入 了量子 力学的 许多基本 特 性 , 极大地提高了计算的效 率 , QPSO 已 逐步成 为一种 新的 计算模式。 Q PSO 算 法大 大提 高了 搜索 效率 , 且 能 弥补 粒 子群算法的不足。
-∀
。
!|
+ ∀
| 2 dx dy dz =
- ∀
!Q dx dy dz = 1 ,
+ ∀
( 6)
即粒子出现在空间中所有位置的概率之和为 1。 算法首先产生一个位于 p i 和 pg 之间的位置向量 p, 其 中 , p 由下式产生 p= (
1
pi +
2
ቤተ መጻሕፍቲ ባይዱ
pg ) / (
1
+
2
) .
( 7)
然后 , 根据概率求得粒子新的位置向量 x i ( t + 1 ) = p # ( 1 /g ) ln ( 1 /u) ∃ |x i ( t) - p | . ( 8)
量子粒子群优化 ( Q PSO ) 算法 是孙俊 等人从 量子力 学 的角度提出 一 种 新的 PSO 算 法
[ 1]
, 认 为 粒子 具 有量 子 行
为 , 每一个粒子在搜索空间移 动时 , 存在 着一个 以 Pbest 为 中心的 DELTA 势阱。由于在量 子空 间中的 粒子 满足聚 集 态的性质完全不同 , 粒子移动时没有确定的轨迹 , 这使粒子 可以在整个可行解空 间中进行探索寻找全 局最优解 , QPSO 算法调整参 数少 , 容 易实 现 , 收敛 能力 强 , 实 现时 间 短
Opti m ization of w ireless sensor net works nodes based on quantu m particle s warm opti m al algorithm
WANG Yan p in g , ZHANG H ui m in , L I U X in gu i
( QPSO ) 算法的分布优化机制。仿真 实验结 果表明 : QPSO 算法在 优化性 能上优于 传统遗 传算 法 ( GA ) 和 量子遗传算 法 ( QGA ), 能够有效提高网 络整体的感知能力 , 该方法用于传感器节点优化部署 是可行的。 关键词 : 无线传感器 网络 ; 节点 ; 优化 ; 部署 ; 量子粒子群 中图分类号 : TP 393 文献标识码 : A 文章编号 : 1000 9787( 2010) 02 0032 03
