有效地提高无线传感器网络使用自适应分割和合并聚类算法

美国Geetha Priya¹境,杂志²

1部门CSE, BHARATH大学、印度
2部门的CSE, BHARATH大学、印度

通讯作者:美国Geetha Priya,电子邮件:(电子邮件保护)

文摘

摘要小说转发方案旨在结合无线传感器网络低计算复杂度和高性能的能源效率和可靠性。分析可能的缺点过度聚类的时间,因为集群密度不均匀。因此,我们提出一个ASMC的算法。该算法提供了适应性移动节点和没有限制网络的可扩展性。分析模型估计的能源效率计划,和一些实际问题如不可靠渠道的影响,讨论了拓扑变化,和MAC的开销。

KeyTerms

能源效率、包分割、可靠性、无线传感器网络。

介绍

无线传感器网络是集传感器节点组织成一个合作网络。传感器是一个小装置,观察到的环境物理参数如温度、压力、相对湿度、声音、振动、运动或污染物,在不同的位置。无线传感器网络(WSN)是高度分布式的无线传感器网络节点部署在大量监测环境或系统。传感器节点传输范围有限和组织本身在一个特设的方式,这意味着两个无线传感器节点,无法直接传送其他传感器节点之间传递数据。一般情况下,数据包从源节点必须遍历多个跳才能到达目的地。近年来,为了保证了网络的生存能力,提高网络的生命周期等特殊用途的环境,提出了各种节能方案的文献[1 - 5]。许多算法主要关注节点的能量平衡,延长生命周期。聚类是设计节能的基本方法之一,健壮的和高度可伸缩的分布式传感器网络。聚类的传感器网络减少了通信开销,也减少了能源消耗和传感器节点之间的干扰。

方法

.Minimizing能源消耗

减少能源消耗的目的,考虑到算法的复杂性,提出了一种新颖的方法,其破裂原始消息分成几个包,这样网络中的每个节点只会向前小子包。分裂过程实现应用ASMC的算法。水槽节点,一旦所有子组件(称为分裂)接收数据包正确,将重组,从而重构原始消息。分裂过程尤其有助于那些比其他人更请求的转发节点在网络由于其位置。建议的方法,几乎所有节点在古典转发算法和运作,除了水槽,几个low-complex算术运算是必要的。水槽节点计算和能量比其他传感器节点装备,整体复杂性仍低,适合传感器网络。此外,该方法不需要使用不相交的路径。这种方法的一些初步结果已提交但他们只经验和通过模拟一个传感器网络,假设一个理想的邻居传感器之间的沟通发生时,和所有的组件可以收到正确的一对节点之间。

通过分析模型允许我们获得准确的结果对能源消耗和复杂性。重要参数的影响,如节点密度和传输范围通过广泛的模拟和节能之间的权衡的分析研究,提出技术的复杂性,和可靠性。在传感器网络中,数据生成的每个节点,从多个数据源到数据接收方或下沉,而节点之间的通信。

b .转发技术

传感器网络中传感器节点周期性地发送消息到一个水槽节点通过多跳传输。基本思想是破裂源节点发送的消息,以便减少每个货代节点传输的比特数。为了更好地理解的主要思想,图1中的示例。A和B节点需要一个数据包转发到水槽和可以通过节点X, Y,和Z,这都在A和B的覆盖范围如果采用正常的转发方案,2例、案例A和B)选择不同的转发节点。这发生在概率2 \ 3。案例b) A和b选择同一nexthop节点。发生这种情况的概率1 \ 3。

如果有ω为每个包位,最大数量的比特通过一组节点属于{X, Y, Z}是w位情况下)和2ω位b)。我们现在假定每个节点集{X, Y, Z}知道a和b有三个可能的跳和采用不同的转发方案,如图1所示。特别是,当X, Y, Z接收数据包,他们只把它发送到水槽里。在这种情况下,X, Y,和Z最多传输比特。在比较两种转发方法,得出的结论是,最后一个减少的最大比特数通过一组节点属于{X, Y, Z}。更准确地说,减少因素是1 - 2 3 = 1 \ \ 3。当比较破裂过程与过程情况下所示),和(2 - 2 \ 3)。1\2 = 2\3 when the bursting procedure is compared to the procedure shown in case b). Summarizing, an average reduction factor of 4/9 is obtained. Accordingly, the lifetime of a sensor network increases as the energy consumption is more distributed among the nodes. It is worth remarking that the bursting procedure has to be performed in a simple manner, and consequently with low energy consumption.

传输比特的总量不会改变(比特传输,要么有或没有分裂);破裂的数据包可以减少每个节点的最大传输比特数,因此每个节点的平均能量消耗的传播。最后,它可以观察到,如果一个完美的平衡是有可能的,这发生在跳节点的数量是一个因素的数量(即传播消息。,消息的数量就是跳数的整除),节点的能量消耗将是相同的要么有或没有破裂。但是,如果情况并非如此,使用爆破技术使转发的数量显著降低。此外,减少增加如果“消息长度超过数量的组件”的比例减少。

自适应SPLIT-AND-MERGE聚类算法

一般来说,当网络适当的集群节点密度和采用合适的功率控制算法,拖延只会限制。然而,有时集群头将接受大量的节点作为集群成员。事实上,节点在集群中感应的状态,接收或发送除了睡觉。延长聚类时间肯定会消耗更多能量,缩短了网络的生命周期。事实上,集群密度产生影响的持续时间许多聚类任务,如计算,发送和接收每天播发或者刊登的列表。通常,集群密度高带来的负面影响扩大许多任务的运行时间,如时间同步、节点位置、密钥分发等等。这些任务也占据集群,集群密度高将显著延长聚类时间具有显著的影响在整个网络中节点睡眠时间剩余的能量。考虑到所有这些因素,我们提出ASMC的算法。波形算法1是该ASMC算法描述。算法2、3、4 ASMC算法描述三个主要过程,即分裂,分别合并和集群头补选。

定义:

NodeID MRENID:最大剩余能量

Aj:一组集群头的集群条目的数量大于Q1

Bj:一组集群头的数量的集群输入小于Q2

算法1:

预设集群头数量在第一轮根据表达式:N / k;

foreach集群头j

广播Cluster_Head_Msg (MREICNID);

接受加入节点

foreach集群头j∈Aj分裂;/ /参见算法2。foreach集群头j j∈Bj合并;/ /参见算法3。

收集MRENID MRENA;

启动集群正面递补选举当集群正面身份广播收到小于N / k;/ /请参见算法4。

结束

算法2:

foreach集群头j∈Aj

停止接受加入节点;

指定一个新的簇头;

结束

算法3:

foreach集群头j∈Bj做MREICNID =零;结束

算法4:

foreach集群头j∈C指定一个新的簇头;结束

矩阵对能源效率

特别是,作为比较,最短路径和负载平衡(SP)被认为是。SP方法非常类似于概率路由。传感器节点有一个数据包转发随机选择邻居节点作为中继者向下沉,这样跳需要达到水槽的数量最小化。负载平衡(即。,a random choice of the relayer) allows prolonging the network lifetime, avoiding that some nodes could be overloaded. Throughout, considered that an SP packet is composed by K words of ω bits each and that the burst-based splitting procedure can be applied to each word by considering that the same is used for all the words of same packet. The overhead due to the MAC layer head, but it is worth noting that all the words in the packet generated by the splitting procedure are represented with the same number of bits and therefore their length can be obtained from the prime number used to split the packet. With the above hypothesis, the expected energy reduction factor can be expressed by considering mean energy consumed by a node in the case of the proposed burst-based and the SP forwarding technique respectively, where and are the mean number of forwarded packets with the above forwarding schemes, is the mean number of bits needed to represent the burst components, and is the energy needed to transmit a bit.

然而,如果大量的数据包被认为,预期的比特总数在数篇论文是关于网络,网络生命周期相关的时间第一个节点的死亡。在这种情况下,所消耗的能源的最大节点应该也会考虑。因此,在这个项目中它也调查相关的能量换算系数的最大能量和转发数据包的最大数量。显然,集o的质数应该正确选择为了最大化上述矩阵。

能量换算系数

重要的是观察到的和可以任意选择的前提是质数。因此,可以减少所需的比特数来表示选择素数尽可能小。这个选择的结果,MERF最大化。在,这说明以最小的质数(MPS)的连续最小的质数集满足条件。例如,如果,是40位词,议员们将最小(这是一组连续四个质数,满足条件)。本例中的MERF是0.725。然而,当上面的质数选择设置为中,消息可以重建当且仅当所有破裂组件正确接收到水槽里。让我们考虑另一个质数。

选择可以重建原始消息即使组件丢失(即。如果我们有一个失败)。事实上,无论失去了组件,质数的乘积与接收组件满足相关条件,因此这方面的假说破裂定理。例如,如果没有收到最后一个组件,又可以获得,是前三个质数的乘积,和前三个MPS-1系数计算。

1。组件的数量(即不改变。,需要相同数量的代理)。2。新获得的MERF设置为0.65,即。,MERF降低了约11%。

因为传感器节点通常会有简单的处理单元,它是强制性的复杂过程获取值很低。这个目标很容易达到,如果是固定的或只需要几值。这是一个非常快的过程。

系统实现

转发算法

转发算法是基于两个时间阶段,初始化阶段和转发阶段。初始化阶段是将数据和执行转发转发阶段。

初始化阶段

这一阶段组织网络优势的集群和也减少啤酒花的数量需要达到水槽,初始化阶段详细描述,它是通过交换实现初始化消息(IMs)从水池里,应该是属于集群。我重新发送。的基础上接收到的IMs,末端的过程网络中的每个节点知道自己的跳,其他节点将使用它作为一个跳,并分成多少部分收到的数据包。

水槽发送第一个我可以获得每个节点初始化阶段的国会议员和选择一个不同的素数MPS-f通过考虑的顺序在我指定的地址。回想一下,为了获得议员- f,是足以知道在IMs固定或指定,而质数数目对应的数量可能跳(每个转发节点知道的基础上接收到的IMs)因为每个源节点可能会有所不同,它使用的符号。

然而,水槽,为了重建信息,还需要知道的索引组件(即收到。为每个)。为了这个目的,它会假设在每个数据包的头部有一场名为面具。面具可以索引的二进制表示组件的数量(即紧随其后。,pair] or a “one-hot” coding bit sequence followed by a tail bit .Its assumed that the overhead introduced by the mask is negligible. According to the previous initialization procedure shown in Figure .It will receive the IM with from the node X, and it decides to belong to, node Y will have only one next-hop (i.e., X) because Y is at the end of the coverage range of nodes belonging to. Now, we consider what happens with the modified procedure.

拟议的初始化过程可以进一步细化为了增加在某些情况下可能的下一跳节点的数量可以使用代理。特别是,当一个节点收到很少的IMs,它没有选择立刻属于集群,但等待IMs与下一个序列号属于最后一个集群更方便。

当节点Y接收即时通讯,它推迟的决定属于其他节点。一段时间后,将收到两个新IMs与从节点A和B,因此它决定属于为了有两个可能的跳,而不是一个如图3所示。基本上,阳极可以推迟的决定属于一个特定的集群如果IMs收到的数量小于选择阈值,但这仅仅能做一次,以避免增加啤酒花的数量需要达到水槽。阈值可以是一个常数值(IM或预先存储在节点中指定的内存,因此已知的节点)。此外,如果收到我的数量小于阈值,可以使用传统的最短路径方法(SP),也与我们的技术工作。执行初始化程序只有当网络首次被激活,并没有必要运行它当一个新节点加入网络或节点能量耗尽。在这两种情况下,它是足够的,很少有IMs之间交换节点及其邻居附近属于集群。更详细的操作需要上述病例描述。此外,为了考虑信道的不可靠性,导致损失的IM数据包,因此在足够数量的邻居节点,每个节点可以定期新加入的过程。

c .转发阶段

一旦网络组织,转发阶段。基本上;遵循相同的所有节点转发规则:如果有很多邻居至少等于,和包没有以前分裂,然后将数据包;使用传统的最短路径的方法。让我们考虑网络显示,集群获得根据初始化过程已经在前一节中描述。每个节点发送的消息H当源节点发送一个消息到水槽美国根据初始化过程中,节点转发G知道这是唯一的节点H,因此它必须转发数据包没有执行分裂过程。值得强调的是,没有必要为G指定数据包的目的地址的列表。事实上,在初始化阶段,节点已经收到了IM消息,因此他们知道节点G有四个跳,所有人将接收到的消息从G为NG = 4部分。因此,当他们收到数据包,根据数据包大小和他们各自选择素数3和发送组件,加上一个合适的面具,一个可能的跳。当水槽接收到一个组件,它标识的数量预计组件的基础上面具,因此它计算MPS-f和所需的系数重构原始消息。

关于算法的复杂性,值得一提的是,消息将是只有一个时间节点执行的最接近源和有机会做(例如,如果他们在附近的邻居高于阈值为初始化阶段指定),而其他网络中传感器节点只会向前子包。此外,只有水槽节点将重建原始消息通过所描述的更复杂的操作,但这通常可以认为水槽节点计算和大力的装备比其他传感器节点。显然,对于非常大的包,可以递归地将数据包,但是为了保持算法的复杂度很低,其认为包只能分裂一次。

绩效评估

在本节中,破裂的性能的比较而言,能源消耗了SP。此外,提供了一些结果比较破裂最天真的分割方案,一个简单的包划分成块。

结果已经通过一个定制的MATLAB仿真。通过分析获得的结果之间的比较,通过模拟器。然后,我们分析一些其他参数,以显示该技术的优点。

图5显示了传输1和传输2的值都由模拟数据包转发让考虑这样一个传感器网络,节点随机分布在正方形区域的尺寸m,与密度节点/ m。传感器节点被认为是静态的像往常一样在大多数应用程序。

Figure.5,显示传输1和传输2的值都由每个仿真模拟数据包转发,水槽节点位于广场中心的网格,每个传感器节点传输范围等于m。

结论

小说转发技术,无线传感器网络基于ASMC算法能够预测过程的能源效率。聚类算法参数的选择为了保持处理复杂性低,然后权衡能耗和可靠性是可以衡量的。最后,引入的开销在数据包头部大小在MAC层会减少。仿真结果证实了结果和显示应用ASMC-based技术大大降低了能源消耗为每个节点,降低计算复杂度,从而提高了网络的生命周期。

引用

Akyildiz, s . Weilian y Sankarasubramaniam, e . Cayirci传感器网络调查,IEEE通讯杂志40 (8)(2002)102 - 114。
思。,Dimitrios J., Dimitrios D., et al. Energy efficiency in wireless sensor networks using sleep mode TDMA scheduling. Ad Hoc Networks 7 (2009) 322-343.
Heinzelman W,切卓卡山·h·能量高效的无线微传感器网络通信协议。:夏威夷国际会议系统科学学报》,1卷,夏威夷,美国,2000年。3005 - 3014页。
o·尤尼斯,s Fahmy注意:混合动力、节能,为特定的传感器网络分布式聚类方法,IEEE移动计算3 (4)366 - 379 (2004)。
Heinzelman W,切卓卡山·h·无线微传感器网络的特定于应用程序的协议体系结构,IEEE无线通讯,1 (4)(2002)660 - 670。
g . Anastasi m .孔蒂m . Di弗朗西斯科·a .主席帕萨雷拉,“如何延长无线传感器网络的生命周期,”在移动Ad Hoc的手册和普遍的通信。瓦伦西亚,CA:美国科学出版社,2007年,ch。6。
t·r·Burchfield美国文卡特斯,韦纳,“最大化吞吐量在ZigBee无线网络分析、模拟和实现,“在Proc, Int。车间局部寒冷。网络协议,圣达菲,海里,2007年6月,页15一个¢29。
g . Campobello A . Leonardi s宫殿,”中国剩余定理的使用节能的无线传感器网络,“在Proc。IEEE国际刑事法庭,北京,中国,2008年5月,页2723¢2727。
g . Campobello A . Leonardi s宫殿,“小说可靠和节能转发技术对无线传感器网络来说,“在Proc。ACM MobiHoc,新奥尔良,洛杉矶,5月18日一个¢21日,2009年,页269¢278。
r . Crepaldi a·f·哈里斯,三世,m·罗西g . Zanca andM。圭”喷泉重组协议:一种可靠的无线传感器网络数据传播方案使用喷泉码,演示抽象,“在Proc。ACM SenSys,悉尼,澳大利亚,2007年11月,页389¢390。
b . Deb,美国博和b·纳”再通知:可靠的信息转发在传感器网络使用多条路径,“在Proc。28日为基础。IEEE LCN、波恩、德国,2003年10月,页406¢415。
p . Djukic和s Valaee“最低能源可靠的特设网络,”在Proc。22日Bienni.Symp.Commun。加拿大金斯顿,2004年6月,页150¢152。
s . Dulman t . Nieberg j . Wu, p .真的,做出“之间的权衡交通开销和可靠性为无线传感器网络多路径路由,“在Proc。WCNC,新奥尔良,洛杉矶,2003年3月,页1918¢1922。
e .法索罗·m·罗西,j . Widmer和m .圭”为无线传感器网络网络聚合技术:一项调查,“IEEEWirelessCommun。,14卷,不。2,页70¢87,2007年4月。
w .樵夫,介绍概率论,第三。纽约:威利,1968年,卷。1。
d . Ganesan r . Govindan s Shenker d·埃斯特林,“高度弹性、能源efficientmultipath路由在无线传感器网络中,“MobileComput。Commun。5卷,没有牧师。4,页10 A¢24,2001年10月。
a . m . Gittelsohn Amer“一个占用问题,”。统计学家,23卷,不。2,页11¢12,1969年4月。
黄永发。在香港,学术界。吴,C.-W。吴”,RSA密码系统基于中国剩余定理”,在Proc。ASP-DAC,横滨日本,2001年1月,