目录
一、Leach协议与NS的关系 (2)
二、算法设计思想 (3)
三、簇头建立算法流程图 (4)
四、难点解决 (6)
五、算法运行结果分析 (9)
参考文献 (9)
一、Leach协议与NS的关系
为了实现leach 协议，对ns进行扩展。在ns中增加了一个事件驱动模拟器支持模拟无线传感器网络协议。这些扩展包括MAC协议，用于计算和交互的能量分配模型和leach协议的体系结构。
网络拓扑结构可以通过简单的Nodes, Links, Agents和Applications 描述。Nodes相当于网络中的终端主机， Links 是用于Nodes交互的连接器, Agent用来实现不同网络协议，是支持分组产生和丢弃的节点。Applications 用来产生数据和实现不同的应用函数。一旦网络拓扑结构建立起来后，模拟通过启动节点上的Applications运行。
为了在ns中支持无线传感器网络，在ns中增加了 mobile nodes, MAC 协议和信道传播模型Channel 。
Applications类的头文件用Tcl语言写的，节点中的其他函数功能用C++语言写成的。
数据包的发送过程：
Applications创建数据包（data packets）,然后发送给Agent. Agent执行协议栈中运输层和网络层的功能，将数据包发送给CMUTrace,。 CMUTrace将packets的统计数据写到trace 文件，然后将packets发至Connector。Connector将数据包传送给用于数据链路处理的链路层(LL).经过一小段时间的延迟后，数据包由LL发送给Queue缓冲队列。如果是还没有传送过的数据包，Queue将以队列进行存储。然后Queue将数据包出队列，发送到MAC层。然后开始运行MAC（媒体访问控制）协议。最终，packets被发送到网络接口层(Network Interface),网络接口层将packets加上正确的传输能量，然后将packets发送到Channel. Channel将packets进行拷贝，并发往连接信道的每一个节点。
发送过程可参考如下图1
数据包的接收过程：
数据包被节点的网络接口接收，并被向上传送至MAC层，Link-Layer, Connector, CMUTrace, 和Agent 函数. Agent 对数据包进行判定，并将数据包到达的信息通知给Application.
接收过程与发送过程传输的路径相反。
二、算法设计思想
Leach协议跨越几个层次实现的协议，Leachapp应用在最高层Application。它是自适应分簇拓扑算法。周期执行，每轮循环分为簇头的建立阶段和稳定的数据通信阶段。
（1）簇头建立阶段：初始阶段，每个节点从0和1中随机产生一个数，如果这个数小于阀值T（n），该节点就成为当前轮的簇头。
其中，P是期望的簇头数在所有节点中占的百分比，r是选举轮数，r mod (1/p)代表这一轮循环中当选过簇头的节点个数，G是这一轮循环中未当选过簇头的节点集合。
每个节点自主选择是否成为当前轮的簇头并通过广播的形式报告给其他节点。簇头通过CSMA MAC协议进行广播，所有的簇头以相同的传输能量进行广播。
簇头建立起来之后，每个非簇头节点要决定在当前轮中自己属于哪个簇头。非簇头节点根据收到的广播信号强度决定加入哪个簇头。非簇头节点决定了自己属于哪个簇头后，必须通知簇头节点它是该簇的成员。非簇头节点同样通过CSMA MAC协议将自己加入该簇的信息报告给簇头节点。
簇头节点收到所有的非簇头节点加入的信息后，基于本簇内加入的节点数目创建TDMA调度，通知每个节点什么时间可以传输数据。
在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; //将节点设置为簇头else
thresh = (double) k / (n - k * round_);
return thresh;
}
（2）数据传输阶段：
一个簇内的信息传输会影响相邻簇。为了减少这种信号干扰，各个簇内的信息交互通过不同的CDMA编码。簇头可以决定本簇中节点所用的CDMA编码。这个用于当前阶段的CDMA编码在广播簇头的时候发送给簇内节点。具体在advertiseClusterHead()中实现。
此外，簇头根据本簇内的节点个数创建TDMA调度。具体的，簇头在findBestCluster()函数中调用createSchedule()，而由createSchedule()函数具体创建TDMA调度。
当簇内节点收到这个消息后，它们会在各自的时间槽内发送数据。簇头节点收到所有的数据后执行信号处理函数压缩数据为一个信号，并将这个合成的信号发给基站。
三、簇头建立算法流程图
簇头的建立是在decideClusterHead()函数实现。具体流程图如图1
N
N
N
图1 簇头建立算法流程图
四、难点解决
1. CDMA 编码问题
Leach 协议中不同簇内用不同的CDMA 编码，同一个簇内采用同一个CDMA 编码进行数据传输。如果以各个簇头为结点，建立完全图。为了使各个簇采用不同的编码，利用PCA 边着色。
所谓PCA 边着色问题，指在完全图中给节点的每条邻接边分配不同的码。每个节点用一个码在其邻接边（即链路）上进行发送或接收数据。
以下，图2是PCA 着色问题的一个示例。
图2 PCA 边着色示意图