快速了解LEACH算法

论文：

  1. Energy-efficient communication protocol for wireless microsensor networks HICSS’00 (DOI: 10.1109/HICSS.2000.926982)
  2. 主要内容：LEACH 算法(Low-Energy Adaptive Clustering Hierarchy)

引入 （Section 1）

  1. 低功耗传感器网络
    1. 精度不高
    2. 节点小巧，便宜，节能，便于大范围部署
    3. 具有容错性（非静态网络）
    4. 通过本地的协作（Local collaboration）来减少带宽压力
  2. 模型假设：
    1. 基站固定，远离距离传感器
    2. 所有节点类型相同，主要受能量约束（ energy-constrained）

      传输能耗计算 （Section 2）

      $ E_{elec} = 50nJ/bit $ 传输/接收电路运转所需能量，仅与二进制位数有关
      $ \epsilon_{amp} = 100nJ/bit/m^2 $ 传输放大器为了让接收者获得信号需要的能力，与二进制位数、传输距离的平方成正比
      令$k$为传输二进制位数，$d$为Tx和Rx之间的距离
      $ E_{Tx}(k,d) = E_{elec}·k+\epsilon_{amp}k·d^2$
      $ E_{Rx}(k,d) = E_{elec}·k$
  • 传输会消耗大量能量
  • 要权衡好传输距离和传输信息的次数

两种简单协议 （Section 3）

  • 直接传输协议：node 1->Base Station

    我放弃手动输入了，你自己写到ppt里吧

  • 最小传输能量协议：node 1->node 2->··· ->node n -> Base Station

MATLAB模拟：随机100个节点的网络，基站位于(0,-100处)

$$ 网络直径- E_{elec}-整体能量消耗 $$

这个图其实看看就好了，重点关注节点的死亡

节点的死亡：假设每个节点的电量是相同，由于传输信息消耗电量，一定轮次后节点的能量消耗殆尽。

180轮后直接传输和MTE的剩余节点

两种协议的缺陷：节点死亡的不均匀。 这不是在传感网中我们期望看到的

分簇

传感器网络的组织：分簇

拓展星形拓扑结构

大量的末端传感器作为簇终端节点(Cluster Node)，一个与终端节点进行数据交换的设备作为簇头节点(Cluster Head)，两者构成一簇。一般来说，为了避免多个簇终端节点同时向基站的同一频道传送数据，减少冲突导致的崩溃和数据重发，往往会采用一个多余的设备,称为高级簇头节点(Super Cluster Head)。簇与簇间以链式多跳的方式来传递簇内数据，最终收集于高级簇头节点中。高级簇头节点中的数据则通过若干转发节点(Transefer Node)将数据传送到基站。

簇头节点会消耗更多的能量

  • 静态分簇：固定的簇头节点,能量消耗不均，健壮性差
  • 动态分簇：LEACH，通过数学方法保证每个节点等概率、轮流的成为簇头节点
    等概率:每个还未曾成为簇头的节点等概率的成为簇头

LEACH算法细节 （Section 5）

簇头节点的选择

$$ P：期望的簇头率$$
$$ r：当前轮数$$
$$ G：上1/p轮中曾被选为簇头的节点集$$
P相当于课本的$\frac{k}{N}$,通过matlab实验发现设定为0.05时最佳
r=0时，T(n)=P,所有节点等概率的成为簇头；r=$\frac{1}{P}-1$时T(n)=1，所有剩余节点都被选为簇头，保证了每$\frac{1}{p}$轮内所有节点都会被选为簇头

建立簇

  1. 每个节点独立地计算自己是否成为簇头
  2. 簇头节点通过非坚持CSMA协议向周围发送信号，宣布自己为簇头；非簇头节点保持通信，根据每个簇头节点发送的信号强度，选择强度最大（消耗能量最少）者为簇头，并将自己的加入该簇的信息告知簇头。

通信

  1. 建立通讯时间表，以时分多址（TDMA）方式进行簇间通信
  2. 簇头节点始终开启，非簇头节点在通信时间以外可以关闭，节省电量
  3. 簇头节点进行数据压缩，减少与基站之间通信消耗的电量

其他细节：

  1. 簇间信号干扰： 频分多址
  2. 多层簇

LEACH协议的效果 （Section 4）

  1. 能量消耗远小于Direct和MTE两种协议，消耗能量约为其八分之一
  2. 能量消耗更均匀，第一个节点死亡的时间延长了8倍
  3. 节点均匀的死亡，更符合传感网的要求

总结 （Section 4）

  1. LEACH 算法的特点
    1. 本地化的簇建立和交流
    2. 自组网
    3. 随机、轮转的选择簇头节点
    4. 本地的数据压缩
  2. 延申的研究：
    1. 考虑节点剩余能量：LEACH-C算法等
    2. 节省簇间的能量消耗：EEUC竞选算法