基于小波变换的猫群算法

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