Multi-objective Optimization of RSSI Sensor Deployment Considering Obstacles for Indoor Positioning
-
摘要: 针对目前无线传感器网络（wireless sensor network, WSN）部署时，障碍物影响WSN优化部署的问题，以接收信号强度指示传感器室内定位应用为例，提出了一种考虑障碍物的无线传感器多目标优化部署方法。首先，基于室内定位算法原理和传感器覆盖模型，给出了在室内定位场景下WSN有效覆盖率的概念和信标节点部署模型。然后，在分析障碍物感知模型和信标节点部署策略的基础上，提出了考虑障碍物的传感器部署多目标优化模型。最后，以第三代非支配排序遗传算法为基础设计优化模型求解算法，数值仿真结果与正三角形、正方形、正六边形均匀部署，以及没有考虑障碍物的优化部署（进化1 000代，传感器个数为36）结果进行对比，结果表明所提方法的WSN有效覆盖率分别提高了52.7%、112.1%、16.6%和9.62%。Abstract:Objectives At present, in the research on the optimization of wireless sensor network (WSN) deployment under the application of indoor positioning, most of studies are generally carried out under the ideal conditions without obstacles, and the impact of obstacles on WSN is rarely considered. To consider the influence of obstacles for WSN deployment, we propose a multi-objective optimization method of WSN topology considering obstacles under the application of indoor positioning using received signal strength indication sensors.Methods Firstly, a concept of effective coverage and beacon node deployment model is proposed based on the indoor positioning algorithm and sensor coverage model. Secondly, after the analysis of obstacle perception model and beacon node deployment strategy, a multi-objective optimization model of sensor deployment considering obstacles is proposed.Finally, the non-dominated sorting genetic algorithm Ⅲ is introduced to solve this optimization model. Three optimization objectives of all individuals, effective coverage, number of sensors, and convex hull area, as well as constraints considering obstacles and WSN topology rationality are calculated.Results The optimization method without considering obstacles is used as the comparison method, and three uniform sensor deployments are compared with the numerical simulation results of the proposed method.Regular triangle, square and hexagon are the mosaic shapes for the uniform sensor deployment.In the 1 000 generation, the effective coverage rate of the proposed method increased by 9.62% compared with the comparison method and increased by 52.7%, 112.1% and 16.6% respectively compared with the uniform deployment of regular triangle, square and regular hexagon.Conclusions The method proposed in this paper not only has advantages in improving the effective coverage rate and accelerating convergence of the optimization algorithm, but also increases the effective coverage rate compared with the traditional uniform deployment of sensors. Therefore, the proposed method will be helpful to improve the accuracy of indoor positioning.
-
城市化发展使城市产生不同功能的区域, 发掘并理解功能区域和人类移动规律可制定更好的城市规划便利人类生活[1]。Fusco等[2]将地域定义为地理上有相邻关系的站点，本文在此基础上定义基于地域的移动模式(zone-based movement pattern, ZMP)为一种移动轨迹及该轨迹关联的一对地域——起始地域O和目的地域D，任意ZMP p表示为p=O→D。对ZMP的发掘即可达到对地域和移动模式的双重发掘。随着GPS技术的快速发展，车辆的移动记录更容易获取，因此被广泛应用于交通[3-4]、人类活动[5]分析等。本文利用出租车GPS数据对城市居民的出行移动路径进行分析，根据乘客移动轨迹的分布与特征得到地域之间的关系，从而实现对ZMP的发掘。
目前对移动轨迹的研究有如下几点：①针对城市区域中特定地域间的运动方式的挖掘，如通过基于动态规划和基因算法的方法分析特定区域间的活动模式[6]；②通过移动数据进行行为分析，如通过结合空间特征和社会经济学特征的模型分析家庭的旅行模式[7]，通过乘客的乘车记录定性分析乘客的搭乘行为[8]等。此外，移动模式的分析还可通过不同领域的数据进行分析[9]，如通过智能卡数据评估未来的公共交通情况[10-11]。而在地域的发掘方面，普通的空间聚类方法如K-means[12]、BIRCH[13]等已发展完善，由此产生基于普通空间算法的改进算法，如基因算法[14]、基于层次结合Voronoi的空间聚类算法[15]等。此外，部分方法将聚类方法与约束方法相结合，如通过变化的人口普查数据进行区域的划分[16]，通过离散的Voronoi图结合位置关系和种子权重进行区域的划分[17]等。
以上方法在同时发掘地域和移动轨迹时仍具有一定的局限性。Kim等[18]开创性地提出了一种通过地铁搭乘记录同时发掘地域及乘客移动模式的方法。但该方法只考虑了空间关系而忽略了属性关系，这将产生有失实际的结果，如将距离很近但功能性质相差较远的地域当成相似类地域进行合并。且地铁只能在固定路线行驶，这导致该方法使用范围受限。相较地铁，出租车可从任意出发点行驶到任意目的点，为研究人类移动动态提供更独特的视窗[3]。因此本文在此研究基础上提出一种通过出租车轨迹发掘基于地域的移动模式的方法，它通过空间和属性特征的双重约束，保证了地域间的无重复性，使发掘的ZMP关联的地域的功能更集中，为使用者提供更有力的决策选择。
1 地域及移动方式发掘分析
本文方法基于聚类分析迭代的合并同一等级的相似实体，通过ZMP的合并实现保留移动方向性前提下的ZMP发掘，达到发掘地域和移动模式的目的。距离和专题属性组成的相邻约束保证了地域专题属性和地域间距离关系的相近性。如图 1所示, ZMP的发掘是通过连接矩阵进行迭代的过程，连接矩阵的元素表征所有ZMP间合并的可能程度，选出最大值后检查其是否满足迭代停止条件，若不满足，则将最大值对应的两个ZMP进行合并并更新连接矩阵，否则返回当前ZMP结果。在了解具体方法前，先介绍数据预处理及与方法相关的概念定义。
1.1 数据预处理
GPS数据源包含大量冗余的信息，需筛选出正确有用的信息，并进行格式编辑，以在发掘算法中被高效利用。预处理主要包括如图 2所示的4个步骤。
第1步:GPS数据的筛选包括两方面：①剔除错误和无用的GPS记录，如点范围不合理、非载客状态、非上下客状态时以及重复和不全的记录，仅保留正确的上下客点记录；②每条GPS记录仅保留有用的经纬度值、载客状态等项目。第2步:需确定站点，出租车没有固定的停靠点，GPS点数据是随机分散的，可借助站点进行移动模式确认工作。类似地域的定义，本文将站点定义为地理上有相邻关系的点的聚类结果点，可通过所有上下客点聚类得到站点数据。K-means是一种广泛使用的简单快速的基本聚类方法，经过上步筛选后的GPS点数据基本无噪声，因此本文通过K-means对GPS点聚类得到站点，每个上下客点都有一个隶属站点。第3步:确定移动轨迹记录，乘客的移动情况只需通过起始点和目的点反映，一条上客点记录和一条下客点记录即可组成一条移动记录。更新移动记录的起始点和目的点为其隶属的站点, 则得到最终的移动记录。此外需剔除起始站点和目的站点相同的移动记录，在某种意义上它表示乘客没有移动。第4步:对移动记录数据分类以获取不同移动模式，将起始站点相同且目的站点相同的移动记录归为一类移动模式，并统计该类移动模式中移动记录的数目。
1.2 相邻约束
本文相邻约束实现几何和属性的双重约束。几何约束主要通过Delaunay三角网与Voronoi图[19]实现，即一个实体只与其直接Delaunay相邻实体间有较为明显的作用。本文定义一个实体与它的Delaunay相邻实体的邻接值g与它们之间的空间距离的平方成反比；而对于Delaunay相邻实体之外的对象，g迅速衰减到可以忽略的程度。
$$ g\left( {p,q} \right) = k\frac{1}{{{d_E}{{\left( {p,q} \right)}^2}}},k = \left\{ \begin{array}{l} 1,q \in {N_p}\\ 0,q \notin {N_p} \end{array} \right. $$ (1) 式中，dE(p, q)表示实体p与其他实体q间的空间距离；k为邻近标志；Np表示与实体p的Delaunay相邻的实体集合。
但实体分布较分散时距离相隔很远的实体也可能是Delaunay相邻的，这可能导致此类实体的合并。因此需加入空间距离进一步约束，仅当两个实体Delaunay相邻且两者间的空间距离dE不超过阈值δ时才是几何相邻的。从而g值表示为：
$$ \begin{array}{*{20}{c}} {g\left( {p,q} \right) = \frac{k}{{{{d'}_E}{{\left( {p,q} \right)}^2}}},}\\ {k = \left\{ \begin{array}{l} 1,q \in {N_p}\;且\;{d_E}\left( {p,q} \right) \le \delta \\ 0,q \notin {N_p}\;或\;{d_E}\left( {p,q} \right) > \delta \end{array} \right.} \end{array} $$ (2) 式中，Np表示实体p的几何相邻实体的集合; d′E(p, q)是dE(p, q)归一化结果。
属性约束通过专题属性实现。即将空间属性与专题属性归一化后分别计算空间距离与专题属性距离，再进行加权融合即得到相邻距离DE, 表达式为：
$$ \begin{array}{*{20}{c}} {{D_E}\left( {p,q} \right) = {w_1}\sqrt {{{\left( {{x_p} - {x_q}} \right)}^2} + {{\left( {{y_p} - {y_q}} \right)}^2}} + }\\ {{w_2}\sqrt {\sum\limits_{k = 1}^n {\left( {{A_{pk}} - {A_{qk}}} \right)} } } \end{array} $$ (3) 式中，Apk表示实体p的第k维专题属性值; w1、w2表示几何约束与属性约束的权值，默认情况为w1=w2=0.5。
通过DE替代式(2)中的d′E得到两个实体的最终g值为：
$$ \begin{array}{*{20}{c}} {g\left( {p,q} \right) = k\frac{1}{{{D_E}{{\left( {p,q} \right)}^2}}},}\\ {k = \left\{ \begin{array}{l} 1,q \in {N_p}\;且\;{d_E}\left( {p,q} \right) \le \delta \\ 0,q \notin {N_p}\;或\;{d_E}\left( {p,q} \right) > \delta \end{array} \right.} \end{array} $$ (4) 1.3 地域及ZMP相关的定义
给定N个站点的集合S={s1…sN}，则有如下定义。
定义1 地域zi是由一个或若干站点组成的，即zi={si…sk}(1≤i≤k≤N)。不同地域不包含相同的站点，即对任意地域zi、zj(i≠j)都有sp≠sq(sp∈zi, sq∈zj)。任意站点可看作单地域，即由单个站点组成的地域。
定义2 两个地域间的邻接值为两个地域zi、zj中站点间邻接值的平均值：
$$ g\left( {{z_i},{z_j}} \right) = \frac{{\sum {g\left( {{s_p},{s_q}} \right)} }}{n},{s_p} \in {z_i},{s_q} \in {z_j} $$ (5) 式中，g(sp, sq)为站点sp和站点sq间的邻接值；n为zi、zj中站点对的数目。
定义3 地域zi的属性平均值$\overline {A\left( {{z_i}} \right)} $为该地域中所有站点的属性的平均值：
$$ \overline {A\left( {{z_i}} \right)} = \frac{{\sum\limits_{i = 1}^n {A\left( {{s_p}} \right)} }}{n},{s_p} \in {z_i} $$ (6) 式中，A(sp)为站点sp归一化后的专题属性值；n为地域zi中的站点数目。
定义4 地域zi、zj间的相邻系数为邻接值与专题属性平均值差异的比值，记为G(zi, zj)：
$$ G\left( {{z_i},{z_j}} \right) = \frac{{g\left( {{z_i},{z_j}} \right)}}{{\left| {\overline {A\left( {{z_i}} \right)} - \overline {A\left( {{z_j}} \right)} } \right|}} $$ (7) G(zi, zj)值越大, 表明地域zi、zj空间距离越小, 属性越接近，反之亦然。
定义5 地域zi、zj是相邻的, 当且仅当G(zi, zj)≥γ成立，否则不相邻。γ为地域合并最小值，只有相邻的地域才可能合并。
在以上地域的定义的基础上，对ZMP可定义为：已知初始状态下包含有N1个地域的集合Z={z1…zN1}关联了N2种ZMP，可表示为ZMP集M={m1…mN2}，其中mk=z0→zd(1≤k≤N2, z0∈Z, zd∈Z且z0≠zd)。通过该ZMP集M迭代发掘到的第i种ZMP为：pi=Oi→Di(Oi⊂Z, Di⊂Z且Oi≠Di)。
定义6 对ZMP pi=Oi→Di和pj=Oj→Dj，若Oi和Oj相邻且Di和Dj相邻，则这两个ZMP相邻。
定义7 两个ZMP pi=Oi→Di和pj=Oj→Dj间的连接值为两者的起始地域的合并地域中站点到目的地域的合并地域站点的平均数目[18]：
$$ \begin{array}{*{20}{c}} {{\rho _{i,j}} = \rho \left( {{p_i},{p_j}} \right) = k\frac{{n\left( {{O_i} \cup {O_j} \to {D_i} \cup {D_j}} \right)}}{{\left| {{O_i} \cup {O_j}} \right| \cdot \left| {{D_i} \cup {D_j}} \right|}},}\\ {k = \left\{ \begin{array}{l} 1,{p_j} \in {N_{{p_i}}}\\ 0,{p_j} \notin {N_{{p_i}}} \end{array} \right.} \end{array} $$ (8) 式中，n(Oi∪Oj→Di∪Dj)表示从合并起始地域Oi∪Oj到合并目的地域Di∪Dj的移动数目；Npi为pi相邻的ZMP集合。两种相邻的ZMP覆盖的轨迹数目越多，关联的站点越少，ρi, j就越大，两者越可能合并。且根据定义有ρi, j=ρj, i。
定义8 已知两个ZMP pi=Oi→Di和pj=Oj→Dj，定义两者合并得到的新ZMP为：
$$ {p_t} = {Q_t} \to {D_t}\left( {{O_t} = {O_i} \cup {O_j},{D_t} = {D_i} \cup {D_j}} \right) $$ (9) 定义9 已知ZMP pi=Oi→Di和pj=Oj→Dj，若Oj⊂Oi且Dj⊂Di, 则pj是pi的子集。
定义10 已知ZMP pi=Oi→Di和pj=Oj→Dj，若Oi=Oj∪Dj或Di=Oj∪Dj，则pj是pi的子集。子集解决不同地域出现相同站点的问题，使得新发掘的地域无交叠，更易理解。
通过式(8)可构建表示ZMP集中任意ZMP间连接值的连接矩阵。由于pi, j=pj, i，可采用上三角连接矩阵表示M中N2个ZMP间的连接值：
$$ \mathit{\boldsymbol{C}} = \left( {\begin{array}{*{20}{c}} 0&{{\rho _{1,2}}}& \cdots &{{\rho _{1,{N_2} - 1}}}&{{\rho _{1,{N_2}}}}\\ 0&0& \cdots &{{\rho _{2,{N_2} - 1}}}&{{\rho _{2,{N_2}}}}\\ \vdots&\vdots&\ddots&\vdots&\vdots \\ 0&0& \cdots &0&{{\rho _{{N_2} - 1,{N_2}}}}\\ 0&0& \cdots &0&0 \end{array}} \right) $$ (10) 1.4 新ZMP的发掘方法
新ZMP的发掘算法通过连接矩阵C获取当前迭代中最优合并的两个ZMP。整体流程如下：
在初始化阶段，将每个站点初始化为单地域得到地域集Z，移动模式初始化为ZMP得到ZMP集M，则可得初始连接矩阵C(1)；第k次迭代时对当前M包含的Rk条ZMP计算连接矩阵C(k)，将矩阵最大元素ρ*(k)=max(ρi, j(k))(i, j=1…Rk且i≠j)关联的两个ZMP合并成新ZMP pt，在剩余ZMP中找到pt的子集合并到pt，M将移除所有合并入pt的ZMP并加入新ZMP pt，同时移除的ZMP关联的地域会从Z中移除，而pt关联的两个新地域将被加入。此外，pt的自集关联的两个地域在更新关联地域后同属一个，需从M中移除。一次迭代后，M中会减少至少2个ZMP，新增1个A类ZMP，有若干C类ZMP可能更新为B类ZMP。更新完Z、M及连接矩阵后继续下一次迭代，直到剩余的ZMP不能合并或连接矩阵中的最大值比阈值θ小，停止迭代，将M返回得到最终结果。
本文将类似pt这样由其他ZMP合并成的新ZMP记为A类ZMP。若被移除的地域在M中仍有其他关联的ZMP，则需用其所属的新地域更新这些ZMP的关联地域，本文记这类与新地域关联但不是新合成的ZMP为B类ZMP，剩下与新地域无关联的ZMP记为C类ZMP，三类ZMP的区别如表 1所示。
表 1 三类ZMP的区别Table 1. Difference of Three Trpes of ZMP条件 A类 B类 C类 由两个ZMP合并成 √ × × 关联地域中有新地域 √ √ × 2 实验与评价
2.1 数据预处理
本文采用北京市连续3天的出租车GPS数据。筛选后得到195 622条移动轨迹记录，覆盖了391 244个上下客站点(见图 3(a))。通过K-means对其初聚类得到站点数据，K值决定了初始地域的粒度，继而影响最终结果地域的粒度，K值越大, 产生的新地域的覆盖范围越小、越精细，根据不同的数据及需求可选择不同的K值。本文以中粒度100个站点为例进行实验(见图 3(b))，本文专题属性采用不同类型的兴趣点在北京的分布来表示(见图 3(c)、图 3(d))，选取的5种类型的兴趣点分别为购物点、教育点、景点、企业点和居民区。这与人类的日常生活关联较为紧密，因此足够表达出城市的不同的功能，本文兴趣点数据来源于百度地图。
图 4(a)是100个站点间的Voronoi图，图中的数字是相应站点的标识码，由此可推断站点间Delaunay相邻关系。对195 622条移动记录分类，并去掉起始站点与目的站点相同的记录，得到674种移动模式共覆盖182 519条移动轨迹。对移动模式覆盖的移动记录数目的统计结果如图 4(b)所示，横、纵坐标分别为起始和目的站点标识码，站点标志码从0增到100，图中格子颜色越深，表示移动数目越多，其能反映更多人的活动轨迹，会优先被用到算法中。但该图中浅色占大部分，这类移动轨迹数目较少的移动模式在发掘算法中大部分是不被用到的，去掉这部分移动模式可减少算法的计算和时间耗费，并消除噪声。本文以去掉移动数目小于100的移动模式为例进行实验，经筛选后剩余336种移动模式共覆盖48 644条移动轨迹。将每个站点初始化单地域，则336种移动模式可全部初始化C类ZMP进行后续发掘。
为定量评估新产生的ZMP和地域，本文采用3种评估值[30]：评估覆盖度的v值、评估精准度的a值和对前两者折中评估的c值。如对ZMP pi=Oi→Di的评估方法如式(11)所示。
$$ \left\{ \begin{array}{l} v\left( {{p_i}} \right) = r\left( {{O_i} \to {D_i}} \right) = \frac{{n\left( {{O_i} \to {D_i}} \right)}}{m}\\ a\left( {{p_i}} \right) = \frac{{r\left( {{O_i} \to {D_i}} \right)}}{{r\left( {{O_i} \to D.} \right) \cdot r\left( {O. \to {D_i}} \right)}} = \\ \;\;\;\;\;\;\;\;\;\;\frac{{mn\left( {{O_i} \to {D_i}} \right)}}{{n\left( {{O_i} \to D.} \right) \cdot n\left( {O. \to {D_i}} \right)}}\\ c\left( {{p_i}} \right) = \sqrt {v\left( {{p_i}} \right)a\left( {{p_i}} \right)} = \\ \;\;\;\;\;\;\;\;\;\;\frac{{n\left( {{O_i} \to {D_i}} \right)}}{{\sqrt {n\left( {{O_i} \to D.} \right) \cdot n\left( {O. \to {D_i}} \right)} }} \end{array} \right. $$ (11) 其中，r(Oi→Di)、r(O·→Di)、r(Oi→D·)依次为从Oi到Di的移动轨迹数目比例、以Di为目的地域的移动轨迹数目比例、以Oi为起始地域的移动轨迹数目的比例；n(Oi→Di)是从Oi到Di移动轨迹数目；m是移动轨迹的总数目。v值通过ZMP覆盖的移动轨迹数目计算，v值越高，则相应ZMP的关联地域间的联系更紧密；a值通过ZMP关联的起始地域和目的地域的独立度计算，其暗示关联的两个地域间有内在联系；c值是覆盖度和准确度的平衡，它可挖掘到性能较好但不易发现的隐藏ZMP。
2.2 实验结果及分析
地域合并最小值γ的影响将在后文详细描述。本文以γ=10为例，使算法迭代到没有可合并的ZMP为止，最终共迭代了19次后返回最终结果。图 5(a)-5(d)依次是第5、10、15、19次迭代后产生的A类ZMP关联的新地域。
最终ZMP集中有238个ZMP，包含14个A类ZMP(见图 6)，124个B类ZMP以及100个C类ZMP。最终结果产生了13个新地域(见表 2)。
表 2 新地域Table 2. Newly Discovered Zones地域 组成站点 z1 95，83，78 z2 53，34 z3 22，11，1 z4 13，2 z5 82，80 z6 33，27 z7 54，24 z8 52，43，37 z9 40，28，3 z10 51，42，30 z11 96，39 z12 76，69 z13 21，19，8 为评估238个ZMP，分别计算3类ZMP的v值、a值、c值的平均值，并与336个初始ZMP和238个结果ZMP的总体平均值对比。图 7(a)是平均v值的对比结果，可发现A类ZMP>B类ZMP>C类ZMP，即发掘的新地域关联的ZMP(A、B类ZMP的并集)相较普通ZMP有较好的覆盖度；同时结果ZMP相比初始ZMP，平均v值有很大提升，从侧面反映出发掘的新ZMP有较大的覆盖度。图 7(b)、图 7(c)是平均a值和平均c值的对比结果，与平均v值结果相同，即A类ZMP不论在覆盖度、精准度还是两者折中的评估标准上都有最好的评估结果，B类ZMP次之，且都优于C类ZMP以及未经处理的初始ZMP。由此反映算法发掘到的新ZMP相较其他ZMP有更优的性能。
为研究γ值影响，固定迭代次数为15次，改变γ值，变化如表 3所示。随着γ的增大，新地域的数目先从5增加到11后减小至0，参与合并新地域的初始地域数目也有相同的变化趋势，而新地域中的最大地域(组成地域数目最多的地域)组成的地域数目却一直在减少。当γ较小时如γ∈[0, 1]时，更多地域间的相邻系数满足G>γ，导致更多地域被合并到同一新地域中，从而产生的新地域不多，且更多次迭代耗费在合并初始地域与另一新地域而非两个初始地域上，因此参与合并的初始地域总数增势缓慢；当γ在[1, 5)，满足G>γ的地域对的数目逐渐减小，更多地产生由初始地域两两合成的新地域，新地域数目增幅明显。同理，更多次迭代会耗费在将合并两个初始地域上，参与合并的初始地域总数随之增多，直到γ=5达到最大。当γ继续增大，满足G>γ的地域对数目剧烈减少，各项指标也随之降低，直到γ=220时已无满足G>γ的地域对可合并，几项指标也随之降到0。
表 3 γ值对产生的新地域的影响Table 3. Influence of γ on the Newly Discovered Zone地域 γ值 0 0.1 1 5 10 20 30 40 50 200 220 新地域 5 5 6 11 10 9 4 3 2 2 0 参与合并初始地域 20 20 21 26 25 18 8 6 4 2 0 最大地域组成地域 12 11 9 4 3 2 2 2 2 1 0 表 4为不同γ值下的结果ZMP的c值评估。γ≥220时不会产生新ZMP，因此不对该范围讨论。随着γ的增大，C类ZMP平均的c值与结果ZMP的平均c值基本持平，A类、B类ZMP的平均c值大体呈下降的趋势，但一直都高于初始ZMP的平均c值，证明通过该算法可在初始ZMP中发掘到性能优良的隐藏ZMP。且不论γ为何值，都有A类ZMP >B类ZMP >C类ZMP，即算法发掘的新地域关联的ZMP的c值优于普通ZMP，反映出该算法在多种条件下都能发掘当前较优的ZMP和地域。
表 4 γ值对c值的影响Table 4. Influence of γ on c ValueZMP γ值 0 0.1 1 5 10 20 30 40 50 200 220 A类ZMP 0.346 8 0.332 8 0.295 8 0.218 1 0.238 9 0.202 4 0.172 3 0.178 6 0.193 6 0.168 9 - B类ZMP 0.142 6 0.139 0 0.137 1 0.138 8 0.136 7 0.142 2 0.130 1 0.145 5 0.151 4 0.135 9 - C类ZMP 0.098 0 0.104 6 0.112 1 0.133 9 0.122 3 0.111 8 0.091 4 0.086 8 0.083 0 0.080 3 - 结果ZMP 0.103 6 0.109 9 0.118 1 0.138 5 0.127 5 0.114 6 0.092 4 0.087 6 0.083 7 0.080 6 - 初始ZMP 0.076 7 - 3 结语
本文研究了基于出租车乘车记录的ZMP的发掘即移动模式和地域的双重发掘。通过从出租车轨迹数据筛选出有用的数据来达到同时确认地域和地域之间的移动模式的目的，并以北京出租车数据为例进行了模型验证分析，实验结果显示，本文方法在发掘ZMP上能得到满意的结果，新发掘到的移动模式与其关联地的地域将有助于决策者更好地理解地域的存在以及这些地域之间的关系。下一步的工作将比较预处理中不同聚类算法对ZMP发掘的影响，同时会考虑采纳更多属性因素以及对连接矩阵的迭代算法进一步优化，以提高新发掘的ZMP的性能与分析效率。
-
![]()
图 5 二维平面网格顶点与染色体基因链的转换
Figure 5. Transformation of Vertex of 2D Planar Grid and Chromosome Gene Chain
![]()
图 7 不同优化方法在不同进化代数下的优化结果
Figure 7. Optimization Results of Different Optimization Methods Under Different Generations
![]()
图 8 在相同进化代数下两种优化方法效果对比
Figure 8. Comparison of Two Optimization Methods Under Same Generation
![]()
图 10 考虑障碍物的信标节点优化部署方案与正六边形均匀部署方案示意图
Figure 10. Optimized Deployment Scheme Considering Obstacles and Regular Hexagon Uniform Deployment Scheme
表 1 本文提出的方法与不同均匀部署方法对比
Table 1 Comparison Between the Proposed Method and Different Uniform Layout Methods
实验方案 进化代数 有效覆盖率/% 运行时间/min 信标个数 27 25 28 优化部署 50代 59.8 57.6 61.9 2.86 100代 65.5 61.6 69.8 5.80 500代 72.8 65.1 74.3 27.66 1 000代 78.8 66.4 79.4 57.44 均匀部署 51.6（正三角形） 31.3（正方形） 68.1（正六边形） 0.015 有效覆盖率提高/% 52.7 112.1 16.6 注：有效覆盖率提高是指优化部署方案的1 000代方案与均匀部署各方案相比，有效覆盖率提高程度。 
下载: 导出CSV
-
[1] Akyildiz I F, Su W L, Sankarasubramaniam Y, et al. A Survey on Sensor Networks[J]. IEEE Communications Magazine, 2002, 40(8): 102-114. doi: 10.1109/MCOM.2002.1024422
[2] 崔莉, 鞠海玲, 苗勇, 等. 无线传感器网络研究进展[J]. 计算机研究与发展, 2005, 42(1): 163-174. Cui Li, Ju Hailing, Miao Yong, et al. Overview of Wireless Sensor Networks[J]. Journal of Computer Research and Development, 2005, 42(1): 163-174.
[3] 刘惠, 柴志杰, 杜军朝, 等. 基于组合虚拟力的传感器网络三维空间重部署算法研究[J]. 自动化学报, 2011, 37(6): 713-723. Liu Hui, Chai Zhijie, Du Junzhao, et al. Sensor Redeployment Algorithm Based on Combined Virtual Forces in Three Dimensional Space[J]. Acta Automatica Sinica, 2011, 37(6): 713-723.
[4] Ke W C, Liu B H, Tsai M J. Constructing a Wireless Sensor Network to Fully Cover Critical Grids by Deploying Minimum Sensors on Grid Points is NP-Complete[J]. IEEE Transactions on Computers, 2007, 56(5): 710-715. doi: 10.1109/TC.2007.1019
[5] Ke W C, Liu B H, Tsai M J. The Critical-Square-Grid Coverage Problem in Wireless Sensor Networks is NP-Complete[J]. Computer Networks, 2011, 55(9): 2209-2220. doi: 10.1016/j.comnet.2011.03.004
[6] 刘玉英, 史旺旺. 一种基于遗传算法的无线传感器网络节点优化方法[J]. 传感技术学报, 2009, 22(6): 869-872. doi: 10.3969/j.issn.1004-1699.2009.06.022 Liu Yuying, Shi Wangwang. Optimal Distribution of Detecting Node of Measure Control System Based on Wireless Sensor Network[J]. Chinese Journal of Sensors and Actuators, 2009, 22(6): 869-872. doi: 10.3969/j.issn.1004-1699.2009.06.022
[7] Mahboubi H, Aghdam A G. Distributed Deployment Algorithms for Coverage Improvement in a Network of Wireless Mobile Sensors: Relocation by Virtual Force[J]. IEEE Transactions on Control of Network Systems, 2017, 4(4): 736-748. doi: 10.1109/TCNS.2016.2547579
[8] Dai G Y, Lü H X, Chen L Y, et al. A Novel Coverage Holes Discovery Algorithm Based on Voronoi Diagram in Wireless Sensor Networks[J]. International Journal of Hybrid Information Technology, 2016, 9(3): 273-282. doi: 10.14257/ijhit.2016.9.3.25
[9] 金合丽, 刘半藤, 陈唯, 等. 基于遗传算法的水下传感器网络节点部署算法研究[J]. 传感技术学报, 2019, 32(7): 1083-1087. doi: 10.3969/j.issn.1004-1699.2019.07.021 Jin Heli, Liu Banteng, Chen Wei, et al. Research on the Nodes Deployment Scheme for Sensor Coverage in Underwater Wireless Networks Based on Genetic Algorithm[J]. Chinese Journal of Sensors and Actuators, 2019, 32(7): 1083-1087. doi: 10.3969/j.issn.1004-1699.2019.07.021
[10] 李晟, 姚鑫骅, 傅建中. 基于通信质量约束的主轴热监测无线传感器布点优化[J]. 浙江大学学报(工学版), 2013, 47(7): 1281-1286. doi: 10.3785/j.issn.1008-973X.2013.07.022 Li Sheng, Yao Xinhua, Fu Jianzhong. Communication Quality Constraint-Based Location Optimization of Wireless Sensor in Thermal Monitoring of Spindle[J]. Journal of Zhejiang University (Engineering Science), 2013, 47(7): 1281-1286. doi: 10.3785/j.issn.1008-973X.2013.07.022
[11] 杨永建, 樊晓光, 甘轶, 等. 基于改进PSO算法的传感器网络覆盖优化[J]. 系统工程与电子技术, 2017, 39(2): 310-315. Yang Yongjian, Fan Xiaoguang, Gan Yi, et al. Coverage Optimization of Sensor Network Based on Improved Particle Swarm Optimization[J]. Systems Engineering and Electronics, 2017, 39(2): 310-315.
[12] Sengupta S, Das S, Nasir M D, et al. Multi-objective Node Deployment in WSNS: In Search of an Optimal Trade-off Among Coverage, Lifetime, Energy Consumption, and Connectivity[J]. Engineering Applications of Artificial Intelligence, 2013, 26(1): 405-416. doi: 10.1016/j.engappai.2012.05.018
[13] Jia J, Chen J, Chang G R, et al. Multi-objective Optimization for Coverage Control in Wireless Sensor Network with Adjustable Sensing Radius[J]. Computers and Mathematics with Applications, 2009, 57(11/12): 1767-1775.
[14] Liu X X, He D S. Ant Colony Optimization with Greedy Migration Mechanism for Node Deployment in Wireless Sensor Networks[J]. Journal of Network and Computer Applications, 2014, 39: 310-318. doi: 10.1016/j.jnca.2013.07.010
[15] Abo-Zahhad M, Sabor N, Sasaki S, et al. A Centralized Immune-Voronoi Deployment Algorithm for Coverage Maximization and Energy Conservation in Mobile Wireless Sensor Networks[J]. Information Fusion, 2016, 30: 36-51. doi: 10.1016/j.inffus.2015.11.005
[16] 权恩猛. 基于遗传算法的多障碍区域最大覆盖优化[J]. 工业控制计算机, 2017, 30(12): 108-110. doi: 10.3969/j.issn.1001-182X.2017.12.048 Quan Enmeng. Maximal Coverage Enhancement Based on Genetic Algorithm in Multiple Obstacles Area[J]. Industrial Control Computer, 2017, 30(12): 108-110. doi: 10.3969/j.issn.1001-182X.2017.12.048
[17] 刘韬, 徐爱功, 隋心, 等. 新息向量的抗差Kalman滤波方法及其在UWB室内导航中的应用[J]. 武汉大学学报(信息科学版), 2019, 44(2): 233-239. doi: 10.13203/j.whugis20170067 Liu Tao, Xu Aigong, Sui Xin, et al. An Improved Robust Kalman Filtering Method Based on Innovation and Its Application in UWB Indoor Navigation[J]. Geomatics and Information Science of Wuhan University, 2019, 44(2): 233-239. doi: 10.13203/j.whugis20170067
[18] 陈锐志, 叶锋. 基于Wi-Fi信道状态信息的室内定位技术现状综述[J]. 武汉大学学报(信息科学版), 2018, 43(12): 2064-2070. doi: 10.13203/j.whugis20180176 Chen Ruizhi, Ye Feng. An Overview of Indoor Positioning Technology Based on Wi-Fi Channel State Information[J]. Geomatics and Information Science of Wuhan University, 2018, 43(12): 2064-2070. doi: 10.13203/j.whugis20180176
[19] 赵昭, 陈小惠. 无线传感器网络中基于RSSI的改进定位算法[J]. 传感技术学报, 2009, 22(3): 391-394. doi: 10.3969/j.issn.1004-1699.2009.03.020 Zhao Zhao, Chen Xiaohui. An Improved Localization Algorithm Based on RSSI in WSN[J]. Chinese Journal of Sensors and Actuators, 2009, 22(3): 391-394. doi: 10.3969/j.issn.1004-1699.2009.03.020
[20] Bahl P, Padmanabhan V N. RADAR: An In-Building RF-Based User Location and Tracking System[C]//The 19th Annual Joint Conference of the IEEE Computer and Communications Societies, Tel Aviv, Israel, 2000.
[21] Bishop A N, Fidan B, Anderson B D O, et al. Optimality Analysis of Sensor-Target Localization Geometries[J]. Automatica, 2010, 46(3): 479-492. doi: 10.1016/j.automatica.2009.12.003
[22] Jameii S M, Faez K, Dehghan M. Multiobjective Optimization for Topology and Coverage Control in Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks, 2015, 2015(2): 100-113.
[23] 孙泽宇, 伍卫国, 王换招, 等. 概率模型下的一种优化覆盖算法[J]. 软件学报, 2016, 27(5): 1285-1300. Sun Zeyu, Wu Weiguo, Wang Huanzhao, et al. Optimized Coverage Algorithm in Probability Model[J]. Journal of Software, 2016, 27(5): 1285-1300.
[24] Rebai M, Le berre M, Snoussi H, et al. Sensor Deployment Optimization Methods to Achieve both Coverage and Connectivity in Wireless Sensor Networks[J]. Computers and Operations Research, 2015, 59: 11-21. doi: 10.1016/j.cor.2014.11.002
[25] Dhillon S S, Chakrabarty K. Sensor Placement for Effective Coverage and Surveillance in Distributed Sensor Networks[C] //IEEE Wireless Communications and Networking Conference, New Orleans, LA, USA, 2003.
[26] Jain H, Deb K. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach, Part Ⅱ: Handling Constraints and Extending to an Adaptive Approach[J]. IEEE Transactions on Evolutionary Computation, 2014, 18 (4): 602-622. doi: 10.1109/TEVC.2013.2281534
[27] Deb K, Pratap A, Agarwal S, et al. A Fast and Elitist Multi-objective Genetic Algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6 (2): 182-197. doi: 10.1109/4235.996017
[28] Jain H, Deb K. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach, Part Ⅱ: Handling Constraints and Extending to an Adaptive Approach[J]. IEEE Transactions on Evolutionary Computation, 2014, 18 (4): 602-622. doi: 10.1109/TEVC.2013.2281534
[29] 田桂林, 刘昌云, 高嘉乐, 等. 基于烟花算法的多传感器优化模型部署[J]. 系统工程与电子技术, 2019, 41 (8): 1742-1748. Tian Guilin, Liu Changyun, Gao Jiale, et al. Multisensor Optimal Disposition Model Based on Fireworks Algorithm[J]. Systems Engineering and Electronics, 2019, 41 (8): 1742-1748. .
-
期刊类型引用(5)
1. 沙洪俊，袁修孝. 双目影像密集匹配方法的回顾与展望. 武汉大学学报(信息科学版). 2023(11): 1813-1833 . 
百度学术
2. 曾兴国，左维，李春来，刘建军，任鑫，严韦，刘宇轩，高兴烨. 中国月球地形制图研究进展. 武汉大学学报(信息科学版). 2022(04): 570-578 . 百度学术
3. 曾兴国，刘建军，左维，任鑫，严韦，张舟斌，高兴烨，陈王丽，刘宇轩，李春来. 泛地图理论下深空探测场景空间制图表达思考. 武汉大学学报(信息科学版). 2022(12): 2123-2133 . 百度学术
4. 林璐，谭龙，王爽，梁爽. 利用卫星立体影像生产DEM的关键技术研究. 北京测绘. 2021(02): 157-160 . 百度学术
5. 马顶，赵尚民，程维明. 基于LROC NAC影像的高分辨率连续DEM数据制作. 测绘通报. 2021(09): 93-97 . 百度学术
其他类型引用(4)
计量
- 文章访问数: 482
- HTML全文浏览量: 113
- PDF下载量: 77
- 被引次数: 9
