《无线传感器网络的簇头重配置研究.ppt》由会员分享，可在线阅读，更多相关《无线传感器网络的簇头重配置研究.ppt（19页珍藏版）》请在三一办公上搜索。
1、无线传感器网络的簇头重配置研究,Reconfiguration of clusterheads for load balancing in wireless sensor networks,Namhoon Kim a,Jongman Heo a,Hyung Seok Kim b,*,Wook Hyun a School of Electrical Engineering and Computer Sciences,Seoul National University,599 Gwanangno,Gwanak-gu,Seoul,151-742,Republic of Korea b Departm
2、ent of Information and Communication Engineering,Sejong University,98 Kunja-dong,Gwangjin-gu,Seoul,143-747,Republic of KoreaReceived 19 December 2006;received in revised form 16 October 2007;accepted 29 October 2007,摘要,Abstract：This paper proposes an effective reconfiguration algorithm to increase t
3、he network lifetime by fairly distributing clusterheads(CHs)inwireless sensor networks.For a fair distribution of the CHs,the current CH chooses the next CH according to the two metrics the number of general nodes(GNs)in a cluster and the number of CHs within the GNs transmission range.By fairly dis
4、tributing the CHs,the number of GNs in the clusters can be balanced,which leads to fair energy consumption of the CHs.Simulation results show that the proposed algorithm increases the network lifetime.,本文提出了无线传感器网络的一种有效的簇头重配置算法，这种算法通过公平的分布簇头节点来增加网络的生存期。为了公平的分布簇头节点，当前簇头根据两个量（一个簇的成员节点数量和成员节点感应范围的簇头节点数
5、量）来确定下一个簇头节点。通过公平分布簇头，簇内成员节点的数量能得到平衡，从而使得簇头节点能量消耗平衡。仿真结果显示，本文提出的算法能有效地延长网络的寿命。,引言,In order to support data aggregation through the efficient network organization,nodes can be partitioned into a number of small groups,called clusters.Each cluster has a coordinator,referred to as a clusterhead(CH),and
6、 a number of general nodes(GNs)7.Instead of communicating directly with BS,a GN transmits data to its CH,which in turn forwards the data to the BS,either directlyor via a multi-hop path through other intermediate CHs.This significantly reduces the battery drainage of individual 为了通过高效率的网络组织来实现数据聚合，节
7、点被分成许多小分组，即簇。每一个簇又一个协调者-叫作簇头和许多普通节点。普通节点传送数据给其簇头节点，而不是直接传送给基站。接着，簇头再把聚合的数据通过直接或多跳向前传送直到基站。这较大的减少了普通节点的能量消耗。本文提出了一种新的强制配置簇头的算法以增加网络寿命。这种算法使当前簇头根据簇的成员节点数量和成员节点感应范围（假设为J）的簇头节点数量来确定下一个簇头节点。具有相同J范围的普通节点有其特有的感应区域，叫做簇的子区域。使用J，我们可以把一个簇的监控区域分成多个子区域。根据，簇内节点的数量，当前簇头节点从不同的子区域来选取下一个簇头节点。因此，簇头节点能公平的分布，从而使簇内的普通节点数
8、量平衡。,2.网络模型,If we assume that N nodes are distributed uniformly in an L*L region with the maximum transmission range R and the number of nodes in the ith cluster denoted by ni,then n1+n2+n3+nk=N where k is the number of clusters.In monitoring or data gathering applications,all nodes can be assumed t
9、o generate the same amount of data within the same period.Therefore,ni can be regarded as the load of ith cluster.我们假设N个节点均匀的分布在L*L的区域中，其最大的传输范围是R，第i个簇内的节点总数为Ni，那么：n1+n2+n3+nk=N 其中k是簇的个数。在监测或数据聚合应用中，假设所有节点在相同周期内发送数据量相同，因此，ni表示第i个簇的负载。简单地说，我们主要研究在单跳簇的普通节点在其感应范围内能直接发送数据给簇头。为了构建单跳簇环境，我们假设Po为某个普通节点在其感应范
10、围内没有簇头节点的概率。Po=（1-q）k，其中q是给定一个普通节点能感应到的区域的一部分,3.提出的簇头重配置算法,一个簇的操作可以分成两个阶段，setup（设置）阶段和steary-state（稳定状态）阶段，如图一。包括这两个阶段的周期称为round。其中稳定状态阶段被分成几个阶段且每一个阶段内所有的普通节点将其原始数据传送给簇头节点。,The operation of a cluster can be divided into two phases,the setup phase and the steady-state phase,as shown in Fig.1.The peri
11、od which contains the setup and steady-state phases is called a round 11.The steady-state phase is divided into several frames and all GNs transmit the raw data to their CHs at each frame.During the setup phase,a set of CHs in the mth round,which is denoted by XemT,is chosen as,3.提出的簇头重配置算法,在设置阶段，第m
12、个round周期的一组簇头节点，假设为X(m)，X(m)=x1(m),x2(m),xk(m)其中xi(m)表示X(m)的第i个簇。如果m=1，那么X(m)是随机选取的或事先定好了。否则，X(m)根据前面的簇头节点组X(m-1)来确定的。接着，每一个簇xi(m)向网络广播信息以通知其他节点其当前是簇头节点。当所有节点（包括簇头节点）接受到这些簇头广播包时，计算这些广播包的数量，J。也就是说，J是一个节点在其感应范围内的簇头节点的数量。通过考虑自身的广播，我们对每一个簇xi(m)的J加1，例如，如果x1(m)接收到两个广播包，那么x1(m)的J是3，其中包括自身的广播包。接下来，普通节点选择最近的
13、一个簇并连接以参与簇的通讯。received signal strength indicator(RSSI)接收信号强度指标用来评估两个传感器之间的距离，这种指标广泛应用于典型的无线传感器网络中。因为所有簇头节点发送数据广播所需的能量一致的，故最高RSSI的簇就是最近的簇。如果J=1，那么普通节点称为唯一的普通节点。,3.提出的簇头重配置算法,在稳定状态阶段，第i个簇的普通节点发送原始数据（包括J和它们剩余的能量指标）给簇头，xi(m)。通过普通节点的数据聚合，xi(m)可能获得其簇内的普通节点数量ni(m)。接着，xi(m)组织起其簇内的普通节点，假设为Ci(m)，其含有k个子集，假设为Si
14、(m,j)（1=J=k），如下式所示。,Si(m,j)是能接受到广播包J次的普通节点的一个子集。例如，如果一个普通节点在初始周期连接到第三个簇，那么它属于C3(1)。如果它接收到广播包两次，即J=1，那么它属于S3（1，2）。在稳定状态阶段的操作可能概括为算法1：,3.提出的簇头重配置算法,3.提出的簇头重配置算法,图2描述了在初始周期时有三个簇。每一个簇具有任意的形状区域，这使其根据J值而划分为几个子区域。每一个子区域的普通节点能用Si(m,j)来表示，这些普通节点在相同的子区域属于相同的子集Si(m,j)。,3.提出的簇头重配置算法,下一个周期，一组新的簇头节点X（m+1）在设置阶段来选取
15、。使用诸如ni(m)、J、普通节点剩余的能量之类的信息，每一个簇xi(m)都能选取一个适当的普通节点来作为下一个簇头。根据ni(m)考虑以下两种情况：,其中N/k是ni的平均值，这些都是网络形成前事先给定的。在第一种情况，xi(m)有很多普通节点，或者说簇比较大，我们假设节点是均匀分布的。为了减小下一个周期普通节点的数量，xi(m)选择其唯一子集中剩余能量最多的普通节点为簇头，即Si(m,1)。根据剩余能量来选取簇头能有效的增加整个网络的寿命，如文献9就提到过。通过在Si(m,1)中选择一个普通节点，xi(m+1)将位于先前簇头节点的感应区域内。第二种情况，一个簇只有少量的普通节点，即簇比较小
16、。这是由邻居簇头节点占有大量普通节点引起的。因为大簇内的簇头节点将选择远离小簇的节点为下一个簇头节点，所以一个小簇的簇头就在其附近选择下一个簇头节点。接着在一个周期，大簇内非独立的区域的普通节点将连接成簇。例如，x2(1)和x3(1)满足第二种情况。如图2，我们假设A被选择x1(2)，接着，大部分S1(1,3)的普通节点和S1(1,2)的一些普通节点根据最近原则来改变其簇。,3.提出的簇头重配置算法,为了选取比较近的普通节点，x2(1)和x3(1)选择那些具有相同J值的普通节点。注意，x2(1)和x3(1)相同J值是3，x2(1)和x3(1)从S1(1,3)和S3(1,3)中的普通节点选取出下
17、一个簇头节点。如果在其子区域里有较多的普通节点，那么选择其中剩余能量最多的那个节点为簇头。如果和的剩余能量相同，那么选取x2()和x3()。设置阶段所有的操作可以概括为算法：,3.提出的簇头重配置算法,图和显示了本文提出的簇头重配置算法在第和第个周期的相应情况。,4.仿真,仿真参数设置如下：,为了使节点分布均匀，节点总数必须较大。如果有个簇头节点（即），那么节点为孤立的概率为0.0002。整个网络有孤立节点的概率为Po*N=0.06。因此，传感器网络满足式（4）。我们把本文的算法与LEACH算法和ET-driver算法相比较。假设簇头节点概率为p，在LEACH算法在300个节点中选取出4个簇头
18、节点。图4-6分别显示了本文算法、LEACH算法和ET-driver算法在头三个周期的重配置过程，由于初始簇头节点式公平分布的，故在第一个周期两边的簇头节点将占据比较多的普通节点。,4.仿真,使用本文提出的算法，大簇的簇头节点将从其他簇头节点稀少区域内选取下一个节点，如图4所示。因此，左边的两个簇头在它们的单独的子区域内选择下一个簇头节点。接着，在第2个周期左边的两簇头离先前的簇头比较远，同时因右边簇比较小，故其当前簇头将从附近区域的普通节点中选取下一个簇头。结果显示，本文提出的算法能平衡簇的普通节点数量。,4.仿真,使用ET-driver算法，每一个簇头选取簇内剩余能量最多的节点为下一个簇头
19、节点。因此，并不是所有簇头节点都是在设置阶段给定初始值来选取下一个簇头的，如图5。,4.仿真,使用LEACH算法，节点自我计算其性能来决定自己要不要设置为簇头，例如，在第一个周期内，每一个节点选择一个随机值r。当rp时，相应的节点就被选取为簇头。,4.仿真,为了衡量负载平衡度，在簇负载的变化定义为：,注意，值比较小意味着簇内负载平衡度高，这能使得簇头合适分布。图7显示了上面提到的算法中值变化时的情况。LEACH算法时一种自我重配置的算法，因为在LEACH算法中簇头的数量和分布与图6描述的随即选取比较相似。,5.结论,本文提出了一种无线传感器网络的簇头重配置的算法，这种算法能延长WSN的生存期。一个簇的当前簇头能根据节点信息(例如簇的节点数量)和在一个节点感应范围内的簇头数量来确定下一个簇头节点。仿真结果显示，本文提出的方案能平衡整个传感器网络的负载并能增加无线传感器网络的寿命。由于每一个节点接收信息不用额外的开销且计算量少，故本文提出的算法在延长网络生存期方面简单、实用。因此，本文的算法是WSN数据集合的一个有效的工具。,Thank You!,
