无线传感器网络最小覆盖集的贪婪近似算法

网络生命期是限制无线传感器网络发展的一个瓶颈.在保证网络监控性能的前提下,仅调度部分节点工作而让其余节点处于低功耗的休眠状态,可以有效节省能耗,延长网络生命期.节点调度的目标是寻找一个能够覆盖监控区域的最小节点集合,这是一个NP难问题,目前,其近似算法的性能较低.提出了一种基于贪婪法的最小覆盖集近似算法,在构造覆盖集的过程中,优先选择扩展面积最大的有效节点加入覆盖集.理论分析表明,该算法能够构造出较好的覆盖集,时间复杂度为O(n),其中,n为初始节点总数.实验数据表明,该算法的性能要优于现有算法,得到的覆盖集的平均大小比现有算法减小了14.2%左右,且执行时间要短于现有算法.当初始节点分布较密时,该算法得到的平均覆盖度小于1.75,近似比小于1.45.     

一种基于拓扑势的网络社区发现方法

从数据场思想出发,提出了一种基于拓扑势的社区发现算法.该方法引入拓扑势描述网络节点间的相互作用,将每个社区视为拓扑势场的局部高势区,通过寻找被低势区域所分割的连通高势区域实现网络的社区划分.理论分析与实验结果表明,该方法无须用户指定社区个数等算法参数,能够揭示网络内在的社区结构及社区间具有不确定性的重叠节点现象.算法的时间复杂度为O(m+n^3/γ)～O(n²),n为网络节点数,m为边数,2<γ<3为一个常数.     

一类实际网络中的最小截算法

讨论了节点和边都有容量限制的无向平面网络中的两点间的最小截问题.传统方法是把节点和边都有容量的网络中的最小截问题转化为只有边有容量的问题,但该方法用在平面网络时不能保持网络的平面性,因此网络的平面性不能得到利用.使用传统方法的计算时间为O(n²logn)(其中n为网络的节点数).给出了可以充分利用网络平面性的方法.对源和汇共面的s-t平面网络,把最小截问题转化为平面图上两点间的最短路径问题,从而可以得到O(n)时间的算法;对一般的平面网络,给出了新的将节点和边都有容量的问题转化为仅边有容量问题的方法,这种转化方法不破坏网络的平面性,从而可以利用平面网络中仅边有容量问题的计算方法,使原问题在O(nlogn)时间内获得解决.     

一维传感网中混合数据传输的能量均衡

无线传感器网络的固有通信特征会引发能耗不均衡现象,进而产生能量空洞问题;混合数据传输是新近提出的一种能量空洞避免策略,其能量均衡性能主要取决于各节点的传输概率.然而,传输概率的设置还缺乏相关理论模型的指导,而且在节点传输距离受限的条件下能否通过混合传输策略实现全网能量均衡,还有待进一步研究.将一维网络中混合传输策略的能量均衡问题转化为传输概率的优化分配问题,通过相应的形式化模型,推导传输概率的精确表达.研究中发现:传输概率主要取决于节点的位置,但当网络片段的个数超过某一阈值时,传输概率的取值非法,无法应用混合传输策略均衡网络能耗.在此基础上,从理论上给出了全网能量均衡的条件,证明仅当网络片段数不超过n₀时全网能量均衡才能实现,n₀仅取决于一个文中新发现的系数α,α是通信系统的能耗溢价率.还分析了传输距离设置对能量均衡的影响,给出了一般情况下混合传输策略的能量均衡上限.通过仿真实验对所给出的能量均衡条件进行了验证,实验结果与理论分析表明:该条件下,基于所提方法设置传输概率,能够均衡所有节点的能耗.     

Multi-Radio Multi-Channel无线传感器网络中信道分配和路由策略

针对无线传感器网络中传输时延长、传输冲突大和吞吐量低等问题,提出了一种在Multi-Radio Multi-Channel无线传感器网络中信道分配和路由策略.该策略动态地建立k元n立方体拓扑结构,使用优化的静态信道分配算法提高节点的吞吐量,使用维序寻径的路由算法减少传输冲突.该方法适用于网络节点稠密、节点相互之间通信冲突大的情况,并且在单跳和多跳的网络环境下均适用.实验结果表明,基于k元n立方体这一拓扑结构的信道分配和路由策略与传统方法相比,有效地减少了端到端时延,降低了网络冲突,减少了节点能量消耗,延长了网络寿命,提高了网络吞吐量.     

光RP(k)网络上Hypercube通信模式的波长指派算法

波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2ⁿ个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,「5(2^n-5/3」}个波长.而在环网络上,实现该通信模式需要复用(N/3+N/12(个波长,比已有算法需要复用「N/3+N/4」个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.     

基于最小节点度的WSNs传输功率控制重编程协议

为了降低节点能耗,提高能量的利用率,提出了一种高效节能的基于最小节点度的传输功率控制(MND—TPC)重编程协议。该协议首先根据每个节点的剩余能量、最大的传输功率、节点度和链路质量来进行网络的初始化,然后分2个阶段完成数据传输。第一阶段通过节点密度、节点度和M度节点的百分比等产生传输范围的调整模型来构建高效的优化网络;第二阶段通过对节点之间发送功率和剩余能量的比较来筛选发送节点,以保证网络负载的均匀分布,有效地实现了高效节能,从而提高整个网络的生存周期。理论分析与实验结果表明:与多跳网络编程(MNP)协议在不同发送功率下相比,平均能量消耗至少降低35.48%。     

复杂网络大数据中重叠社区检测算法

大数据时代互联网用户数量呈爆炸性增长,社交网络、电商交易网络等复杂网络规模快速发展,准确有效地检测复杂网络大数据中重叠社区结构对用户兴趣点推荐和热点传播具有重要意义。提出一种新的面向复杂网络大数据的重叠社区检测算法DOC（Detecting Overlapping Communities over complex network big data）,时间复杂度为O（nlog²（n））,算法基于模块度聚类和图计算思想应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法。相对于传统重叠节点检测算法,对每个节点分析的频率大大降低,可以在较低的算法运行时间下获得较高的识别准确率。复杂网络大数据集上的算法测试结果表明：DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法。     

无存储器冲突的并行快速排序算法*

本文在一个EREW PRAM(exclusive read exclusive write paralled random accessmachine)上提出一个并行快速排序算法，这个算法用k个处理器可将n个项目在平均O((n/k+logn)logn)时间内排序．所以平均来说算法的时间和处理器数量的乘积对任何k≤n/logn是 O(nlogn)．     

无线传感网中代码更新机制的研究与设计

无线传感网的感知节点部署后需要进行软件维护和功能扩展,因此远程代码更新已变成一种不可或缺的服务。在分析MOAP、Deluge、Ripple等代码分发协议的基础上,设计了一种高可靠、低能耗、低存储、低延迟的多跳代码更新机制Air_update。该机制通过重新设计Bootloader来保证加载代码镜像的正确性、完整性以及节点重编程异常后的可用性;同时,采用子集到子集的分发协议、单播请求的重传策略、滑动窗口的存储管理机制,以减少代码分发的通信量和SRAM、EEPROM的使用量,降低能耗,延长网络的生命周期。最后通过组网实验验证了设计的正确性与有效性。     

A multicast reprogramming protocol for wireless sensor networks based on small world concepts

Automatic reprogramming is an important and challenging issue in wireless sensor networks (WSNs). A usual approach is the over-the-air programming (OAP), which is a fundamental service based on reliable broadcast for efficient code dissemination. However, existing OAP protocols do not enable the reprogramming of a subset of the sensor nodes in a WSN. Hence, in this work we propose a multicast-based over-the-air programming protocol that considers a small world infrastructure (MOAP-SW). The small world model is used to create shortcuts toward the sink in the communication infrastructure of sensor networks. The endpoints of these shortcuts are more powerful nodes, resulting in a heterogeneous wireless sensor network. Simulation results show the feasibility of the protocol regarding the number of messages transmitted, the energy consumption and the time to reconfigure the network.     

基于速龙码的WSNs传输功率控制重编程协议

为了降低节点能耗,提高能量的利用率,提出了一种高效节能的基于速龙码（ RC）的传输功率控制（ RC-TPC）重编程协议。该协议分两个阶段完成数据传输,第一阶段各个节点更新自己的位置信息,形成最优化的拓扑结构。进入第二阶段后,根据优化的拓扑结构通过调整发送节点的传输功率和中继节点的累计选择次数,Sink节点选择适当的中继节点,使中继节点的传输功率和RC的开销达到最优化。此外,RC的编码方式使传输数据包发生的错误概率更小,减少了重编程过程中的冗余以保证网络负载的均匀分布,有效地实现了高效节能,从而提高整个网络的生存周期。理论分析与实验结果表明：与MNP协议和ATPC协议相比,RC-TPC协议用于传输的平均能量消耗降低17.2%。     

具有范围选择的传感网络再编程协议算法研究

已有的传感网络再编程协议大多假定网络中所有节点是同类的,运行同一版本的应用程序,而实际网络节点是异类的。提出了一种新的具有范围选择的再编程协议,该协议变传统的ADV-REQ-DATA三次握手该协议为路由形成、代码传送、请求丢失包三个阶段协议,有效地降低了参与代码转发的中间节点数;中间转发节点通过获取一跳范围内希望接收更新代码数据的节点序列,采取单播或组播方式有针对性传送更新代码,而不是泛洪式的广播,减少了REQ确认信息包,并能统计出参与代码更新的同类节点数和参与代码转发的异类中间节点数。性能分析与模拟实验表明:该协议在平均延时、能量消耗等方面优于传统的Aqueduct。     

A comparative study on simulation vs. real time deployment in wireless sensor networks

Increasing deployment density and shrinking size of wireless sensor nodes requires small equipped battery size. This means emerging wireless sensor nodes must compete for efficient energy utilization. Medium Access Control (MAC) protocols play a vital role in energy consumption of sensor node as it controls the radio activities. Customized or open source simulators play an important role to measure the performance effectiveness of MAC protocols based on the fact that they are flexible, reduce experimental overhead and cost. Nevertheless, these benefits come at the cost of results accuracy. In this paper, we investigate differences of the behaviour of our agent based S-MAC protocols in real deployment compared to the results produced using our custom based simulator, which ignores the lower layers effects such as packet collision and overhearing. We use network simulator 2 (ns2), an open source simulator, which provides a complete protocol stack. We further try to find and explain the rationale of the variance of results produced by real deployment and that of simulators.     

一种基于多播分发树的无线传感器网络代码分发协议

代码分发协议是无线传感器网络（WSNs）在实地部署之后进行软件更新的关键技术。针对现有代码分发协议对特定目标节点分发时需要传输冗余代码镜像的问题,提出了一种基于多播分发树的代码分发（MTCD）协议。MTCD协议通过建立基站节点到目标节点的分发树路径来降低网络中参与代码分发节点的个数,从而降低数据冗余传输和网络能量消耗。TOSSIM仿真结果表明：与TinyOS的标准代码分发协议Deluge相比,MTCD协议在分发时间和数据包传输方面都有更优的性能。     

基于多Mobile-Sink能量有效的WSN再编程协议研究

现有的WSN再编程能量有效协议多集中在单个Sink的静态网络环境下,这就限制了网络规模。基于多Sink的动态WSN再编程能量有效协议能够适应大规模网络环境。提出一种基于多Mobile-Sink能量有效的WSN再编程协议,在该协议中,网络拓扑采用圆形部署,以圆心为坐标系原点,将圆形拓扑分为八个半象限,而每一个mobile sink沿着八个半象限相交的直线往返运动,在每条直线上隔一定距离设置一个信息交换点IEP,Sink在IEP同周围的节点通信。仿真结果表明,提出的方案同MNP协议相比,在节点平均能耗和单个数据包传输能耗两项上更有效率和优势。     

一种大规模传感器网络节能数据发布协议

无线传感器网络的主要功能是实现数据发布,在接收到信息查询时能够以有效的方式传输给查询者.目前的数据发布方式通常基于洪泛机制查询信息,浪费了有限的能源.虽然一些最近的数据发布协议从不同程度上解决了这一问题,但不能保证查询成功率.基于圆形节点分布网络模型提出了一种既能减少能源消耗,又能提高成功率的数据发布模式--直径-弦模式DCS(diameter-chord scheme).该模式利用了每个圆的弦都存在一个直径与之垂直相交的性质.在此基础上提出了Two-Phase协议.它在信息查询时分成两个工作方式不同的阶段进行,在第1段查询不中时触发第2段查找.为了减少Two-Phase的延迟,提出了基于优先级和概率转发两种解决方法.理论分析和实验结果都表明,所提出的数据发布协议具有较好的性能.     

无线传感网使用网络编码的新型数据传输方法

网络编码能提高无线传感器网络数据传输可靠性,针对现有基于网络编码的数据传输策略随机选取编码向量和使用固定路径所带来的缺陷,设计了一个新的编码矩阵构造方法,并提出了一种新型的基于网络编码的可靠数据传输方法。该编码方案能保证任意k个编码向量线性无关,且不用传输编码向量。数据转发使用"区域推进"机制,自动选取最佳转发节点,将数据包可靠地向sin"k推进",并实现了最少冗余传输和网络均衡能耗。分析与仿真表明,新的数据传输策略能消除现有方法的缺陷,提高数据传输可靠性,降低能耗。     

异构传感器网络的分布式能量有效成簇算法

为了延长网络的生存时间,需要设计能量有效的协议,以适应传感器网络的特点.成簇算法是传感器网络中减少能量消耗的一种关键技术,它能够增强网络的扩展性和延长网络的生存时间.研究了异构传感器网络中成簇算法在节省能量方面的性能,提出一种适应异构无线传感器网络的分布式能量有效的成簇方案.此方案基于节点剩余能量与网络节点的平均能量的比例来选举簇头节点.较高初始能量和剩余能量的节点比低能量节点拥有更多的机会成为簇头节点,从而使网络能量均匀消耗,延长网络的生存时间.模拟实验结果显示,与现有的重要成簇方案相比,新的成簇算法在异构网络下提供了更长的网络生存时间和更大的网络有效吞吐量.     

采用半贪心优化的节点非均匀分布路由协议

为避免无线传感器网络中因节点能耗不均衡而产生的能量空洞现象,延长网络生命周期,提出采用半贪心优化的节点非均匀分布路由协议。首先在网络监测区域分层的基础上,计算各层感知数据转发能耗,根据各层网络能耗比例和监测区域覆盖要求,设计了密度递减的节点部署模型;然后基于两跳通信的贪心范围,提出两跳能耗代价估计函数,改进半贪心算法;在簇间多跳通信阶段,利用优化的半贪心算法求解簇头到基站的最优转发路径。仿真实验表明,与现有的几种路由协议相比,新协议能够均衡各层网络节点能耗,延长网络生命周期,有效避免能量空洞现象。