一种WSN分布式非均匀分簇方法

1.一种WSN分布式非均匀分簇方法，包括：
步骤1：设置网络场景；
在预设的监测区域内随机分布N个传感器节点，在该监测区域外布置一个网关节点，每个传感器节点具有唯一的身份标识号；
步骤2：网络初始化；
各节点通过广播“初始化消息”建立“邻居节点列表”，所述“邻居节点列表”中包括邻居节点身份标识号、邻居节点离网关节点的距离；
其特征在于：
步骤3：计算候选概率；
每个传感器节点按照公式(1)计算自己成为候选簇首的概率，
si.P＝P0×Di×Ei (1)
其中si.P表示传感器节点Si的候选概率，P0是传感器节点成为候选簇首的初始概率，Di为传感器节点Si的位置因子，Ei为传感器节点Si的平均能量因子，且其中，Dmax和Dmin分别表示网关节点到网络的最大距离和
最小距离，si.dist为传感器节点Si到网关节点的距离，si.Eres为传感器节点Si的剩余能量，Eave为全网平均剩余能量；
步骤4：产生随机数判断是否成为候选簇首；
每个传感器节点自动生成一个随机数μ，μ∈(0，1)，如果传感器节点Si产生的随机数μ＜si.P，则成为候选簇首，否则进入休眠状态；
步骤5：竞选最终簇首；
候选簇首按照公式(2)计算自己的等待时间，按照公式(3)计算自己的竞争半径；
其中si.T表示传感器节点Si的等待时间，α是(0，1)的常数，si.Neg表示传感器节点Si的邻居节点数目，si.E0为传感器节点Si的初始能量，Cr是(0.9，1)的随机数，T0为时间常数，si.RC是传感器节点Si的竞争半径，dmax和dmin分别表示网络模型中传感器节点到网关节点距离的最大值和最小值，Rmax是候选簇首竞争半径的最大值，c1，c2，c3为(0，1)的常数；
候选簇首中的传感器节点Si如果在等待时间si.T内收到其他候选簇发出的竞选成功消息，则退出竞争进入休眠状态；否则，传感器节点Si成为最终簇首，并在等待时间si.T结束时刻以竞争半径si.RC广播竞选成功消息；
步骤6：加入簇首；
唤醒所有处于休眠状态的非簇首节点，让非簇首节点按照公式(4)计算能耗函数值；
其中i∈CH，CH为最终簇首节点的集合；j∈CM，CM为非簇首节点的集合；d(i，j)表示非簇首节点sj与最终簇首节点si之间的距离，β是(0，1)的权重常数，W(j，i)即为非簇首节点sj相对于最终簇首节点si的能耗函数值；
非簇首节点sj选择集合CM中能耗函数值最大的一个最终簇首节点作为自己的簇头并加入。
2.根据权利要求1所述的一种WSN分布式非均匀分簇方法，其特征在于：P0＝0.4，c1＝0.25，c2＝0.3，c3＝0.2，α＝0.3，β＝0.5， 且Eelec＝
2
50nJ/bit，εfs＝10pJ/(bit·m)。

一种WSN分布式非均匀分簇方法\n技术领域\n[0001] 本发明涉及到无线传感器网络路由技术中的分簇算法，具体地说，是一种WSN分布式非均匀分簇方法。\n背景技术\n[0002] 无线传感器网络(Wireless Sensor Networks：WSN)通过大量部署在监测区域内的传感器节点，以多跳的无线通信方式，将采集的感知信息汇聚于网关节点，传输给终端用户。由此可见，网关节点附近区域的传感器节点将承担大量数据转发，其能量消耗水平将高于其他区域，从而而被称为“热区”，热区内的传感器节点过早消耗完自己的能量最终死亡导致网络失效称为能量空洞现象。\n[0003] 当前避免能量空洞的方法主要通过最大限度地均衡网络负载，许多学者从不同方面采取应对策略，例如：节点初始能量不均匀配置、节点功率控制以及节点非均匀部署等等，以上策略可以使“热区”能量充足，但对传感器节点要求较高，需特定部署，不易操作。也有人采用动态网关节点或者部署多个网关节点，这样传感器节点可以选择最佳网关节点传输数据来减少能量消耗，但是改变网关节点的位置或增加其数量都需耗费大量成本。\n[0004] 因此，提出一种灵活高效易实现的分簇路由策略来均衡网络负载很有必要。现有技术中，文献：李成法，陈贵海，叶懋，等.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报，2007，30(1)：27-36提出了一种经典的非均匀分簇路由协议EEUC，该协议中候选簇首通过非均匀的竞争范围构造大小不等的簇来缓解“热区”问题。参考文献：CHEN Gui-hai，LI Cheng-fa，YE Mao，et al.An unequal cluster-based routing protocol in wireless sensor networks[J].Wireless Networks，2009，15(2)：193-207.在上述协议的基础上对簇间路由进行改进并提出一种UCR算法，从而节约中继节点的能量。\n[0005] 现有技术的缺点是：在EEUC协议和UCR算法中，节点部署及候选簇首选择的随机性可能导致处于网络边缘或者能量较低的节点当选为簇首；并且仅采用局部比较节点剩余能量来选择最终簇首无法从整体上协调全网的能量消耗来避免能量空洞，同时也无法保证网络完全覆盖；所采取的就近入簇和固定路由方式也不利于均衡簇间能量消耗。\n发明内容\n[0006] 为了解决上述缺陷，本发明提出一种WSN分布式非均匀分簇方法，该方法在平衡全网能量的基础上选择出候选簇首，并通过自适应校正竞争半径进行非均匀分簇，最后节点根据基于能量和距离的能耗函数选择最佳簇加入，避免能量空洞，最终实现高效的数据传输。\n[0007] 本发明的具体技术方案如下：\n[0008] 一种WSN分布式非均匀分簇方法，包括：\n[0009] 步骤1：设置网络场景；\n[0010] 在预设的监测区域内随机分布N个传感器节点，在该监测区域外布置一个网关节点，每个传感器节点具有唯一的身份标识号；\n[0011] 步骤2：网络初始化；\n[0012] 各节点通过广播“初始化消息”建立“邻居节点列表”，所述“邻居节点列表”中包括邻居节点身份标识号、邻居节点离网关节点的距离；\n[0013] 其关键在于：\n[0014] 步骤3：计算候选概率；\n[0015] 每个传感器节点按照公式(1)计算自己成为候选簇首的概率，\n[0016] si.P＝P0×Di×Ei (1)\n[0017] 其中si.P表示传感器节点Si的候选概率，P0是传感器节点成为候选簇首的初始概率，Di为传感器节点Si的位置因子，Ei为传感器节点Si的平均能量因子，且其中，Dmax和Dmin分别表示网关节点到网络的最大距离和\n最小距离，si.dist为传感器节点Si到网关节点的距离，si.Eres为传感器节点Si的剩余能量，Eave为全网平均剩余能量；\n[0018] 步骤4：产生随机数判断是否成为候选簇首；\n[0019] 每个传感器节点自动生成一个随机数μ，μ∈(0，1)，如果传感器节点Si产生的随机数μ＜si.P，则成为候选簇首，否则进入休眠状态；\n[0020] 步骤5：竞选最终簇首；\n[0021] 候选簇首按照公式(2)计算自己的等待时间，按照公式(3)计算自己的竞争半径；\n[0022] \n[0023] \n[0024] 其中si.T表示传感器节点Si的等待时间，α是(0，1)的常数，si.Neg表示传感器节点Si的邻居节点数目，si.E0为传感器节点Si的初始能量，Cr是(0.9，1)的随机数，T0为时间常数，si.RC是传感器节点Si的竞争半径，dmax和dmin分别表示网络模型中传感器节点到网关节点距离的最大值和最小值，Rmax是候选簇首竞争半径的最大值，c1，c2，c3为(0，\n1)的常数；\n[0025] 候选簇首中的传感器节点Si如果在等待时间si.T内收到其他候选簇发出的竞选成功消息，则退出竞争进入休眠状态；否则，传感器节点Si成为最终簇首，并在等待时间si.T结束时刻以竞争半径si.RC广播竞选成功消息；\n[0026] 步骤6：加入簇首；\n[0027] 唤醒所有处于休眠状态的非簇首节点，让非簇首节点按照公式(4)计算能耗函数值；\n[0028] \n[0029] 其中i∈CH，CH为最终簇首节点的集合；j∈CM，CM为非簇首节点的集合；d(i，j)表示非簇首节点sj与最终簇首节点si之间的距离，β是(0，1)的权重常数，W(j，i)即为非簇首节点sj相对于最终簇首节点si的能耗函数值；\n[0030] 非簇首节点sj选择集合CM中能耗函数值最大的一个最终簇首节点作为自己的簇头并加入。\n[0031] 作为最优，上述公式中的各个参数设置如下：P0＝0.4，c1＝0.25，c2＝0.3，c3＝0.2，α＝0.3，β＝0.5， 且Eelec＝50nJ/bit，εfs＝10pJ/\n(bit·m2)。\n[0032] 本发明的显著效果是：算法简单，容易实现，针对无线传感器网络中存在的能量空洞问题，在已有分簇路由协议的基础上提出的一种分布式非均匀分簇算法。算法在选择候选簇首时引入位置因子和平均能量因子以平衡全网节点的剩余能量，综合考虑节点剩余能量和邻居节点数目选择最终簇首以保证网络完全覆盖，基于能量和距离的能耗函数入簇机制，均衡了全网负载，本方法能有效的避免能量空洞，延长网络生命周期，缓解“热区”问题。\n附图说明\n[0033] 图1是本发明的网络拓扑示意图；\n[0034] 图2是本发明的工作流程图；\n[0035] 图3是全网存活节点数目分析图；\n[0036] 图4是热区节点剩余能量分析图。\n具体实施方式\n[0037] 下面结合附图和具体实施例对本发明作进一步详细说明。\n[0038] 如图1，图2所示，一种WSN分布式非均匀分簇方法，包括：\n[0039] 步骤1：设置网络场景；\n[0040] 在预设的监测区域内随机分布N个传感器节点，在该监测区域外布置一个网关节点，每个传感器节点具有唯一的身份标识号，本实施例中的监测区域为(0，0)～(200，200)m的正方形区域，传感器节点总数N＝400。\n[0041] 步骤2：网络初始化；\n[0042] 各节点通过广播“初始化消息”建立“邻居节点列表”，所述“邻居节点列表”中包括邻居节点身份标识号、邻居节点离网关节点的距离。在实施过程中，首先让网关节点以特定的发送功率向网络中广播信号，每个传感器节点接收该信号并根据其强度计算自己到网关节点的距离。随后每个节点以固定的功率半径广播“初始化消息”来建立“邻居节点列表”。.\n[0043] 步骤3：计算候选概率；\n[0044] 由于节点部署的随机性，随机竞选候选簇首的方式可能造成处于网络边缘的节点竞选成功，而能量高的节点反而竞选失败，这无疑不利于平衡网络能量而影响网络寿命。因此，本方法让每个传感器节点按照公式(1)计算自己成为候选簇首的概率。\n[0045] si.P＝P0×Di×Ei (1)\n[0046] 其中si.P表示传感器节点Si的候选概率，P0是传感器节点成为候选簇首的初始概率，Di为传感器节点Si的位置因子，Ei为传感器节点Si的平均能量因子，且其中，Dmax和Dmin分别表示网关节点到网络的最大距离和\n最小距离，si.dist为传感器节点Si到网关节点的距离，si.Eres为传感器节点Si的剩余能量，Eave为全网平均剩余能量。\n[0047] 通过引用位置因子和平均能量因子来平衡全网能量，使得离网关节点越近，剩余能量占全网平均能量比重越大的节点成为候选簇首的概率越大。\n[0048] 步骤4：产生随机数判断是否成为候选簇首；\n[0049] 每个传感器节点自动生成一个随机数μ，μ∈(0，1)，如果传感器节点Si产生的随机数μ＜si.P，则成为候选簇首，否则进入休眠状态；\n[0050] 步骤5：竞选最终簇首；\n[0051] 候选簇首按照公式(2)计算自己的等待时间，按照公式(3)计算自己的竞争半径；\n[0052] \n[0053] \n[0054] 其中si.T表示传感器节点Si的等待时间，α是(0，1)的常数，si.Neg表示传感器节点Si的邻居节点数目，si.E0为传感器节点Si的初始能量，Cr是(0.9，1)的随机数，T0为时间常数，si.RC是传感器节点Si的竞争半径，dmax和dmin分别表示网络模型中传感器节点到网关节点距离的最大值和最小值，Rmax是候选簇首竞争半径的最大值，c1，c2，c3为(0，\n1)的常数；\n[0055] 候选簇首中的传感器节点Si如果在等待时间si.T内收到其他候选簇发出的竞选成功消息，则退出竞争进入休眠状态；否则，传感器节点Si成为最终簇首，并在等待时间si.T结束时刻以竞争半径si.RC广播竞选成功消息；\n[0056] 本方法中，最终簇首的选择采用定时器竞争机制，综合考虑节点的剩余能量和邻居节点数目，避免出现无法覆盖整个网络，造成网络失衡的情况。\n[0057] 步骤6：加入簇首；\n[0058] 唤醒所有处于休眠状态的非簇首节点，让非簇首节点按照公式(4)计算能耗函数值；\n[0059] \n[0060] 其中i∈CH，CH为最终簇首节点的集合；j∈CM，CM为非簇首节点的集合；d(i，j)表示非簇首节点sj与最终簇首节点si之间的距离，β是(0，1)的权重常数，W(j，i)即为非簇首节点sj相对于最终簇首节点si的能耗函数值；\n[0061] 非簇首节点sj选择集合CM中能耗函数值最大的一个最终簇首节点作为自己的簇头并加入。\n[0062] 由于节点加入哪个簇关系到平衡当前簇头地区的能量消耗。而现有分簇路由算法几乎都采取就近入簇，常常造成离网关近的簇规模反而比离网关节点远的簇规模大，导致处于“热区”的簇首簇内负担过重，不利于平衡全网能量消耗。为此，本方法提出一种基于能量和距离的能耗函数入簇机制，使得节点会尽量选择与簇首距离近，簇首剩余能量多且簇规模大的簇(离网关节点远的簇)加入，平衡了簇内和簇间负载。\n[0063] 作为最优，上述各式中的相关参数设置如下：P0＝0.4，c1＝0.25，c2＝0.3，c3＝0.2，α＝0.3，β＝0.5， 且Eelec＝50nJ/bit，εfs＝10pJ/\n2\n(bit·m)。\n[0064] 利用本方法让各传感器节点竞选成簇，在数据传输过程中，既包括簇内数据传输，又包括簇间数据传输。其中簇内数据传输采用文献：Heinzelman W R，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications，2002，\n1(4)：660-670.提出的LEACH算法。簇间数据传输采用多跳动态路由的方式。路由构建时，所有非簇首节点进入睡眠状态。每个簇首以相同概率广播其状态信息STATE_MSG(ID，si.Eres，si.dist)，若簇首节点si到网关节点的距离si.dist小于阈值TD_MAX，则直接与网关节点通信，否则在自己的路由转发集合 中随机\n动态选取一个簇首作为转发节点多跳传送给网关节点。若簇首节点si的si.RCH为空，则与网关节点直接通信。采取动态路由方式虽然不及每次选取最优的转发节点，但可避免固定的转发路径导致转发节点因能量消耗过快而死亡，均衡了中继簇首节点的能量消耗，进而均衡了全网能量消耗。\n[0065] 如图3，图4所示，将本方法与UCR算法进行比较，可以看出网络中存活节点数随时间变化的情况，本方法全网节点死亡时间较晚，网络生命周期长，经过1000轮数据传输后，本方法处于“热区”节点的剩余能量明显高于UCR算法，降低了处于“热区”的簇首能量消耗速度，均衡了全网能量消耗，有效避免了能量空洞。