《Leach代码分析（9月11日）.pptx》由会员分享，可在线阅读，更多相关《Leach代码分析（9月11日）.pptx（20页珍藏版）》请在金锄头文库上搜索。
1、学 海 无 涯,目录 一、Leach 协议与NS 的关系. 2 二、 算法设计思想 . 4 三、簇头建立算法流程图 . 5 四、难点解决 . 7 五、 算法运行结果分析 . 10 参考文献 . 19,1,2,学 海 无 涯,一、Leach 协议与 NS 的关系 为了实现leach 协议，对ns 进行扩展。在ns 中增加了一个事件驱动模拟 器支持模拟无线传感器网络协议。这些扩展包括MAC 协议，用于计算和交互的 能量分配模型和leach 协议的体系结构。 网络拓扑结构可以通过简单的Nodes, Links, Agents 和Applications 描述。 Nodes 相当于网络中的终端主机，
2、Links 是用于 Nodes 交互的连接器, Agent 用来实现不同网络协议，是支持分组产生和丢弃的节点。Applications 用来产生 数据和实现不同的应用函数。一旦网络拓扑结构建立起来后，模拟通过启动节点 上的Applications 运行。 为了在ns 中支持无线传感器网络，在ns 中增加了 mobile nodes, MAC 协 议和信道传播模型Channel 。 Applications 类的头文件用 Tcl 语言写的，节点中的其他函数功能用 C+ 语言写成的。 数据包的发送过程： Applications 创建数据包（data packets）,然后发送给Agent. Ag
3、ent 执行协议 栈中运输层和网络层的功能，将数据包发送给 CMUTrace,。CMUTrace 将packets 的统计数据写到trace 文件，然后将 packets 发至Connector。Connector 将数据包 传送给用于数据链路处理的链路层(LL).经过一小段时间的延迟后，数据包由 LL 发送给Queue 缓冲队列。如果是还没有传送过的数据包，Queue 将以队列进行存 储。然后 Queue 将数据包出队列，发送到 MAC 层。然后开始运行 MAC（媒体 访问控制）协议。最终，packets 被发送到网络接口层(Network Interface),网络接,学 海 无 涯 口层
4、将packets 加上正确的传输能量，然后将packets 发送到Channel. Channel 将 packets 进行拷贝，并发往连接信道的每一个节点。 发送过程可参考如下图 1 数据包的接收过程： 数据包被节点的网络接口接收，并被向上传送至 MAC 层，Link-Layer, Connector, CMUTrace, 和Agent 函数. Agent 对数据包进行判定，并将数据包到 达的信息通知给Application. 接收过程与发送过程传输的路径相反。,二、 算法设计思想 Leach 协议跨越几个层次实现的协议，Leachapp 应用在最高层Application。 它是自适应分簇
5、拓扑算法。周期执行，每轮循环分为簇头的建立阶段和稳定的数 据通信阶段。,3,学 海 无 涯 （1）簇头建立阶段：初始阶段，每个节点从 0 和 1 中随机产生一个数， 如果这个数小于阀值T（n），该节点就成为当前轮的簇头。,其中，P 是期望的簇头数在所有节点中占的百分比，r 是选举轮数，r mod (1/p) 代表这一轮循环中当选过簇头的节点个数，G 是这一轮循环中未当选过簇头的节 点集合。 每个节点自主选择是否成为当前轮的簇头并通过广播的形式报告给其他节 点。簇头通过 CSMA MAC 协议进行广播，所有的簇头以相同的传输能量进行广 播。 簇头建立起来之后，每个非簇头节点要决定在当前轮中自己属
6、于哪个簇头。 非簇头节点根据收到的广播信号强度决定加入哪个簇头。非簇头节点决定了自己 属于哪个簇头后，必须通知簇头节点它是该簇的成员。非簇头节点同样通过 CSMA MAC 协议将自己加入该簇的信息报告给簇头节点。 簇头节点收到所有的非簇头节点加入的信息后，基于本簇内加入的节点数目 创建TDMA 调度，通知每个节点什么时间可以传输数据。 在leach 协议中，具体通过calculatePi()函数计算门限值thresh. double LeachApp:calculatePi() register int n = config_.numberNodes_;/节点个数 register int k
7、 = config_.desiredClusters_; /期望簇头数 double thresh;/阀值,4,5,学 海 无 涯 if (hasBeenClusterHead(),thresh = 0;,/已经是簇头，本轮中不再成为簇头,else if (n - k * round_ 1),thresh = 1;,/将节点设置为簇头,else thresh = (double) k / (n - k * round_); return thresh; （2）数据传输阶段： 一个簇内的信息传输会影响相邻簇。为了减少这种信号干扰，各个簇内的信 息交互通过不同的CDMA 编码。簇头可以决定本簇中节
8、点所用的CDMA 编码。 这个用于当前阶段的 CDMA 编码在广播簇头的时候发送给簇内节点。具体在 advertiseClusterHead()中实现。 此外，簇头根据本簇内的节点个数创建 TDMA 调度。具体的，簇头在 findBestCluster()函数中调用createSchedule()，而由 createSchedule()函数具体创建 TDMA 调度。 当簇内节点收到这个消息后，它们会在各自的时间槽内发送数据。簇头节点 收到所有的数据后执行信号处理函数压缩数据为一个信号，并将这个合成的信号 发给基站。 三、簇头建立算法流程图 簇头的建立是在decideClusterHead()函
9、数实现。具体流程图如 图 1,学 海 无 涯,从0，1中产生 Random thresh ？,本轮中还未产生簇头 setHasNotBeenClusterHe ad(),初始化设置 totRounds为总轮数,开始,轮数round从0开始计,round=0 ?,已进行的轮数= 总轮数 ？,Y,6,N,N,Y,Y,N,学 海 无 涯,设置为簇头,广播簇头,设置为非簇头,设置收听广播包 listenADV_ = true,清除其他簇头发来的包,设置轮数，下次启动簇头选择的时 间,Scheduler调度下次簇头选择,Scheduler调度findBestCluster(),7,结束 图 1簇头建立算
10、法流程图 四、难点解决 1. CDMA 编码问题 Leach 协议中不同簇内用不同的 CDMA 编码，同一个簇内采用同一个 CDMA 编码进行数据传输。如果以各个簇头为结点，建立完全图。为了使各个 簇采用不同的编码，利用PCA 边着色。 所谓PCA 边着色问题，指在完全图中给节点的每条邻接边分配不同的码。 每个节点用一个码在其邻接边（即链路）上进行发送或接收数据。,学 海 无 涯 以下，图 2 是PCA 着色问题的一个示例。,图 2PCA 边着色示意图 如果记PCA 需要的最大可用码数为：（PCA） 根据图论知识： （PCA）myADVnum() % numCodesAvail) + 1;/
11、设置 CDMA 编码 在leachApp.cc 程序中，struct leachConfig 中对 desiredClusters_（期望的簇头 数）和config_.spreading 进行了定义。,8,9,学 海 无 涯 在initializeConfig()函数中语句： config_.spreading_ = config_.desiredClusters_ + 1 在 LeachApp 的构造函数 LeachApp(int nNodes, int nClusters, double maxDist) 中语句：config_.desiredClusters_ = nClusters 在
12、TCL 脚本中,set val(n_common),10/普通节点个数可任意设置，此处设,为 10 set val(n_ch)0/簇头数初始值为 0 set val(n_ch) expr int($val(n_common) * 2 / 10)/对期望的簇头数 进行了设置，为普通节点个数的 20（即 上式中的 2/10） 因此，可以计算得出numCodesAvail 在mac-sensor.h 中， int myADVnum_;/ 收到的广播消息，即邻近的簇头节点的个数 inline int myADVnum()是在 MAC 层中计算求得。启动运行后，计算每个簇头的 邻近簇头发来的 ADV。
13、因此，可求得clusterCode 2. TDMA 调度 在findBestCluster()函数中，当判定节点是簇头节点时需要 createScheduler。 在createScheduler 函数中，如果簇内节点不空，就需要创建 TDMA 时分复用帧。 frameTime表示该簇头节点分配的一个时间帧； clusterNodes_.size()表示一个簇内的节点个数,10,学 海 无 涯 config_.ssSlotTime_表示一个时间帧内的小的时隙 lstRndDelay表示缓冲时间 xmitTime_表示簇内所有节点的数据发送时间 createScheduler 函数主要语句如下：
14、,frameTime_,= (5 + clusterNodes_.size() * config_.ssSlotTime_;/计算时间帧,lstRndDelay_ = Random:uniform(0, 0.01);,/随机选取缓冲时间,xmitTime_= config_.ssSlotTime_ * (clusterNodes_.size() + lstRndDelay_; Scheduler:instance().schedule( eventHandler_, new LeachEvent( 而普通节点则需要在findBestCluster()中找到最优簇头（即距离最近的簇头）,11,学
15、 海 无 涯 后，执行clearClusterChoices() 4. 一些定义 （1）virtual double TxTime(int n) return n * 8.0 / 1000000.0; TxTime 指以 1 Mbps 的速度传输n bit 数据所需要的时间,五、 算法运行结果分析 1场景介绍 用ns 模拟每个节点向基站传输数据 Basic Configuration:,学 海 无 涯,图 3Basic Configuration 配置图 Access Point:,图 4Access Point 配置图 Common Node:,12,学 海 无 涯,图 5Common Node 配置图 输出得到TCL 文件。在ns 环境下运行该TCL 文件，得到trace 文件。 2. trace 文件分析 trace 的功能是详细记录模拟的过程，可以根据用户的需要记录模拟过程中的 任何一个细节。所有对模拟的分析是基于 trace 文件。截取一部分文件代码如下： 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
