基于贪婪算法的无线传感器网络中继节点布局的研究_王翥_吕翠翠_陈建辉

格式：pdf
大小：475.21 KB
文档页数：4

下载文档原格式

贪婪寻优算法在中继节点布局中的应用

算法所忽视的布局完成后网络整体能耗的问题，出了基于最小通信网络距离因子的针提布局算法评价新标准，同时将中继节点布局禁区、通信路径不可逆等约束条件。解决方法上，采用了基于贪婪寻优算法的中继节点布局算法，实现了无线传感器网络中继节点的多约束容错性布局。仿真实验表明，出的基于贪婪寻优算法的提中继节点布局算法与常规中继节点布局算法相比，降低通信网络整体能耗以及保证能耗均衡性方面具有明显的优势。在关键词：中继节点布设禁区；通信网络距离因子；贪婪寻优算法；通信容量；无线传感器网络
中图分类号：Ｐ９Ｔ３３文献标识码：Ａ文章编号：０２—１４（０１００００１０８１２１）５— １６— ３
ＲｅａｄｓＰａｅｅｔＢａｅｎＧｒｅｙＯｐｉｚｔｏｇｒｔｍｌｙＮｏｅｌｃｍｎｓｄｏｅｄｔｍｉａｉｎＡｌｏｉｈ
ＷＡＮＧＺｕ，ＷＥＩＤｅｂｏｈ —ａ
（ｃｏｌｆｎｏｍａｉｎＳｉｎｅａｄＥｇｎｅｉｇＨａｂｎＩｓｔｔｆｅｈｏｏｙＡｅＨａ，ｅｉ２４０，ｈｎ）Ｓｈｏｆｒｔｃｃｎｎｉｅｒ，ｒｉｎｔｕｅｏｃｎｌｇｔｉｉＷｉ，６２９ＣｉａｏＩｏｅｎｉＴＷＨａ
２１正０１
仪表技术与传感器
ＩｓｕｎＴｃｎｑｅａｄＳｎｏｎｔｍｅｔｅｈｉｕｎｅｓｒｒ
２】０ｌ
第５期
Ｎｏ５．

基于嵌入式系统的无线传感器网络的应用研究

湖南文理学院课程设计报告课程名称：嵌入式系统课程设计专业班级：自动化2班学生姓名：**指导教师：***完成时间：报告成绩：序基于嵌入式系统的无线传感器网络的应用研究随着半导体技术、传感器技术、嵌入式技术以及通信技术的飞速发展，具有感知、计算、存储和通信能力的无线传感器网络的应用越来越广泛。

无线传感器网络作为一种嵌入式设备能够实时监测、感知和采集网络分布区域内监视对象的各种信息，并加以处理。

本文提供了一种基于CC2420的无线传感器网络的硬件节点设计方案,通过选择芯片,设计硬件接口,构建了一个完整的无线传感器网络节点。

经仿真调试,该节点在试验中应用良好,电路板可以实现两个节点间的通信,能由LED指示发送、接收或应答信息,基本达到了设计要求,在煤矿监控系统的实验中应用良好,能采集精度较高的温度、压力等数据信息,并实现准确的数据交互,实现了传感器网络所需的外形小、集成度高、低功耗,为将来实际应用研究提供了一个实验平台,具有一定的应用价值。

目录1.设计要求 (2)2.设计的作用与目的 (2)3.无线传感器网络应用研究的设计方案 (4)3.1 体系结构 (4)3.2 节点结构 (5)4.系统硬件设计 (5)4.1 无线传感器网络节点组成及工作流程 (5)4.2 无线传感器网络节点设计 (6)4.2.1 处理器模块 (7)4.2.2 通信模块 (8)4.2.3 能量供应模块 (11)5.设计流程 (11)6．心得体会及建议 (15)6.1 心得体会 (15)6.2 建议 (15)7．参考文献 (16)1.设计要求无线传感器网络是集成了传感器、嵌入式系统、网络和无线通信四大技术而形成的一种全新的信息获取和处理技术它是一种新型的无基础设施的无线网络能够实时监测、感知和采集各种环境或监测对象的信息并对其进行处理、传送到需要这些信息的用户。

2.设计的作用与目的无线传感器网络在环境、健康、家庭和其他商业领域有广阔的应用前景，在军事、空间探索和灾难拯救等特殊领域有其得天独厚的技术优势。

无线传感器网络中继节点的布局算法

ｓｏｌｖｅｔｈｉｓｐｒｏｂｌｅｍ，ｃｏｎｓｔｒａｉｎｔｃｏｎｄｉｔｉｏｎｓｗｅｒｅａｄｄｅｄｔｏｔｈｅｒｅｌａｙｎｏｄｅｐｌａｃｅｍｅｎｔ．Ｔｈｅｐａｐｅｒｐｒｏｐｏｓｅｄａｒｅｌａｙｎｏｄｅｐｌａｃｅｍｅｎｔ印一ｐｒｏａｃｈｂａｓｅｄｏｎｇｒｅｅｄｙａｌｇｏｒｉｔｈｍａｎｄｒｅａｌｉｚｅｄｔｈｅｍｉｎｉｍｕｍｅｎｅｒｙｇｃｏｎｓｕｍｐｔｉｏｎｉｎｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓｔｈｒｏｕｇｈｔｈｅｌｏｃｌａｏｐｔｉ — ｍｕｍｇｒｅｅｄｙｓｔｒａｔｅｙ．ｇＡｃｃｏｒｄｉｎｇｔｏｔｈｅｒｅｇｅｄｙａｌｇｏｒｉｔｈｍ，ｔｈｅｔｈｅｏｒｅｔｉｃａｌａｎａｌｙｓｉｓａｎｄｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｐｒｏｖｅｔｈａｔｔｈｅｎｕｍｂｅｒｏｆｒｅｌａｙｎｏｄｅｉＳｆｅｗｅｒ．ＴｈｅｔｏｔｌａｅｎｅｒｙｇｃｏｎｓｕｍｐｔｉｏｎｏｆＷＳＮｉＳｌｅｓｓ．Ｋｅｙｗｏｒｄｓ：ｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ；ｒｅｌａｙｎｏｄｅｐｌａｃｅｍｅｎｔ；ｇｒｅｅｄｙａｌｇｏｒｉｔｈｍ；ｃｏｎｓｔｒａｉｎｔｃｏｎｄｉｔｉｏｎｓ

解决无线传感器网络能量洞问题的贪婪算法

解决无线传感器网络能量洞问题的贪婪算法
宋超;刘明;龚海刚
【期刊名称】《计算机工程与应用》
【年(卷),期】2009(45)15
【摘要】无线传感器网络中的能量洞问题是影响网络寿命的关键因素之一.在基于环模型的多跳传感器网络中,通过优化所有环的传输距离可以有效地延长网络寿命.提出了一种近似的贪婪算法(ASGT),该算法将最优传输距离序列问题转化为最优生成树问题,在降低搜索(算法)复杂度的同时得到与最优解近似的结果.模拟实验证明了采用ASGT算法的网络寿命逼近于理想最优序列下的网络生命时间,并且与已有的文献算法相比,ASGT可以延长网络寿命两倍以上.
【总页数】5页(P24-27,60)
【作者】宋超;刘明;龚海刚
【作者单位】电子科技大学,计算机科学与工程学院,成都,610054;电子科技大学,计算机科学与工程学院,成都,610054;电子科技大学,计算机科学与工程学院,成
都,610054
【正文语种】中文
【中图分类】TP393
【相关文献】
1.中继节点解决无线传感器网络的能量空洞问题 [J], 陈碧云;张萍;慧聪
2.无线传感器网络解决能量空洞问题综述 [J], 王东方;齐小刚
3.WSN中PMRC模型能量洞问题的解决策略研究 [J], 李倩倩;刘方爱;丁鼎
4.负载相似节点分布解决传感器网络能量洞问题 [J], 李巧勤;刘明;杨梅;陈贵海
5.放置中继节点解决无线传感器网络能量空洞问题 [J], 傅菊平;王东方;齐小刚因版权原因，仅展示原文概要，查看原文内容请购买。

无线传感器网络节点的设计方法与实现

2018年第3期2018年第3期时代农机TIMES AGRICULTURAL MACHINERY第45卷第3期Vol.45No.32018年3月Mar.2018无线传感器网络节点的设计方法与实现王云鹤，王忠宝(,132000)摘要：针对目前无线传感器网络节点设计过程存在的问题，文章从实践角度出发，分析了无线传感器网络节点的设计方法，并提出了设计实现控制的方法策略，其目的是为相关建设者提供一些理论依据。

结果表明，针对无线传感器网络节点电源能量不足问题，应配备能量供应模块与USB 作为设计控制对策，以促进现代化经济建设的全面发展进程。

关键词：无线传感器；网络节点；硬件设计基金项目：基于虚拟仪器的高职电信类专业课程实训平台开发研究，2017ZCY129，吉林省教育厅。

作者简介：王云鹤（1981-），女，吉林人，硕士，讲师，主要研究方向：电子信息工程。

无线传感器网络节点设计的科学有效性，将会对所处通信行业的快速发展进程带来影响。

为此，相关人员应着手进行优化控制，即将现有的科学技术成果更多地作用于实践，以提高节点硬件设计的合理性。

如此，无线传感器的网络节点就能为数据采集、传输与实际使用提供安全可靠性的运行控制。

故，相关人员应将其作为重点科研对象，即通过硬件设计实例，来提高设计控制的合理性，最终实现促进经济建设的全面发展进程目标。

1无线传感器网络节点设计方法与实现的现实意义作为由大量无线传感器节点组成的无线传感器网络，其节点的组成元素为：传感器采集数据、芯片处理数据接收以及传感器采集数据处理。

当其经无线射频芯片后，就能以无线传输与接收的方式，来使数据信息的传输运行具备爱无线组网功能。

此外，作为编程接口与电源，USB 的接口应将一线硅序列号看成节点的唯一标识。

当Flash 的芯片作用于数据信息的存储时，JTAG 口可作用于编程与调试处理。

总的来说，无线传感器网络节点技术的运用，将提升数据传输的有效性。

相关人员应在明确无线传感器网络节点设计方法应用要点的情况下，对实现过程进行分析控制，以促进所处通信行业的快速稳定发展。

基于多目标觅母算法的无线传感器网络中继节点部署优化方法[发明专利]

专利名称：基于多目标觅母算法的无线传感器网络中继节点部署优化方法
专利类型：发明专利
发明人：张军,钟竞辉
申请号：CN201310171937.0
申请日：20130425
公开号：CN103249179A
公开日：
20130814
专利内容由知识产权出版社提供
摘要：无线传感器网络的中继节点部署优化是提高无线传感器网络寿命和降低网络建造成本的重要技术。

本发明将多目标觅母算法运用于优化无线传感器网络的中继节点部署策略，涉及无线传感器网络和智能计算两大领域。

发明的方法采用多目标觅母算法优化无线传感器网络中各个中继节点的位置，从而最大化网络的整体寿命和最小化中继节点的数目。

在本发明的算法中引入了三个新颖的与问题相关的局部优化操作，有效提高了算法的优化效率。

以多个具有不同传感器规模的网络进行仿真测试，证明了本发明的高效性。

申请人：中山大学
地址：510275 广东省广州市海珠区新港西路135号
国籍：CN
更多信息请下载全文后查看。

基于异步深度强化学习的无线传感器网络拓扑优化方法[发明专利]

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号 (43)申请公布日 (21)申请号 202010641920.7(22)申请日 2020.07.06(71)申请人天津大学地址 300072 天津市南开区卫津路92号(72)发明人邱铁　陈宁　李克秋　周晓波　赵来平　张朝昆　(74)专利代理机构天津市北洋有限责任专利代理事务所 12201代理人刘子文(51)Int.Cl.H04W 16/18(2009.01)H04W 24/02(2009.01)H04W 24/06(2009.01)G06K 9/62(2006.01)G06N 3/08(2006.01)H04W 84/18(2009.01)(54)发明名称基于异步深度强化学习的无线传感器网络拓扑优化方法(57)摘要本发明公开一种基于异步深度强化学习的无线传感器网络拓扑优化方法，利用无标度网络模型的规则生成初始化的无线传感器网络拓扑结构；压缩无线传感器网络拓扑结构；初始化异步深度强化学习模型；训练与测试阶段；在训练阶段，首先对无线传感器网络拓扑结构进行序列化，用一个行向量来表示无线传感器网络拓扑结构；然后，网络拓扑结构行向量分别输入到不同的本地网络训练模型中；其次，本地网络训练模型中包含两个神经网络模型，分别是动作选取策略网络和策略评估网络；测试阶段，全局网络训练模型对测试数据集进行测试评估；重复步骤1、2、3和4；直至最大的迭代次数。

权利要求书1页说明书4页附图1页CN 111935724 A 2020.11.13C N 111935724A1.基于异步深度强化学习的无线传感器网络拓扑优化方法，其特征在于，包括以下步骤：步骤1.利用无标度网络模型的规则生成初始化的无线传感器网络拓扑结构；随机部署节点，新加入的无线传感器网络节点按照边密度参数进行连接；新加入的节点优先连接之前已存在的节点，保证无线传感器网络能够最大程度的描述现实世界的网络拓扑特征，同时固定节点的地理位置；每个节点具有相同的属性；步骤2.压缩无线传感器网络拓扑结构；无线传感器网络中节点的信息包括节点ID、坐标、通信范围和邻居节点；无线传感器网络中节点的信息保存到中心服务器；采用邻接矩阵的上三角部分将无线传感器网络拓扑结构转换为拓扑状态行向量；其次，剔除非邻居节点的信息，进一步的降低存储无线传感器网络拓扑结构的空间；步骤3.初始化异步深度强化学习模型；根据服务器的CPU核心数，每个CPU核初始化一个基于深度强化学习框架的本地网络训练模型，同时这些本地网络训练模型共享相同的内存空间，并初始化一个全局网络训练模型与其他本地网络训练模型共享模型参数；本地和全局网络训练模型的输入层和输出层的神经元个数根据无线传感器网络拓扑结构的行向量大小设置；随机初始化本地和全局网络训练模型的参数，初始化的参数是相同的；步骤4.训练与测试阶段；在训练阶段，首先对无线传感器网络拓扑结构进行序列化，用一个行向量来表示无线传感器网络拓扑结构；然后，网络拓扑结构行向量分别输入到不同的本地网络训练模型中；其次，本地网络训练模型中包含两个神经网络模型，分别是动作选取策略网络和策略评估网络；动作选取策略网络根据输入层的数据输出选取的优化动作，策略评估网络用于评估上述动作选取策略的优劣，同时累计每次的学习经验并更新本地网络训练模型的参数；最后，每个本地网络训练模型每隔一段时间异步地与全局网络训练模型共享网络参数；测试阶段，全局网络训练模型对测试数据集进行测试评估；步骤5.重复步骤1、2、3和4；直至最大的迭代次数；上述过程中，当本地和全局的网络训练模型的训练效果不再变化时，认为达到最优结果；重复该实验，选取最优结果的平均值作为最终实验的结果。

基于邻域旋跳迭代机制的无线传感器网络节点定位

基于邻域旋跳迭代机制的无线传感器网络节点定位曹世华;王琦晖;王李东【摘要】针对无线传感器网络(WSN)测距过程中的多维动态弹性测距问题,提出一种基于邻域旋跳迭代机制的节点定位算法.对WSN中的节点进行邻域聚类,将一阶邻域节点与二阶邻域节点作为网络邻域,根据邻域半径的排斥与吸引情况实现网络节点的定位,并通过迭代机制实现误差的最小化,最终获得精确的节点位置坐标.仿真结果表明,与基于RSLM机制的节点定位算法和SOCP网络节点定位算法相比,该算法能有效降低多维测距中的节点位置误差和网络控制开销,并提高节点定位精度和网络分组投递率.【期刊名称】《计算机工程》【年(卷),期】2016(042)007【总页数】6页(P94-99)【关键词】无线传感器网络;邻域旋跳;邻域聚类;节点定位;多维测距;网络分组投递率【作者】曹世华;王琦晖;王李东【作者单位】杭州师范大学钱江学院物联网研究中心,杭州310036;杭州师范大学钱江学院物联网研究中心,杭州310036;杭州师范大学钱江学院物联网研究中心,杭州310036【正文语种】中文【中图分类】TP393中文引用格式:曹世华，王琦晖，王李东.基于邻域旋跳迭代机制的无线传感器网络节点定位［J］.计算机工程，2016，42(7):94-99.英文引用格式:Cao Shihua，W ang Qihui，W ang Lidong.W ireless Sensor Network Node Localization Based on Iterative M echanism of Neighborhood Rotation and Hopping［J］.Computer Engineering，2016，42(7):94-99.随着集成电路工艺和芯片制造产业的不断发展，无线传感器网络节点的数据处理能力及工作稳定程度也不断提高，现有无线传感器网络节点在进行数据采集与汇聚的同时，对周围环境的若干目标进行测量、定位和跟踪［1］。

基于干扰模式的无线传感器网络链路调度算法

基于干扰模式的无线传感器网络链路调度算法
王媛丽;刘湘辉;殷建平;景宁
【期刊名称】《计算机工程与科学》
【年(卷),期】2007(029)009
【摘要】传感器网络把各种各样的微型传感器设备通过Ad Hoc网络连接起来,以便完成某些特定任务.但是,由于Ad Hoc无线网需要通过共享信道来实现节点间的通信,所以本文基于节点之间可能存在的信道干扰研究了:给定一个源和目的节点对的集合{(si,ti)},怎样在链路层上对从源到目的的数据流进行调度,以使带宽资源得到充分的利用,并设计了链路的调度算法.
【总页数】4页(P94-96,109)
【作者】王媛丽;刘湘辉;殷建平;景宁
【作者单位】国防科技大学计算机学院,湖南,长沙,410073;国防科技大学计算机学院,湖南,长沙,410073;国防科技大学电子科学与工程学院,湖南,长沙,410073;国防科技大学计算机学院,湖南,长沙,410073;国防科技大学电子科学与工程学院,湖南,长沙,410073
【正文语种】中文
【中图分类】TP393
【相关文献】
1.Mesh模式下基于最小干扰流量的带宽调度算法 [J], 徐雅静;李智涛;钟秀芳;徐惠民
2.基于分层聚类和干扰对齐的MIMO链路调度算法 [J], 熊最;王可人;金虎;钱锋
3.MIMO-pipe模型下基于干扰对齐的链路调度算法 [J], 熊最;王可人;金虎
4.基于链路质量的无线传感器网络抗干扰路由协议 [J], 王境;徐桢;刘晓春
5.无线传感器网络中基于功率控制的链路调度算法研究 [J], 王鲜;李金宝;张德升;任倩倩
因版权原因，仅展示原文概要，查看原文内容请购买。

基于贪婪思想的二阶段无线传感器网络定位算法

基于贪婪思想的二阶段无线传感器网络定位算法孟颍辉;陈剑;闻英友;赵宏【摘要】Using optimization algorithm to solve the node localization problem has become a research focus .This paper makes deep analysis on the distance relationship between two successive localization results and designs a neighborhood function , and then proposes the greedy localization algorithm based on greedy idea .The proposed algorithm is divided into two phases .In the first phase ,a set of estimated positions is generated based on the greedy iterative optimization .In the second phase ,some unknown nodes will be elevated to anchor nodes ,and the first phase is executed again .The second phase is repeated until there is no node that can be elevated to an anchor node .Finally ,the experimental results show the proposed algorithm achieves more accurate result and take less time than the existing optimization localization algorithms .%近些年来，将优化算法应用到节点定位问题当中成为了一个研究热点。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

Misra 等人[10-12]提出近似比例为 O(1) 的多项式时间近似算法，保证网络中放置的中继节点数目最少。上述文献在 RN 数目、WSN 整体能量消耗等方面对 RN 布局进行研究，对于具有线性区域的 WSN，本文在 RN 能量不受限的情况下，研究 WSN 两层中继节点布局算法，即 SN 感知、采集数据，不转发其它邻居节点的数据， RN 只转发邻居节点的数据，本身不采集数据。 WSN 中继节点布局问题是 NP-hard
网络出版时间：2013-09-10 17:10 网络出版地址：/kcms/detail/51.1196.TP.20130910.1710.076.html 优先出版计算机应用研究第 31 卷
基于贪婪算法的无线传感器网络中继节点布局的研究
王翥，吕翠翠，陈建辉
-------------------------------[6] [5]
7-近似算法和多项式时间 (5
) -近似算法，其中，是大于零
的任意常数，这两种近似算法通过放置最少数目的中继节点保证网络连通，只适用于要求 1-连通的情况。基于最优生成树的原理，Lu.K 等人
[7-8]
提出一种中继节点最小功耗布置算法，同
（哈尔滨工业大学（威海）信息与电气工程学院，山东威海 264209）摘
＊
要：无线传感器网络中的节点通常由电池供电，由于节点固有功率的限制，通信范围有限。为实现远距离的无线通
信，在网络中添加中继节点，采用多跳路由传输数据。对于中继节点的布局问题，依据线性结构使网络整体能量消耗最小的特征，提出一种中继节点贪婪布局算法。该算法通过最近贪婪策略、中继节点通信容量、传感器节点数据转发跳数等约束方法限制中继节点的布局位置。理论分析和实验验证了该算法能够有效减少能量消耗，延长网络寿命。关键词：无线传感器网络；中继节点；线性结构；网络寿命中图分类号：TP393.02 文献标志码：A
（7）
本文研究无数据聚合的 RN 布局，如图 2(b)所示，离 sink 较远的 SN，经 RN 逐跳转发数据，通过限制 SN 下一跳 RN 的通信容量，保证 SN 与 sink 之间 RN 承担的数据量相同，减少 sink 周围 RN 承担数据量过重、时延较长的现象。
vi
vi
vj
1
e
vi
vi
1
在两层中继节点布局问题中， SN、 RN、 sink 满足公式（1 ） ~公式（4）。f (vi , v j ) 0 （1）
m} ，
vi (1
i
编号为 i 的 SN，v j (n 1 n) ：
j
n m) ：编号为 j
vi v j ；
的 RN， v0 ：sink； (2). d (vi , v j ) ： vi , v j 之间的欧几里得距离， d (vi , v j ) (3).当且仅当 d (vi , v j ) 一条边 (vi , v j )
r （ r ：通信半径)时， vi 与 v j 之间有
E；
(4). f (vi , v j ) ：从 vi 到 v j 的数据流； (5). C (v j ) ： v j 的通信容量， w(vi ) ： v j 的流量负荷（ v j 转发的流量）， RC (v j ) ： v j 冗余容量， RC (v j ) C (v j ) w(vi ) ； (6). E0 ：SN 的初始能量； (7). e(vi ) : vi 的能量消耗； (8). Etotal
时该课题组基于平衡传感器节点或中继节点的功耗，推导出一个中继节点密度函数，根据密度函数在感知区域放置中继节点。崔素辉等人[9] 通过添加最少数目的 RN，设计出时间复杂度为
O(n5 k 2 ) 的近似算法，保证传感器节点、基站之间均存在
k (k
2) 条不相交路径。对于单层受限的中继节点布局问题，
hop _ count _ max(vi , v0 ) d (vi , v0 ) d0
1 1 两层中继节点布局模型
用图 G
(V , E ) 表示 WSN， V 是顶点集； E 是 G 中所
有边的集合。不失一般性，文中符号定义如下： (1). V ：SN、RN、sink，即 V {v0 , v1 , v2 ,..., vn , vn 1,..., vn
vj
f(v v) 0 ,k
0 (1 k
n
m)
（2）（3）（4）
v0
v0
f (vi , vk )
0(1
k
n)
( f (v j , vk ) f (vh , v j )) 0(n 1 k n m,1 h n m)
(a)数据聚合
(b)无数据聚合
对于距离为 d ，长度为 l bit 的信息，发送所消耗的能量如公式（5）所示。（5） eTx (v j ) (1 2 d n0 ) l 节点接收 l bit 信息所消耗的能量如公式（6）所示。
0 引言
无线传感器网络(Wireless Sensor Networks， WSN)是当前国际上备受关注、多学科交叉的一个新兴前沿热点研究领域[1]。它由大量的具有通信能力、计算能力的微型传感器节点（Sensor Node，SN）组成，能够实时监测、感知和采集网络分布区域内各种环境或监测对象的信息，并将处理后的数据以多跳的方式传送到终端用户，实现物理世界、计算机世界和人类社会三元世界的连通。在国防军事、国家安全、交通管理、医疗卫生等领域有广阔的应用前景和巨大的应用价值[2-3]。由于受到体积、价格和电源供给等因素的限制，SN 的处理能力、存储能力相对较弱[4]，通常只与其通信范围内的邻居节点进行通信，如果访问通信范围以外的其它节点，需要借助中继节点（Relay Node，RN），这样 SN 经过一个或多个 RN 将采集并处理的数据传送至 sink 节点，实现远距离的通信和两层中继节点布局问题，Lloyd 等人
d 0 n0
vj
v0
1 (n0 1) 2
图 3 SN 选择 RN 的示意图根据公式（8）可知：
0 0
0 2
在 WSN 两层中继节点布局中，如图 1 所示，WSN 的能量消耗：
Etotal (
1 n0 2 d1 )
图 2 RN 布局中的数据聚合如图 3 所示，传感器节点 vi 选择下一跳中继节点 v j 转发数据时，制定一种贪婪策略，如公式（8）所示， SN 在其通信范围内的邻居节点中，选择比自身更接近 sink 的 RN 作为下一跳。 d (vi , v0 ) d (v j , v0 ) （8）
vi
0 1 2
eRx (v j ) l
式中： 1 、 2 、是系统参数； n0 为路径损耗因子，
（6）
n0 [2, 4] 。
定理 1 在 SN、sink 和跳数 hop _ count 固定的情况下，RN 放置在 SN 与 sink 之间的连线上，且相邻两节点之间的距离相等时，整体能量消耗最小[7]。定理 2 最优跳数 hop _ countopt 是 d / d0 或 d / d0 [7]，其中
优先出版
计算机应用研究
d1
SN RN RN
第 31 卷
dp
Sink
问题，难以在有限的时间求出最优解。贪婪算法是一种求最优解的简单、迅速的设计技术，该算法容易设计、实现并且节省时间，它通常包含一个用以寻找最优解的迭代过程，本文采用贪婪算法部署 RN，实现能量消耗小的目标。
图 1 线性结构由于 SN 与 sink 之间的距离 d 通常不是 d 0 的整数倍，最优跳数 hop _ countopt 是 d / d0 或 d / d0 。因此定理 1 和定理 2 对于 WSN 两层中继节点布局保证网络整体的能耗最小也成立。如果在 SN 和 sink 之间的连线上按照定理 1、定理 2 放置 RN，形成的网络拓扑结构类似于星型，WSN 整体的能量消耗最小，然而需要放置的 RN 数目较多，为此，本文选取 RN 作为簇头节点，通过贪婪策略选择其通信范围内的子节点作为成员节点。我们限制 SN 到 sink 的最大跳数、RN 选择子节点的标准，避免 SN 的下一跳比自身离 sink 更远，规定 vi 到 sink 的最大跳数 hop _ count _ max(vi , v0 ) 。
Research on relay node placement based on greedy algorithm in wireless sensor networks
WANG Zhu, LV Cui-cui, CHEN Jian-hui
(School of Information & Electrical Engineering, Harbin Institute of Technology At Weihai, Weihai, 264209, Shandong, China) Abstract: Sensor nodes in wireless sensor network are usually powered by battery, which has limited energy supply. Because of intrinsic power limitation, the communication range of sensor nodes is restricted.To realize the long-distance wireless communication, relay nodes are added in wireless sensor network (WSN), and multi-hop routing is adopted to transmit the data. For the problem of relay node placement, the paper presented a relay node greedy placement algorithm on the basis of the characteristic of linear structure, which could make overall energy consumption of the network minimal, and the algorithm used constraints methods, such as greedy strategy, relay node communication capacity and data forwarding hop count of sensor nodes, to astrict the locations of relay nodes. The theory and experiment verify the greedy algorithm can effectively reduce the energy consumption and extend the network lifetime. Key Words: wireless sensor network; relay node; linear structure; network lifetime