为了正常的体验网站,请在浏览器设置里面开启Javascript功能!
首页 > 无线传感器网络多重覆盖问题分析

无线传感器网络多重覆盖问题分析

2010-08-04 10页 pdf 490KB 17阅读

用户头像

is_301769

暂无简介

举报
无线传感器网络多重覆盖问题分析 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn Journal of Software, Vol.18, No.1, January 2007, pp.127−136 http://www.jos.org.cn DOI: 10.1360/jos180127 Tel/Fax: +86-10-62562563 © 2007 by Journal of Software. All rights reserved. 无线传感器网络多重覆盖问题分析∗ 刘 明...
无线传感器网络多重覆盖问题分析
ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn Journal of Software, Vol.18, No.1, January 2007, pp.127−136 http://www.jos.org.cn DOI: 10.1360/jos180127 Tel/Fax: +86-10-62562563 © 2007 by Journal of Software. All rights reserved. 无线传感器网络多重覆盖问题分析∗ 刘 明 1,2+, 曹建农 2, 郑 源 2, 陈力军 1, 谢 立 1 1(计算机软件新技术国家重点实验室(南京大学),江苏 南京 210093) 2(香港理工大学 电子计算学系,香港) Analysis for Multi-Coverage Problem in Wireless Sensor Networks LIU Ming1,2+, CAO Jian-Nong2, ZHENG Yuan2, CHEN Li-Jun1, XIE Li1 1(State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210093, China) 2(Department of Computing, The Hong Kong Polytechnic University, Hong Kong, China) + Corresponding author: Phn: +86-013881880533, E-mail: wing.lm@gmail.com Liu M, Cao JN, Zheng Y, Chen LJ, Xie L. Analysis for multi-coverage problem in wireless sensor networks. Journal of Software, 2007,18(1):127−136. http://www.jos.org.cn/1000-9825/18/127.htm Abstract: Since wireless sensor networks consist of a large number of tiny sensors with limited power supply, it becomes a major concern that how to extend sensor network lifetime and maintain sufficient sensing area at the same time. To achieve this goal, a broadly used strategy is to select some sensor nodes as working nodes to cover the deployment area and at the same time turn off redundant nodes. This paper proposes a mathematical model in which only if the proportion of the sensing range of nodes to the range of the deployment area is known, the number of the nodes needed to reach the expected coverage fraction can be calculated. This work is different from the most literature studying the coverage problem because it is not based on location information of sensor nodes, and thus the cost of hardware and the energy consumption on sensor nodes for deriving and maintaining location information can be considerably reduced. The simulated experiment suggests that in random deployment strategy, the error between the expected coverage fraction and the coverage fraction derived from the simulated experiment is no larger than 2% of the expected coverage fraction; when the expected coverage fraction and the coverage fraction derived from the simulated experiment is the same, the error between the number of working nodes derived from the calculation and the number of working nodes derived from the simulated experiment is less than 5% of the number derived from the calculation. It suggests that the results are identical to the experimental results. The analytical results in this paper can be widely adopted in handling sensor deployment, topology control, and other issues. Key words: wireless sensor network; coverage fraction; multi-coverage ∗ Supported by the National Natural Science Foundation of China under Grant No.60573132 (国家自然科学基金); the National Grand Fundamental Research 973 Program of China under Grant No.2002CB312002 (国家重点基础研究发展规划(973)); the Hong Kong Polytechnic University of China Interdisciplinary/Collaborative Research Grant under Grant No.A-PF77 (香港理工大学学科合 作研究基金) Received 2005-11-22; Accepted 2006-02-24 128 Journal of Software 软件学报 Vol.18, No.1, January 2007 摘 要: 传感器网络由大量能量有限的微型传感器节点组成.因此,如何保证在足够覆盖监测区域的同时延 长网络的寿命,是一个需要解决的重要问题.为了达到这一目标,一种广泛采用的策略是选出部分能够足够覆 盖监测区域的节点作为工作节点,同时关闭其他冗余节点.提出了一个数学模型,使得只要已知监测范围和节 点感知半径的比值,就可以计算出达到服务质量期望所需要的节点数量.需要指出的是:与大部分研究覆盖的 文献不同,该研究不基于节点的位置信息,因此可以极大地降低硬件成本,并且减少节点获得和维护位置信息 的开销.模拟实验结果明:在随机部署条件下,服务质量期望与实验所得到的实际覆盖度的误差不大于服务 质量期望的 2%;而对于相同的服务质量期望和实际覆盖度,计算所得的工作节点数量与实验所得的工作节点 数量的误差小于计算数量的 5%,这表明推导出的节点数量与服务质量期望之间的关系与模拟实验的结果相 吻合.该结果可以广泛应用于传感器网络的节点部署、拓扑控制等领域中. 关键词: 无线传感器网络;覆盖度;多重覆盖 中图法分类号: TP393 文献标识码: A 随着传感器技术、嵌入式技术以及低功耗无线通信技术的发展,生产具备感应、无线通信以及信息处理 能力的微型无线传感器已成为可能.这些廉价的、低功耗的传感器节点共同组织成无线传感器网络,通过节 点间的相互协作,将其监测和感应的多种环境信息(如温度、湿度等)传送到基站进行处理.大规模的无线传感 器网络依靠成千上万的微型传感器节点来完成对目标的监测.网络中的节点可以感知周围的环境、执行简单 的计算,并且,每个节点可以与其无线传输半径内的邻居节点通信.通过自组织的方式,这些节点构成了一个 高度灵活的、低能耗的网络.通常情况下,无线传感器节点的能量由电池提供,根据应用的要求这些节点需要 在不补充能量的情况下工作几个月甚至一年.然而,由于传感器节点密集部署(密度可高达 20 nodes/m3)[1]所 带来的可扩展性、冗余以及无线信道干涉等问题,因此,必须通过有效的来合理地利用节点的能量. 传感器节点的高密度部署可能导致较大的能量开销,然而,另一方面,它也是设计节能的基础.一种 广泛使用的策略就是:通过启发式的算法[2,3]对节点的状态进行调度,利用节点的冗余性在满足覆盖要求的情 况下轮流关闭节点,从而减少能量的消耗.目前,大多数覆盖算法[4−8]是根据节点的物理位置信息或利用有向 天线获得信号达到角度(arrival of angle,简称 AOA)来计算节点的覆盖关系、选取工作节点.然而,依赖于 GPS 或有向天线这种复杂的硬件设备,不但极大地增加了节点的硬件成本和能量消耗,同时由于位置、方向等消 息的传递和计算也会导致节点能量的开销,因此,我们希望调度算法不依赖于任何地理信息.然而,没有精确 的地理信息,我们又很难测量节点间的覆盖关系,因此,关闭一个节点可能造成监测区域中出现盲区,该盲区 不在网络中任何工作节点的监测范围内.文献[9,10]都给出了不基于位置信息的覆盖方法:文献[9]给出了传 感器网络监测区域大小、节点密度和覆盖之间的关系;文献[10]讨论了一个传感器节点的感知区域内,需要有 多少个工作节点才能完全覆盖该节点的感知区域. 事实上,启发式算法很难保证在关闭节点的同时不产生盲区.因此,传感器网络提供最大覆盖的最简单方 法是使所有节点同时处于工作状态,然而,这种方法将浪费很多的能量,从而导致网络寿命减小.对于随机部 署方式而言,即使利用地理信息的启发式算法,也不能保证监测区域完全被覆盖,这是因为随机部署方式在概 率上不能保证部署的节点可以完全覆盖整个监测区域.所幸的是,绝大部分应用并不要求传感器网络一直保 持最大覆盖的状态,在一段时间间隔内产生少量的盲区是可以接受的.只要传感器网络中的工作节点对监测 区域能够维持一个合理的覆盖比,大部分的应用就都可以满足.故覆盖度可以作为衡量网络监测功能的服务 质量之一[11]:当网络的覆盖率低于某个阈值时,则认为网络不能正常工作.因此,如果能够提出一种不依赖地 理信息,并且在统计上满足应用所要求的覆盖度的启发式节点调度算法将具有非常重要的意义. 本文给出了一个数学模型,该模型描述了在随机部署方式下,节点感知半径、监测区域半径以及节点数 量与覆盖度之间的关系.通过该公式,我们可以根据监测区域半径、节点感知半径以及应用要求的服务质量 (覆盖度)来计算出达到该服务质量所需的节点数量.与文献[9]相比,我们的模型考虑了边界条件的影响,因此, 分析结果更为精确;而文献[10]只分析了一个节点的感知区域需要多少个工作节点才能覆盖,因此,其结果只 刘明 等:无线传感器网络多重覆盖问题分析 129 是本文工作的一个特例. 1 相关工作 覆盖问题是无线传感器网络中的重要问题之一.由于存在不同的传感器网络应用,对于覆盖问题的定义 也有所不同.我们认为:对于单重覆盖,传感器网络的覆盖问题可以简单地解释为监测区域中的每个位置至少 位于一个传感器节点的感知范围以内.如果要求监测区域中的每一点至少被 k个传感器所覆盖,则称为 k重覆 盖问题. 无线传感器网络一般具有高密度部署和节点能量受限的特点,通常采用工作节点密度控制算法和节点 状态调度机制,以达到在保证覆盖的前提下减小能耗和延长网络寿命的目的. 在文献[4,5]中提出求解最大覆盖集的方法,将所有的传感器节点分成若干个不相交的覆盖集(cover set), 每个集合中的节点都可以独立地完成区域监测任务,这些集合中的节点按轮次顺序执行区域监测任务.在文 献[4]中,Slijepcevic等人证明了计算最大的覆盖集是一个NP完全问题,文献[4,5]分别提出了most-constrained least-constraining算法和基于 graph-coloring近似算法.文献[4,5]提出的算法都是集中式的,并不适合传感器节 点数量众多的情况,而且两种算法都要依赖传感器节点的位置信息计算覆盖集. Xu等人在文献[6]中提出 GAF(geographical adaptive fidelity)算法.在 GAF算法中,每个节点根据自己的 物理位置信息,将整个区域划分为若干个格子(grid),其大小必须保证相邻格子中任何一对节点可以直接通 信.因此,任何时候,只需在每个格子中选择一个节点作为活动节点转发数据包,而其他节点进入节能睡眠状 态就可以实现通信.但是,GAF算法并没有考虑到网络覆盖的问题. Tian 等人在文献 [2]中提出了基于节点状态调度的分布式覆盖算法 ,其中的免职合格规则 (off-duty eligibility rule)可以根据节点的物理位置信息或利用有向天线获得信号达到角度来计算节点与其邻居的覆 盖关系,选取工作节点.很明显,依赖于 GPS 或 AOA 信息,对于传感器来说是非常耗能且昂贵的.此外,免职合 格规则没有考虑节点覆盖区域可能出现过多的重叠,使得选出的工作节点数量过多,造成额外的能耗.文献 [12]证明了这种基于节点活动调度的算法是低效的. Ye等人在文献[3]中提出了基于探测(probing)的密度控制算法 PEAS.PEAS算法是基于探测机制的,也就 是说,每个睡眠节点在一定时间内、在其探测范围内发送广播消息 PRB,任何收到消息的工作节点返回应答 消息.若节点收到应答消息,则进入睡眠状态,工作节点继续工作,直至其能量耗尽或物理失效;否则,睡眠节点 进入工作状态.节点的物理位置用于计算节点探测范围和所要求的节点密度.显然,PEAS 算法中的某些节点 可能持续工作,导致其过早地死亡,整个网络中的节点能耗不均匀,影响了覆盖质量. 文献[10]中提出了一种基于概率而不是基于位置信息的分析节点冗余的数学方法.根据该方法,节点可 以根据自身感知半径内的邻居节点数量计算出自身成为冗余节点的概率.由于不需要配备 GPS 或有向天线, 所以,节点的成本得到了控制;此外,也不需要通过消息交换来获取节点的位置信息,所以减轻了传感器网络 系统的通信开销.然而,由于绝大多数节点的感知硬件和通信部件是完全独立的两个模块,即通信半径和感知 半径不一致.因此,要知道节点感知半径中的邻居节点数量,需要有专门的硬件进行判断,这无疑要增加硬件 的成本. 从以上的介绍中可以看出:目前提出的覆盖算法大多依赖于外部基础设施,如 GPS,有向天线或者定位算 法等,这不仅使成本相对较高、耗能多,而且仍然存在其他一些问题.如依赖于 GPS的协议通常需要处理在计 算定位中的一些错误;对于室内环境,基于 GPS 的系统并不能可靠地工作,这可能需要部署其他定位系统.对 于一些定位算法,每个节点需要与灯塔节点交换大量的信息,计算出其位置,这同样需要消耗大量的能量.在 文献[12]中,Stojemenvic 对基于位置信息的算法作了一个综述,并指出获得和维护位置信息将产生很大的 开销. 在本文中,我们给出了一种有效估计节点覆盖度的数学模型,只要知道节点感知半径与区域 C 半径的比 值,就可以通过简单的计算得到区域 C 中节点数量与服务质量期望之间的关系.因此,我们的方法具有广泛的 130 Journal of Software 软件学报 Vol.18, No.1, January 2007 适用性,可以很方便地应用到节点部署、拓扑控制、负载均衡等领域中. 2 网络模型和问题陈述 2.1 部署模型 在文献[13]中,作者对以下几种通常的部署策略进行了研究:随机部署、规则部署(regular deployment)以 及计划部署(planned deployment).其中:随机部署是指部署后节点在部署区域内呈现为均匀分布;规则部署是 指置放的节点构成规则的拓扑结构,比如格子;而计划部署是指在监测现象的高发区其节点的部署密度也较 高.在计划部署中,虽然节点在部署区域内呈非均匀分布,然而在一个较小的范围内,节点的分布仍可近似为 均匀分布.因此,虽然我们的分析基于随机部署方式,但其结果依然适用于计划部署. 对于预先不知道被监测区域情况的应用场景,随机部署这种节点部署方式是合理的.为了方便理论分析, 本文假设节点被部署在一个二维的半径为 R的圆形区域 C内.事实上,我们对整个部署区域的形状并不关心, 它可以是方形或圆形,并且区域 C 可以只是整个部署区域的一个子集,也可以是整个部署区域.我们研究的焦 点在于,如何在满足覆盖度的情况下得到覆盖区域 C 所需的节点数量.我们假设节点均匀而独立地分布在区 域 C 中,并且在任意一个位置上不可能存在两个以上的节点.由上面的描述可知,节点的部署可以看作一个齐 次平面的 POISSON 点过程.基于这种假设,区域 C 中的任意一个节点落入 C 中某个子区域 S 的概率只与 S 的面积有关,即 p=||S||/||C||. 2.2 感知模型 本文的分析基于布尔感知模型,该模型被广泛应用于传感器网络的研究工作中[2,3,9,10].布尔感知模型中 每个节点都具有一个固定的传感半径,每个传感器只能够感知和发现其传感半径内的环境或者事件.并且,本 文假设所有节点的传感半径相同,且节点的感知半径 r≤R.监测区域中任意一点被覆盖,当且仅当其位于至少 一个传感器节点的感知半径内.这样,监测区域就被分为两个部分:覆盖区和盲区.覆盖区中的任意一点至少 被一个传感器节点覆盖,而盲区则是覆盖区的补集.事实上,有的应用对事件的监测需要有较高的准确度,要 求覆盖区中的任意一点至少要同时位于 K 个节点的传感半径内,否则就被作为盲点,我们称之为 K 重覆盖. 2.3 相关定义 如图 1所示,为了方便下面的讨论,我们首先给出如下定义: 定义 1. 邻域.对于任意一点 p(x,y)∈C,其邻域定义如下: ℵ(x,y)={∀(x′,y′)∈C|((x′−x)2+(y′−y)2≤r2)}. 定义 2. 中心区域(center area)C′.中心区域 C′定义如下: C′={∀(x,y)∈C|x2+y2⇐(R−r)2}. 定义 3. 非中心区域 C″.非中心区域 C″定义如下 C″={∀(x,y)∈C|x2+y2>(R−r)2}. 定义 4. 全覆盖和部分覆盖.设节点 i的感知区域是 Si,如果在所有 N个部署的传感器节点中存在一个子 集 u(例如工作节点集合),使得 则子集 u 是对区域 C 的一个全覆盖.如果子集 u 只能部分覆盖区域 C,即 ∅,则我们称集合 u是对区域 C的一个部分覆盖. ,CSiui ⊃∪∈ ≠∩∪− ∈ CSC iui 定义 5. 服务质量期望 Q.对于全覆盖和部分覆盖,其服务质量期望的定义有所不同:全覆盖条件下的服 务质量期望 Qf是指工作节点集合 u完全覆盖区域 C的概率;部分覆盖条件下的服务质量期望 Qp是指工作节 点集合 u所覆盖的区域与整个监测区域 C的比值,即 |||| C CS Q iui p ∩∪ = ∈ .我们对服务质量期望 Q的定义,很容易 从单覆盖扩展到 K覆盖.对于要求 K覆盖的服务质量期望 Q,其覆盖区中的任意一点至少同时被 K个传感器 节点监测. 刘明 等:无线传感器网络多重覆盖问题分析 131 Y r l R X rC′ C Fig.1 Illustration of neighboring area, center area and non-center area 图 1 邻域、中心区域与非中心区域示意图 2.4 问题描述 假设在监测区域 C 中随机均匀部署 N 个节点,每个节点 i(1≤i≤N)的监测范围为 Si.对于全覆盖,需要从 N 个节点中随机选取一个工作节点集合 u,使得区域 C 中每一点至少被 K 个节点覆盖的概率大于等于 Qf.对于 部分覆盖,则是从 N 个节点中随机选取一个工作节点集合 u,使得 C 中被节点覆盖的区域与整个区域 C 面积 的比值大于等于 Qp. 3 覆盖分析和数值结果 3.1 全覆盖分析 要完全 K重覆盖区域 C,则对 C中的任意点都要求在其邻域内至少存在 K个以上的节点.然而,就目前我 们所知,准确地求出完全覆盖概率表达式依然是一个难题.由于二维全覆盖概率难以准确地计算,因此我们就 寻求渐进的结果. 定理 1[14]. 设 C 是面积为 A*的凸集,S1,S2,…,Sn为相互全等,面积等于 A,周长等于 L 的凸集.假定让 Si随 机地落在 C上,则 C的每一点至少被 K块 Si覆盖的概率为(A*→∞,n/A*=ρ) q=exp{−KρA*exp(−ρA)[1+…+((ρA)K/K!)]},r=0,1,2,… (1) 特殊地,令 A*=πR2,A=πr2,我们就得到当 N个传感半径为 r的节点随机部署在区域 C时,完全 K重覆盖区 域 C的概率: Qf=exp{−KρπR2exp(−ρπr2)[1+…+((ρπr2)K/K!)]} (2) 在后面的模拟实验中,我们对 K重全覆盖式(2)的准确性进行了检验. 3.2 部分覆盖分析 对于任意一点 p(x,y)∈C,如果在其邻域内至少存在一个节点,则该点被覆盖.由于区域 C 中工作节点的分 布可以看作是一个 POISSON 点过程,所以任意节点落入点 p(x,y)邻域内的概率为 p=||ℵ(x,y)||/||C||.如图 2 所 示,C′中任意点的邻域面积为||ℵ(x,y)||=πr2,而对于 C″中任意点的邻域面积为||ℵ(x,y)||<πr2. 假设区域 C中随机均匀部署了 n个节点.对于单覆盖来说,C中任意一点 p(x,y)被覆盖的概率等于至少有 一个节点落入其邻域的概率,即 =1−(1−p)nnnCyx pn n pp n pp n p    ++−   +−   = −−∈ ...)1(2)1(1 221 }),{( n (3) 由式(3)可知:对于区域 C 中任何两点,如果其邻域的面积相同,则其被覆盖的概率相等.显然,所有与圆心 距离相等的点具有相同的邻域面积.对于区域 C 中边缘区间 C″的点,其邻域面积小于πr2.特别是属于 C 边界 上的点,其邻域面积最小,故其被覆盖的几率也最小.设位于 C 边界上的点被覆盖的几率为 pmin,显然有 pmin≤ p{(x,y)∈C}≤p{(x,y)∈C′}.对∀(x,y)∈C′,其邻域面积πr2||ℵ(x,y)||=πr2,故任意节点落入中心区域某点邻域内的概率为 132 Journal of Software 软件学报 Vol.18, No.1, January 2007 p=||ℵ(x,y)||/||C||=r2/R2.根据式(1),如果 C中随机部署了 n个节点,则对∀(x,y)∈C′,其被节点覆盖的概率为 n Cyx R rp     −−=′∈ 2 2 }),{( 11 (4) rrrr (a) p(x,y) located in area C′ (b) p(x,y) located in area C″ (a) 点 p(x,y)位于 C′ (b) 点 p(x,y)位于 C″ Fig.2 Illustration of neighboring area 图 2 邻域两种情况的示意图 定理 2. 当||C||→∞时,设节点的传感半径为 r 并且在 C 上以密度λ=n/||C||随机均匀部署,则该传感器网络 所提供的服务质量期望(单覆盖)为 .e1 2rq π−−= λ 证明:因为||C−C′||/||C||→0,因此可以忽略掉边界影响,近似地认为 C 中任意一点被覆盖的概率相同,其值 为 n Cyx R rp     −−≈∈ 2 2 )),(( 11 .当||C||→∞时,任意点 p(x,y)∈C不被工作节点覆盖的概率为 )( 2 2 )coverdnot ),(( 2 2 e1 nE R rn Cyx R rEp − ∈ =              −= 2e rπ−= λ (5) 设区域 C中没有被节点集合 u覆盖的部分用 C表示,则 C面积的期望值为 ∫∫ ∈= C CyxpCE σd||][|| )coverdnot ),(( (6) 因此,根据式(5)、式(6)可以得到工作节点集合 u覆盖的区域占整个监测区域的期望值: 2 2 e1 |||| ||||e1 |||| d 1 |||| |||| )coverdnot ),(( rrC Cyx C C C p C CE π− π−∈ −=−=−=   ∫∫ λλσ (7) 由式(7)可知,服务质量期望等价于区域 C中一点被覆盖的概率.对于大型传感器网络的设计者,可以根据 式(7)近似地计算出节点达到期望覆盖比例所需要的节点密度.在忽略边界影响的条件下可以看到:式(7)的结 果与文献[10]相同. 对于区域 C和 C′,有一个小于 1的正常数ε满足ε<||C−C′||/||C||<1.当ε足够大时,表明边界影响不能忽略,如 果继续用式(2)计算服务质量期望就会产生很大的误差.所以,为了准确地估计区域 C的服务质量期望,我们需 要准确地计算区域 C中所有点的平均邻域面积.如图 2所示,与圆心距离为 l且 l>R−r的一点 p(x,y)∈C″,其邻 域面积||ℵ(x,y)C″||为阴影部分的面积,其值为         −+−−=ℵ ∫∫ +− +− − ′′ 1 2 2 1 2 1 2 2 1 2 dd)(2||),(|| 222 222 yyRylyryx R l lrR l lrR rl C 刘明 等:无线传感器网络多重覆盖问题分析 133 2 2222 2 222222 2 2 2222 2 222222 222 4 )( 22 arcsin 4 )( 22 arcsin)( 2 1 l lrRR l lrR lR lrRR l lrRr l lrR lr lrRrRr +−−+−−+− −−−−−−+−−++π= (8) 由式(6),我们得到了一个计算区间 C″上任意一点邻域的通用表达式.显然,对于任意一点 p(x,y)∈C″,有 22 yxl += .由于区域 C″中任意一点的邻域面积是关于 l 的函数,因此我们可以用    + 22 yxf 来表示邻域 面积. 下一步,我们可以通过面积积分来得到区域 C″中所有点的平均邻域面积 Cyx ′′ℵ ),( . ))((d)(2 ))((d)(d||||d)(||||d),( 22 22 2 0 22 rRRf rRRfCfCyxfyx R rR R rR CC C −−= −π−π=′′=′′   +=ℵ ∫ ∫ ∫∫∫∫∫ − π −′′′′ ′′ ρρρ ρρρθθρρσ (9) 故整个部署区域 C中所有点的平均邻域面积为 22222 22222 /))())((),(( /))())((),((),( RrRrrRRyx RrRrrRRyxyx C C −×+−−ℵ= π−×π+−π−πℵ=ℵ ′′ ′′ (10) 所以,区域 C中所有点的平均覆盖几率,也就是服务质量期望(同理于式(7))为 n R yx q     π ℵ−= 2 ),( 1 (11) 前面我们只讨论了单覆盖,对于K覆盖来说,其覆盖区域中任意一点的邻域内,至少存在K个以上的节点, 因此被覆盖的几率为 (12) ∑ = −−−+− ∈ −=++−+−= n km mnmm n nn n knk n knk nCyx ppCpCppCppCp )1(...)1()1( 121 }),{( 其中,在||C−C′||/||C||→0时,有 2 2 R rp = ;在不能忽略掉边界条件时,有 . 2 ),( R yx p π ℵ= 3.3 部分覆盖的数值结果 本节中,我们给出了部分覆盖的数值结果.表 1 给出了区域 C 半径 R 与节点感知半径 r 在不同比值情况 下,平均邻域面积与最大邻域面积之比.可以看到:如果 r和 R的比值越大,则 C中所有点的平均邻域面积与最 大邻域面积的比值越小.当 R=r 时,平均邻域面积与最大邻域面积的比值只有 0.578 1.显然,在此种情况下,计 算服务质量 q 时不能忽略边界影响;而当 r<标准
从全覆盖降低为部分覆盖,则整个网络中所需的工作节点的密度会大为降低,从而极大地节省了整个 网络的能量. 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 SC AC Q oS 15 100015 200015 The number of working nodes Fig.6 Comparing SC with AC (r/R=0.01) 图 6 全覆盖实验结果和分析结果比较(r/R=0.01) 5 小 结 本文中,我们对随机部署方式下的覆盖问题进行了研究,并且提出了一个数学模型,使得只要已知监测范 围和节点感知半径的比值,就可以计算出达到服务质量期望所需要的节点数量.据目前所知,还没有类似的文 献研究此种情况下节点数量与服务质量期望之间的关系.需要指出的是:与大部分研究覆盖的文献不同,本文 的研究不基于节点的位置信息,因此可以极大地降低硬件成本,并且减少节点获得和维护位置信息的开销. References: [1] Shih E, Cho S, Ickes N, Min R, Sinha A, Wang A, Chandrakasan A. Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks. In: Christopher R, Mahmoud N, Michele Z, eds. Proc. of the 7th Annual Int’l Conf. on Mobile Computing and Networking (MobiCom 2001). Rome: ACM Press, 2001. 272−287. 136 Journal of Software 软件学报 Vol.18, No.1, January 2007 [2] Tian D, Georganas N. A coverage-preserving node scheduling scheme for large wireless sensor networks. In: Raghavendra CS, Sivalingam K, eds. Proc. of the 1st Int’l Workshop on Wireless Sensor Networks and Applications (WSNA 2002). Atlanta: ACM Press, 2002. 32−41. [3] Ye F, Zhong G, Lu S, Zhang L. PEAS: A robust energy conserving protocol for long-lived sensor networks. In: McKinley PK, Shatz S, eds. Proc. of the 23nd Int’l Conf. on Distributed Computing Systems (ICDCS). Providence: IEEE Press, 2003. 28−37. [4] Slijepcevic S, Potkonjak M. Power efficient organization of wireless sensor networks. In: Glisic S, ed. Proc. of the IEEE Conf. on Communications. Helsinki: IEEE Press, 2001. 472−476. [5] Cardei M, MarCallum D, Cheng X, Min M, Jia X, Li D, Du D. Wireless sensor networks with energy efficient organization. Journal of Interconnection Networks, 2002,3(3-4):213−229. [6] Xu Y, Heidemann J, Estrin D. Geography-Informed energy conservation for ad hoc routing. In: Proc. of the 7th Annual ACM/IEEE Int’l Conf. on Mobile Computing and Networking. Rome: ACM Press, 2001. 70−84. [7] Zhang H, Hou JC. Maintaining scheme coverage and connectivity in large sensor networks. Wireless Ad Hoc and Sensor Networks: An International Journal, 2005,1(1-2):89−123. [8] Wang X, Xing G, Zhang Y, Lu C, Pless R, Gill CD. Integrated coverage and connectivity configuration in wireless sensor networks. In: Proc. of the 1st Int’l Conf. on Embedded Networked Sensor Systems. New York: ACM Press, 2003. 28−39. [9] Liu B, Towsley D. A study on the coverage of large-scale sensor networks. In: Proc. of the 1st IEEE Int’l Conf. on Mobile Ad-Hoc and Sensor Systems. Fort Lauderdale: IEEE Press, 2004. http://www.ececs.uc.edu/~cdmc/mass/mass2004/35142.pdf [10] Gao Y, Wu K, Li F. Analysis on the redundancy of wireless sensor networks. In: Sivalingam KM, Raghavendra CS, eds. Proc. of the 2nd ACM Int’l Conf. on Wireless Sensor Networks and Applications (WSNA 2003). San Diego: ACM Press, 2003. 108−114. [11] Meguerdichian S, Koushanfar F, Potkonjak M, Srivastava M. Coverage problems in wireless ad-hoc sensor networks. In: Proc of the IEEE INFOCOM. Anchorage: IEEE Press, 2001. 1380−1387. [12] Stojmenovic I. Position based routing in ad hoc networks. IEEE Communications Magazine, 2002,40(7):128−134. [13] Tilak S, Abu-Ghazaleh N, Heinzelman W. Infrastructure tradeoffs for sensor networks. In: Raghavendra CS, ed. Proc. of the 1st Int’l Workshop on Wireless Sensor Networks and Applications (WSNA 2002). Atlanta: ACM Press, 2002. 49−5
/
本文档为【无线传感器网络多重覆盖问题分析】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索