Leach代码分析

1、目录一、Leach协议与NS的关系2二、 算法设计思想4三、簇头建立算法流程图5四、难点解决7五、 算法运行结果分析10参考文献19一、Leach协议与NS的关系 为了实现leach 协议，对ns进行扩展。在ns中增加了一个事件驱动模拟器支持模拟无线传感器网络协议。这些扩展包括MAC协议，用于计算和交互的能量分配模型和leach协议的体系结构。 网络拓扑结构可以通过简单的Nodes, Links, Agents和Applications 描述。Nodes相当于网络中的终端主机， Links 是用于Nodes交互的连接器, Agent用来实现不同网络协议，是支持分组产生和丢弃的节点。Applic

2、ations用来产生数据和实现不同的应用函数。一旦网络拓扑结构建立起来后，模拟通过启动节点上的Applications运行。 为了在ns中支持无线传感器网络，在ns中增加了 mobile nodes, MAC协议和信道传播模型Channel 。 Applications类的头文件用Tcl语言写的，节点中的其他函数功能用C+语言写成的。数据包的发送过程：Applications创建数据包（data packets）,然后发送给Agent. Agent执行协议栈中运输层和网络层的功能，将数据包发送给CMUTrace,。 CMUTrace将packets的统计数据写到trace 文件，然后将pack

3、ets发至Connector。Connector将数据包传送给用于数据链路处理的链路层(LL).经过一小段时间的延迟后，数据包由LL发送给Queue缓冲队列。如果是还没有传送过的数据包，Queue将以队列进行存储。然后Queue将数据包出队列，发送到MAC层。然后开始运行MAC（媒体访问控制）协议。最终，packets被发送到网络接口层(Network Interface),网络接口层将packets加上正确的传输能量，然后将packets发送到Channel. Channel将packets进行拷贝，并发往连接信道的每一个节点。发送过程可参考如下图1数据包的接收过程：数据包被节点的网络接口接

4、收，并被向上传送至MAC层，Link-Layer, Connector, CMUTrace, 和Agent 函数. Agent 对数据包进行判定，并将数据包到达的信息通知给Application. 接收过程与发送过程传输的路径相反。 二、 算法设计思想Leach协议跨越几个层次实现的协议，Leachapp应用在最高层Application。它是自适应分簇拓扑算法。周期执行，每轮循环分为簇头的建立阶段和稳定的数据通信阶段。（1）簇头建立阶段：初始阶段，每个节点从0和1中随机产生一个数，如果这个数小于阀值T（n），该节点就成为当前轮的簇头。 其中，P是期望的簇头数在所有节点中占的百分比，r是选举轮

5、数，r mod (1/p)代表这一轮循环中当选过簇头的节点个数，G是这一轮循环中未当选过簇头的节点集合。 每个节点自主选择是否成为当前轮的簇头并通过广播的形式报告给其他节点。簇头通过CSMA MAC协议进行广播，所有的簇头以相同的传输能量进行广播。 簇头建立起来之后，每个非簇头节点要决定在当前轮中自己属于哪个簇头。非簇头节点根据收到的广播信号强度决定加入哪个簇头。非簇头节点决定了自己属于哪个簇头后，必须通知簇头节点它是该簇的成员。非簇头节点同样通过CSMA MAC协议将自己加入该簇的信息报告给簇头节点。簇头节点收到所有的非簇头节点加入的信息后，基于本簇内加入的节点数目创建TDMA调度，通知每个

6、节点什么时间可以传输数据。在leach协议中，具体通过calculatePi()函数计算门限值thresh.double LeachApp:calculatePi()register int n = config_.numberNodes_; /节点个数register int k = config_.desiredClusters_; /期望簇头数double thresh; /阀值if (hasBeenClusterHead()thresh = 0; /已经是簇头，本轮中不再成为簇头else if (n - k * round_ 1)thresh = 1; /将节点设置为簇头elsethr

7、esh = (double) k / (n - k * round_);return thresh;（2）数据传输阶段：一个簇内的信息传输会影响相邻簇。为了减少这种信号干扰，各个簇内的信息交互通过不同的CDMA编码。簇头可以决定本簇中节点所用的CDMA编码。这个用于当前阶段的CDMA编码在广播簇头的时候发送给簇内节点。具体在advertiseClusterHead()中实现。此外，簇头根据本簇内的节点个数创建TDMA调度。具体的，簇头在findBestCluster()函数中调用createSchedule()，而由createSchedule()函数具体创建TDMA调度。当簇内节点收到这个消

8、息后，它们会在各自的时间槽内发送数据。簇头节点收到所有的数据后执行信号处理函数压缩数据为一个信号，并将这个合成的信号发给基站。三、簇头建立算法流程图 簇头的建立是在decideClusterHead()函数实现。具体流程图如 图1 图1 簇头建立算法流程图四、难点解决 1. CDMA编码问题 Leach协议中不同簇内用不同的CDMA编码，同一个簇内采用同一个CDMA编码进行数据传输。如果以各个簇头为结点，建立完全图。为了使各个簇采用不同的编码，利用PCA边着色。 所谓PCA边着色问题，指在完全图中给节点的每条邻接边分配不同的码。每个节点用一个码在其邻接边（即链路）上进行发送或接收数据。 以下，

9、图2是PCA着色问题的一个示例。 图2 PCA边着色示意图如果记PCA需要的最大可用码数为：（PCA）根据图论知识：（PCA）=2-1 ，其中指图中节点的最大度数例如：在图2中，节点的最大度数为6，故为6在leach协议中，假定期望的簇头数为n， 再加上汇聚节点，所以，节点的最大度数为（n1）。因此， （PCA）myADVnum() % numCodesAvail) + 1; /设置CDMA编码在leachApp.cc程序中，struct leachConfig中对desiredClusters_（期望的簇头数）和config_.spreading进行了定义。在initializeConfig

10、()函数中语句： config_.spreading_ = config_.desiredClusters_ + 1 在LeachApp的构造函数LeachApp(int nNodes, int nClusters, double maxDist) 中语句：config_.desiredClusters_ = nClusters 在TCL脚本中 set val(n_common) 10 /普通节点个数可任意设置，此处设为10set val(n_ch) 0 /簇头数初始值为0 set val(n_ch) expr int($val(n_common) * 2 / 10) /对期望的簇头数进行了设

11、置，为普通节点个数的20（即 上式中的 2/10） 因此，可以计算得出numCodesAvail在mac-sensor.h中，int myADVnum_; / 收到的广播消息，即邻近的簇头节点的个数inline int & myADVnum() return myADVnum_; myADVnum()是在MAC层中计算求得。启动运行后，计算每个簇头的邻近簇头发来的ADV。 因此，可求得clusterCode 2. TDMA调度 在findBestCluster()函数中，当判定节点是簇头节点时需要createScheduler。在createScheduler函数中，如果簇内节点不空，就需要创

12、建TDMA时分复用帧。frameTime 表示该簇头节点分配的一个时间帧；clusterNodes_.size() 表示一个簇内的节点个数config_.ssSlotTime_ 表示一个时间帧内的小的时隙lstRndDelay 表示缓冲时间xmitTime_ 表示簇内所有节点的数据发送时间createScheduler函数主要语句如下：frameTime_ = (5 + clusterNodes_.size() * config_.ssSlotTime_; /计算时间帧lstRndDelay_ = Random:uniform(0, 0.01); /随机选取缓冲时间xmitTime_ = co

13、nfig_.ssSlotTime_ * (clusterNodes_.size() + lstRndDelay_; Scheduler:instance().schedule(eventHandler_,new LeachEvent(&LeachApp:sendDataToBS),xmitTime_); 3. clearClusterChoices() 由于各个簇头形成和建立起来的时间不同，而簇头建立起来后需要广播ADV, 通知其他节点加入。簇头广播的ADV会被网络中的所有节点接收到，即簇头和普通节点都能收到先建立起来的簇头发来的ADV。普通节点收到簇头发来的通知包后都会将该数据包加入自己的一

14、个接收队列。对后来建立起来的簇头来说，一旦自己成为簇头，就会删除其他簇头发来的广播包；对没有成为簇头的普通节点来说，需要出接收的簇头队列中选出一个距离最近的簇头加入，然后删除接收队列中的广播包。在decideClusterHead()函数中，当节点成为簇头后，需要执行clearClusterChoices(), 函数clearClusterChoices()主要语句如下：for (CHs:iterator it = clusterChoices_.begin(); it != clusterChoices_.end(); it+)chadv element = (chadv) *it;if (

15、element.object != NULL)delete element.object;而普通节点则需要在findBestCluster()中找到最优簇头（即距离最近的簇头）后，执行clearClusterChoices()4. 一些定义 （1）virtual double TxTime(int n) return n * 8.0 / 1000000.0; TxTime指以1 Mbps的速度传输n bit数据所需要的时间（2） double lstRndDelay_; / 上次随机延迟时间int currentCH_; /当前簇头int currentCHMAC_; /当前簇头所用的MAC协

16、议bool listenADV_;/ 是否收听ADVbool listenJOINREQ_;/ 是否监听加入请求五、 算法运行结果分析1场景介绍 用ns模拟每个节点向基站传输数据 Basic Configuration: 图3 Basic Configuration配置图Access Point: 图4 Access Point配置图Common Node: 图5 Common Node配置图输出得到TCL文件。在ns环境下运行该TCL文件，得到trace文件。2. trace文件分析trace的功能是详细记录模拟的过程，可以根据用户的需要记录模拟过程中的任何一个细节。所有对模拟的分析是基于t

17、race文件。截取一部分文件代码如下：s -t 0.007580973 -Hs 1 -Hd -2 -Ni 1 -Nx 48.64 -Ny 86.26 -Nz 0.00 -Ne 10.000000 -Nl AGT -Nw - -Ma 0 -Md 1000000 -Ms 0 -Mt 0 -Is 1.0 -Id -1.0 -It rca -Il 4 -If 0 -Ii 0 -Iv 32 r -t 0.007580973 -Hs 1 -Hd -2 -Ni 1 -Nx 48.64 -Ny 86.26 -Nz 0.00 -Ne 10.000000 -Nl RTR -Nw - -Ma 0 -Md 10000

18、00 -Ms 0 -Mt 0 -Is 1.0 -Id -1.0 -It rca -Il 4 -If 0 -Ii 0 -Iv 32 s -t 0.007580973 -Hs 1 -Hd -2 -Ni 1 -Nx 48.64 -Ny 86.26 -Nz 0.00 -Ne 10.000000 -Nl RTR -Nw - -Ma 0 -Md 1000000 -Ms 0 -Mt 0 -Is 1.0 -Id -1.0 -It rca -Il 4 -If 0 -Ii 0 -Iv 32在文件分析中主要用到t, Ni, Ne这几个数据。其中，t 后面的数字代表时间，Ni后面的数字代表节点ID，Ne后面的数字代表

19、节点能量 使用语言gwak, 绘图工具gnuplot. 上述场景中生成的trace文件名为：trace.tr去掉所有以N开头的行数，该行为统计数据，得到文件trace1.tr (1) 单个节点能量变化统计：以节点1为例,提取所有Ni等于1的节点的时间和相应能量，存入文件1.txt. 在gawk环境中，输入代码如下：gawk $9=/1/print $3,$17trace1.tr 1.txt得到统计数据如下：0.007580973 10.0000000.007580973 10.0000000.007580973 10.0000000.007605973 10.0000002.461346376

20、 9.9633632.461371376 9.9633632.461371376 9.9633633.536372973 9.9458033.536372973 9.9458033.536372973 9.9458033.536397973 9.945803在gnuplot环境中输入：gnuplot 1.txt using 1:2得到的能量变化图如下图所示： 图6 节点1能量变化图(2) 工作节点能量统计： 从trace.tr文件中提取普通节点的数据。 gawk $1/N/ print $3,$5,&7 trace.tr n.txt /第3列代表时间，第5列代表节点ID，第7列代表能量值 ga

21、wk $2!=0 print $1,$3n.txt 2.txt /去掉sink节点，sink节点ID为0 再从2.txt中进行能量统计，统计时间间隔为0.5秒 gawk if($13.txt gawk if($13.txt gawk if($13.txt gawk if($13.txt gawk if($13.txt gawk if($13.txt gawk if($13.txt 得到 文件3.txt的统计数据如下： 0.5 3918.841.0 2937.012.5 1395.123.0 4700.223.5 5194.794.0 3271.124.5 1132.38 全网间隔时间为0.5秒

22、工作节点能量变化图： 图7 工作节点能量变化图3全网所有节点能量和变化统计在gawk环境下输入：gawk $9!=0 print $3,$9,$17trace1.tr 4.txt /提取普通节点的时间，ID，能量将以下程序写入文件1.awkBEGIN FS= unit=0.5; ftime=0; time=0; for(i=1;i=50;i+) ei=10.0; sum+=ei; printf %f ,%fn,time,sum; time+=unit; if(ftime$1 &$1time ) k=$2; ek=$3; END sum=0 for(i=1;i5.txt 在5.txt文件中得到的

23、是0到0.5秒之间全网的总能量。 再不断地将每个时间间隔为0.5秒的数据写入文件5.txt（只需在文件5.txt 中不断追加统计数据）。最后可以得到0到4.5秒之间全网在每0.5秒的时间间隔内的总能量。 最后得到的5.txt统计数据如下： 0.000000 ,500.0000000.500000,499.7572171.000000,499.5048001.500000,499.5048002.000000,499.5048002.500000,499.1727333.000000,498.4367983.500000,497.8758164.000000,497.5257304.500000,496.948944在gnuplot环境下，输入命令：gnuplot 5.txt using 1:2 with lp最后得到的全网能量变化情况如下图所示： 图8 全网能量统计图4. 生成的簇头和簇内节点统计 设置普通节点个数50，AP节点1个，仿真时间10秒，普通节点位置随机产生。生成TCL文件，运行该TCL文件将结果输出到2.tr文件中。 在gawk环境中，输入下列命令： gawk ($1=”On”)&($7=”at”)print $0 2.tr 3.tr gawk BEGIN FS=” “; print $10,$11,$12,