无线传感网络设计问题

摘要

本文针对无线传感网络节点展开讨论，主要研究在监视区域内放置节点个数与成功覆盖概率的关系、节点的通信模型设计问题。

对于问题1，首先考虑将节点分为两大类，一类节点一定完全落在监视区域内，另一类节点只能部分落在监视区域内，通过这两类节点的发生概率以及这两类节点覆盖面积的期望值，可以求得所有节点覆盖面积的期望值。运用概率论的知识综合两类节点的期望，求解出至少要放置88个节点，才能使成功覆盖整个区域的概率在95%以上。

同时通过随机模拟仿真实验，我们得出了成功覆盖概率与节点个数的关系图，可以清晰的看出成功覆盖概率随着节点个数的变化趋势。

对于问题2，首先根据题目要求描点连线，将不可以通行的路径去掉，得到节点通信路径图，通过该图我们可以找出任意两个节点间的通信通路，例如节点31到节点74的通信通路为：31?69?21?74，但显然其路径不唯一，我们在节点通信路径图的基础上进行优化，找出两个节点之间的最短路径，在解决这个问题上我们分为两步优化：

第一步：运用Dijkstra算法求出固定起点到任意点的最短路径；第二步：运用Floyd算法求出任意两节点间的最短通信通路，例如节点1到节点90的最短通信通路为：1?80?64?25?46?65?66?93?13?3?87?15?60?90。

对于问题3，从节能角度出发，在问题2通信模型的基础上，进一步考虑无线传感网络节点间通信半径与能量消耗的关系。本文认为通信半径越长，能量消耗越多。因此，问题3的目标变为了使相邻节点间路径最短，根据这个目标我们可以引用最小生成树的思想得到一个最小生成树路径图，得到从节能角度考虑设计的任意两节点间的通信路径，例如节点76到节点19的通信通路为：76?60?19。

在问题3上的基础上我们提出了相应的改进思想，根据最小生成树路径图，我们发现有些节点处于其他若干个节点的通信路径交汇处，如节点72、106、107，这类节点存在过载使用。为避免这种情况，最大最小通信使得节点的剩余电量尽可能多，即最大化节点的最小剩余电量。基于以上的思想我们认为可以定义一个电源的开销函数。这样可以避免交叉节点的过载使用，延长整个遥测遥感网的通信寿命。

关键词：成功覆盖率；通信模型；Dijkstra算法；Floyd算法 ；最小生成树

1

一、 问题的重述

自然灾害频频发生，给人民的生命财产造成巨大的损失，因此一些国家通过在容易出现自然灾害的重点地区放置高科技的监视装置，进而建立无线传感网络的方式，帮助人们准确而及时地掌握险情的发展情况，为有效地抢先救灾创造有利条件，这对于减少人民的生命财产损失具有重大意义。

放置在同一监视区域内的这种监视装置（以下简称为节点）可以构成一个无线传感网络如附录一图1。

如果监视区域的任意一点都处于放置在该区域内某一节点的监视范围内，则称节点能覆盖该监视区域，可见研究能确保有效覆盖且数量最少的节点放置问题显然具有重要意义。网络节点间的通信设计问题也是无线传感器网络设计的重要问题之一，每个节点都有一定的覆盖范围，节点可以与覆盖范围内的节点进行通信。但是当节点需要与不在其覆盖范围内的节点通信时，需要其它节点转发才可以进行通信如附录一图2。

通过查找相关资料，建立数学模型解决以下问题：

问题一：在一个监视区域为边长b=100(长度单位)的正方形中，每个节点的覆盖半径均为r=10(长度单位)。确定至少需要放置多少个节点，才能使得成功覆盖整个区域的概率在95%以上。

问题二：在问题一所给的条件下，已知在该监视区域内放置了120个节点，它们位置的横、纵坐标如附录二表1中120个点的坐标表所示。试设计一种节点间的通信模型，给出任意10组两节点之间的通信通路，比如节点1与节点90如何通信等。

问题三：对用于监视旱情的遥测遥感网，由于地处边远地区，每个节点都只能以电池为能源，电池用尽节点即报废。实际情况下，节点的覆盖范围也会随着节点能量发生变化。针对附录二中表1的数据，从节能角度考虑设计，改进问题2中的通信模型。给出任意10组两节点之间的通信通路，比如节点1与节点90如何通信等。

二、 问题的分析

建立无线传感网络，使人们能准确而及时地掌握险情的发展情况，但到底要设置多少个节点使得成功覆盖概率较高的问题值得我们关注，同时设计一个合理有效的节点通信模型也是整个无线传感网络中的重中之重。

对于问题（1），基于给定的监视区域以及覆盖半径，要求放置最少的节点使得成功覆盖整个区域的概率在95%以上。由于给定监视区域存在边界，故可以将节点分为两大类，一类节点一定完全落在监视区域内，另一类节点只能部分落在监视区域内，这两类节点发生的概率可以由相应区域面积与总监视区域面积之比得出，同时，可以得到两类节点覆盖面积的期望值，进而可以求得随机在给定监视区域内放置节点，节点覆盖面积的期望值。可以运用概率论的知识综合两类节点的期望求解覆盖整个监视区域的概率，令该概率值大于95%即可求解。当然，还可以通过设计随机仿真实验的方法进行进一步的分析求解最少的节点数目。

对于问题（2），由于每个节点都有一定的覆盖范围，节点只可以与其覆盖范围内的节点进行通信，根据120个节点的坐标，即可得到两两节点之间的距离，于是满足节点通信条件的所有节点都可以找到。通过这样的方法，任意两节点之间的通信通路即可得出。

由前面的方法可以找到两节点的通信路径，但是路径不唯一，所以通过Dijkstra算

2

法可以求出固定起点（本文我们固定节点1为起点）到其余任意节点的最短通信路径。借鉴上述Dijkstra求特解的思路，我们又可运用Floyd算法求出任意两节点之间的最短通信路径，因此本文可以尝试用上述两种算法对模型进行进一步优化从而快速得到任意两节点之间的最短通信通路。

对于问题（3），我们需从节能角度出发，在问题（2）所得节点间最短通信路径模型的基础上，进一步考虑无线传感网络节点间通信半径与能量消耗的关系，即通信半径越长，能量消耗越多。因此，这里我们可以引用最小生成树的思想得到一个最短路径图，得到从节能角度考虑设计的任意两点间的通信路径。

三、 模型的假设与符号的说明

3.1模型的假设

（1）监视装置工作稳定，不会突然失效；

（2）每个监视装置单位感知距离内耗能相同； 3.2符号的说明

r：节点的覆盖半径；

b：正方形监视区域的边长； E(C)：节点覆盖面积的期望值； ?：监测区域的面积； n：放置的节点数目；

?：无线传感网络覆盖率；

xi：节点位置的x坐标，i=1,2,3,...,119,120； yi：节点位置的y坐标，i=1,2,3,...,119,120；

dij：节点i到节点j的距离，i=1,2,3,...,119,120，j?1,2,3,...,119,120；

k：无线传感网络的某一节点； R：节点间的通信半径

e：无线传感网络中某一节点的能量消耗；

E：无线传感网络中所有节点的能量消耗总和。

四、 模型的建立与求解

4.1问题（1）的模型建立与求解

4.1.1模型一：无线传感网络概率覆盖模型【1】

首先考虑在监测区域内部部署一些节点，这些节点构造成一个节点集合S，每个节点的覆盖面积为为E(C)，覆盖概率为E(C)/?；当节点集合为空时，放置n个节点便得

E(C)n1-），这样就得到了S不为空集的情况下，网络节到网络的覆盖率：P(S为空)=（?点的覆盖概率值：

E(C)nP(Sn)=1-（1-） （1）

?式（1）和观察到的limE(Sn)=1是一致的，它表明了当节点数目足够大时，该区域

n?? 3