《基于小波变换猫群算法》由会员分享，可在线阅读，更多相关《基于小波变换猫群算法（30页珍藏版）》请在金锄头文库上搜索。
1、On Deployment of Wireless Sensors on 3-D Terrains to Maximize Sensing Coverage by Utilizing Cat Swarm Optimization with Wavelet Transform 基于小波变换的猫群算法，以最大限度提高基于小波变换的猫群算法，以最大限度提高在三维地形部署无线传感器的覆盖率在三维地形部署无线传感器的覆盖率浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所.1.本文针对三维山丘地形环境下的网络覆盖策略展开研究,真实的无线传感器网络应用环境中,三维地形空间上的网络覆盖连通以及拓
2、扑控制等远比二维平面要复杂,二维平面空间上的覆盖策略不能直接用来解决三维地形上传感器网络的覆盖问题。2.覆盖问题指的是如何在监测区域部署传感器节点,并通过节点间的相互协作来提升无线传感器网络监测服务质量。网络覆盖情况直接关系到网络性能的好坏。为了能够更好地完成目标监测和信息获取的任务,必须保证无线传感器节点能有效地覆盖目标监测区域。浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所要解决的问题与问题的难点要解决的问题与问题的难点l需要解决的问题 如何在一个三维地形上部署最少的传感器，以达到最大的覆盖质量（QoC）l对算法QoC的影响因素 地形上的障碍物，信号的衰变，传感器的能量限制
3、（传感器由电池供电，在传输，接收和传感阶段都需要能量）等l如何计算QoC line-of-sight（LOS）算法（判断地形上的一个点是否被障碍物阻碍，因为更快的计算能力（需要计算的节点更少，不需要使用插值法计算）浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所 l现有方法 1.基于仿生算法：粒子群优化(PSO) 细菌觅食算法(BAF) 2.拉格朗日启发式 3.混合进化算法 4.三角形的分治算法（divide-and-conquer），DT-Score 以上所提出的算法都在某些方面具备一定的优势，但又存在很大的局限性： 基于仿生算法的，只在计算最优阀值时，速度上体现一定优势； 拉
4、个朗日算法，善不确定是否可用了存在大量传感器的三维环境； 浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所 混合进化算法，由于需要给出地形图的最大化视图，这就要依赖摄像机来实现； 三角形的分治算法（divide-and-conquer），DT-Score二维环境中，在扩展性方面具备一定优势，但在三维中实施失败；l本文提出的一种新方法 CSO-WT算法 优势：1.计算时间更快 2.迭代次数更少 3.收敛性更好 4.找到全局最优解方面具有更好的性能浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所所用方法概念介绍所用方法概念介绍1.小波变换（小波变换（WT） 传统的信号理
5、论是建立在传统的信号理论，是建立在Fourier分析基础上的，而Fourier变换作为一种全局性的变化，其有一定的局限性，如不具备局部化分析能力、不能分析非平稳信号等。 小波变换是一种新的变换分析方法，它继承和发展了短时傅立叶变换局部化的思想，同时又克服了窗口大小不随频率变化等缺点，能够提供一个随频率改变的“时间-频率”窗口，是进行信号时频分析和处理的理想工具。浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所1.DWT(discrete wavelet transform) 离散小波变换离散小波变换在计算DWT时，我们就有两种方法：1，构造出尺度函数和所有小波函数，直接计算。，构
6、造出尺度函数和所有小波函数，直接计算。2，设计低通滤波器h(k)，利用鱼骨型算法迭代计算。浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所尺度函数1.DWT(discrete wavelet transform) 离散小波变换离散小波变换近似系数纵向小波函数（vertical）横向小波函数（horizontal ）对角线小波函数（diagonl）浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所1.DWT(discrete wavelet transform) 离散小波变换离散小波变换离散小波变换用处：离散小波变换用处： Qoc是对每个像素点邻近传感器的信号等级的一种
7、评估标准，用于评估覆盖质量，但是维度太高，不直观！ 通过DWT进行降低维度，以便于寻找覆盖中的漏洞（coverage cavities）。浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所2.CSO(cat swarm optimization) 猫群猫群 猫群算法是一种新的智能群算法。分为两种模式：搜寻模式和追踪模式。搜寻模式中猫群搜寻下一个移动点，追踪模式中猫群追踪目标。猫群大部分时间是居于搜寻模式，当找到一个好的目标点（“猎物”），便会立即进入追踪模式。猫群在固定范围内随机分布，其中的“猫”随机取值。当“猫”取得合适的值时，便会记录“猫”的分布情况。算法会一直循环，直到最终模
8、式满足要求。浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所3.传感模式（传感模式（sensing models）本文运用了2种传感模式：1.Binary sensing model2.Probabilistic sensing modelWSN中的传感模式是一种基于传感器覆盖率特点的数学公式，是一种基于距离和环境条件的函数。浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所3.传感模式（传感模式（sensing models）1.Binary sensing model二进制感应可能性3-D 欧几里德距离传感器的最大感应范围浙江工业大学浙江工业大学 网络与多媒体研究
9、所网络与多媒体研究所3.传感模式（传感模式（sensing models）LOS ：line of sight算法。用来确定一个算法。用来确定一个地形点是否被障碍物阻挡，导致无法感应。地形点是否被障碍物阻挡，导致无法感应。浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所3.传感模式（传感模式（sensing models）2.Probabilistic sensing model传感器感应误差值。物理环境影响因素用于计算QoC浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所Sj 传感器和Pk像素点之间传感可能性传感器第i次部署之后的整体覆盖率水平像素点总数传感器总数
10、4.QoC（ quality of the coverage ）浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所Sj 传感器和Pj像素点之间的欧几里德距离覆盖质量值（一个像素点）4.QoC（ quality of the coverage ）QoC采用了CRM（Coverage Resolution Mode）浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所Proposed CSO-WT algorithm(a)复杂地形(b)起伏地形(c)平坦地形地形越平坦，传感器的覆盖率增加。复杂地形中，传感器的配置更加困难，因为传感器和相关像素点之前的LOS会变小。浙江工业大学
11、浙江工业大学 网络与多媒体研究所网络与多媒体研究所Proposed CSO-WT algorithm猫群算法猫群算法3中模式：中模式：1初始化模式（ Initialization ）2.搜寻模式（ Seeking Mode ）3.跟踪模式（ Tracing Mode ）浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所1.初始化模式（ Initialization ）初始化的概念是为了构建出一只一只的猫，形成猫群。猫的概念：猫的概念：将传感器部署到地形中去之后，每个传感器都视为为坐标，那么记录所有坐标的向量记做Dv（deployment vector），也称之为猫。浙江工业大学浙江
12、工业大学 网络与多媒体研究所网络与多媒体研究所1.初始化模式（ Initialization ）构造一只猫的步骤过程。构造一只猫的步骤过程。1.部署少量传感器，计算部署少量传感器，计算QoC。2. 通过通过dwt分析分析qoc矩阵，发现矩阵，发现qoc矩阵中的漏洞。部署剩下的矩阵中的漏洞。部署剩下的传感器在漏洞处，提高传感器在漏洞处，提高qoc。3.计算新计算新dv的的qoc如果达标，形如果达标，形成一只猫。成一只猫。4.重复这个步骤重复这个步骤k 次。得到次。得到k只只猫。猫。浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所1.初始化模式（ Initialization ）概念
13、引入：概念引入：自适应临界值（Th）：式子中k是一个介于0.01与0.1之间的一个值，表示迭代次数。具体实现：具体实现：Step1中通过计算少量的传感器部署得出了一个初步QoC。Step2中用dwt去分析qoc矩阵，使之降维。得到一个近似系数矩阵。将矩阵分为i列，那第i列的比重定义为Wi 计算公式如下：代表第i列，小于自适应临界值th的系数个数。N 代表整个矩阵小于th的系数个数。浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所1.初始化模式（ Initialization ）得到每个分区的比重Wi 之中，就可以算出，第i个分区所需要部署的传感器个数，定义为Sdi。然后根据Sdi
14、，把剩下的传感器部署到那些系数值小于th的像素点上。以上就是完成了漏洞的查询以及修补，得到了一个新的部署方案（Dv）。通过2个条件来判断Dv是否可以初始化成为一只可用猫，1.Qoc合格2.所有传感器使用完。判断完成，得到一只初始化的猫，保存Dv。然后重复上述步骤k次，得到k只猫，形成猫群。文章中提及，k值应该在10到40之间，但是最有效的值是20。浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所2.搜寻模式（ Seeking Mode ）首先根据混合比例MR来对猫群进入不同模式的猫进行分类。进入seeking mode的猫：step1，复制SMP只猫。step2，每一只复制的猫，
15、通过CDC来计算每一只猫中需要变动的传感器个数。setp3，一只需要移动的猫中，传感器移动的距离根据SRD来计算得出，再根据SMR也就是每个传感器的移动能力，来对每个传感器来进行移动。step4，计算出所有复制猫的移动耗能。step5，选择最高耗能的Dv来代替原来的猫，形成一只新猫。浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所3.追踪模式（ Tracing Mode ）一只猫进入tracing mode（25%），Step 1，每一只猫的MRT成分的传感器朝着更好的位置移动。根据WT计算出漏洞空间，然后传感器朝着该方向移动，移动还是根据SMR随机移动。（防止局部最优化）Ste
16、p 2，计算出移动之后的猫的能耗，以及qoc ，如果较原来的好，就代替它。浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所3.追踪模式（ Tracing Mode ）Fig. 6. Comparison of minimum number of sensors needed in order toachieve 90% coverage on different types of terrains.浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所DTFig. 5. Voronoi cells and Delaunay Triangulation.Delaunay三角
17、网的构建步骤应为： 1、离散点自动构建三角网，即构建Delaunay三角网。对离散点和形成的三角形编号，记录每个三角形是由哪三个离散点构成的。 2、找出与每个离散点相邻的所有三角形的编号，并记录下来。这只要在已构建的三角网中找出具有一个相同顶点的所有三角形即可。浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所Fig. 7. Comparison of QoC values that is achieved with different algorithmsby deploying 96 sensors on different types of terrains.浙江工业大学浙江
18、工业大学 网络与多媒体研究所网络与多媒体研究所Fig. 9. Progress of deployment with 64 sensors on 64 64 pixel size3-D terrain after (a) initial deployment for all methods (QoC=67%); (b) 1000iterations (QoC=75%); (c) 2000 iterations (QoC=77.3%).浙江工业大学浙江工业大学 网络与多媒体研究所网络与多媒体研究所Fig. 10. Comparison of CSO-WT method withg650 simple GA (GA-S) andsteady state GA (GA-SS) methods.
