本发明涉及无线传感器网络领域，特别是涉及一种无线传感器网络的分簇路由方法及系统。
背景技术：
随着物联网的发展，作为数据感知与收集的重要通信技术之一具有低成本、自组织等特点的无线传感器网络得到大规模的应用。
无线传感器网络由大量的微体积无线传感器构成，体积微小导致传感器所装配的电池容量有限。在多种应用场景下由于传感器分布范围广泛、环境恶劣等因素导致不能进行及时的电池更换。所以，能量是限制无线传感器网络寿命的重要因素。
为延长无线传感器网络的寿命，提出了多种多样的能量路由策略。通过簇首数据融合减少传输数据量，但导致簇首早亡；为分担簇首能耗，提出双簇首方案，将数据融合和收集能耗与数据传输能耗分摊到两个节点上，但负责转发数据的簇首能量消耗过快；为减少数据传输能耗，采用簇首与基站多跳的通信方式以减少长距离传输，以达到节约簇首能耗，延长网络寿命的目的，但导致近基站节点能耗过快，出现“能量空洞”。
技术实现要素：
本发明的目的是提供一种无线传感器网络的分簇路由方法及系统，以解决目前的无线传感器网络出现的能量空洞的问题。
为实现上述目的，本发明提供了如下方案：
一种无线传感器网络的分簇路由方法，包括：
利用所述基站收集无线传输网络中的节点信息，并根据所述节点信息构建初始最低能耗路径树；所述节点信息包括节点位置、节点能量以及节点id；
计算所述初始最低能耗路径树中除所述基站外的节点的第一簇首竞争系数，逐一进行第一批簇首选择和节点入簇，构建第一分簇树并更新所述初始最低能耗路径树，确定一次更新后的最低能耗路径树；
计算所述一次更新后的最低能耗路径树中除所述基站外的节点的第二簇首竞争系数，逐一进行第二批簇首选择和节点入簇，构建第二分簇树并更新所述一次更新后的最低能耗路径树，确定二次更新后的最低能耗路径树；
根据所述第一分簇树以及第二分簇树计算已有簇首对于所述二次更新后的最低能耗路径树中除所述基站外的节点的第三入簇竞争系数；
判断所述第三入簇竞争系数是否为-∞，得到第一判断结果；
若所述第一判断结果表示为所述第三入簇竞争系数为-∞，将未入簇的节点按照所述初始最低能耗路径树中的路径与基站进行通信，并选择所述初始最低能耗路径树中所述基站的子节点作为中继节点；
计算簇首以及所述中继节点之间的通信能耗；
根据所述通信能耗计算簇首到所述基站的最小权值路径，将所述最小权值路径作为所述簇首与所述基站的通信路径，并根据所述所述簇首与所述基站的通信路径确定所述节点与所述基站的通信路径；
确定所有所述节点按照所述节点与所述基站的通信路径将所述节点信息上传至所述基站；
若所述第一判断结果表示为所述第三入簇竞争系数不为-∞，依照所述第三入簇竞争系数对所述二次更新后的最低能耗路径树内的节点进行入簇操作，每当一个所述二次更新后的最低能耗路径树内的节点完成入簇，更新所述二次更新后的最低能耗路径树内的节点加入的分簇树以及所述二次更新后的最低能耗路径树。
可选的，所述利用所述基站收集无线传输网络中的节点信息，并根据所述节点信息构建初始最低能耗路径树，具体包括：
根据所述节点信息计算任意两个所述节点所建立的连接边的权值，生成连接边的第一权值矩阵；
根据所述连接边的第一权值矩阵计算存活节点到所述基站的最小权值通信路由；
根据所述存活节点到所述基站的最小权值通信路由，将所述存活节点的下一跳节点作为所述存活节点的父节点，构建以所述基站为根节点的初始最低能耗路径树。
可选的，所述计算所述初始最低能耗路径树中除所述基站外的节点的第一簇首竞争系数，逐一进行第一批簇首选择和节点入簇，构建第一分簇树并更新所述初始最低能耗路径树，确定一次更新后的最低能耗路径树，具体包括：
选取所述第一簇首竞争系数满足簇首竞争系数阈值范围内最大的第一簇首竞争系数对应的节点作为簇首；
以所述簇首为根节点的子树作为第一分簇树，并保留所述第一分簇树内的通信路径；
删除所述第一分簇树中的节点以及节点关联的边从所述初始最低能耗路径树中，确定一次更新后的最低能耗路径树。
可选的，所述删除所述第一分簇树中的节点以及节点关联的边从所述初始最低能耗路径树中，确定一次更新后的最低能耗路径树，之后还包括：
若所述最大的第一簇首竞争系数小于所述簇首竞争系数阈值范围的下限，且已选出的簇首数量未达到簇首数量阈值，同时所述无线传感器网络内仍存在未入簇的节点，执行“计算所述一次更新后的最低能耗路径树中除所述基站外的节点的第二簇首竞争系数，逐一进行第二批簇首选择和节点入簇，构建第二分簇树并更新所述一次更新后的最低能耗路径树，确定二次更新后的最低能耗路径树”；
若已选出的簇首数量超出簇首数量阈值且无线传感器网络中仍存在未入簇的节点，执行“根据所述第一分簇树以及第二分簇树计算已有簇首对于所述二次更新后的最低能耗路径树中除所述基站外的节点的第三入簇竞争系数”；
若所述一次更新后的最低能耗路径树仅剩余所述基站时，执行“选择所述初始最低能耗路径树中所述基站的子节点作为中继节点”。
可选的，所述计算所述一次更新后的最低能耗路径树中除所述基站外的节点的第二簇首竞争系数，逐一进行第二批簇首选择和节点入簇，构建第二分簇树并更新所述一次更新后的最低能耗路径树，确定二次更新后的最低能耗路径树，具体包括：
判断所述第二簇首竞争系数是否均为0，得到第二判断结果；
若所述第二判断结果表示为所述第二簇首竞争系数均为0，执行“根据所述第一分簇树以及第二分簇树计算已有簇首对于所述二次更新后的最低能耗路径树中除所述基站外的节点的第三入簇竞争系数”；
若所述第二判断结果表示为所述第二簇首竞争系数不均为0，选取所述第二簇首竞争系数内最大的第二簇首竞争系数对应的节点作为簇首；
以所述簇首为根节点的子树作为第二分簇树，并保留所述第二分簇树内的通信路径；
删除所述第二分簇树中的节点以及节点关联的边从所述一次更新后的最低能耗路径树中，确定二次更新后的最低能耗路径树。
可选的，所述更新所述二次更新后的最低能耗路径树内的节点加入的分簇树以及所述二次更新后的最低能耗路径树，之后还包括：
获取更新后的当前最低能耗路径树；
若所述当前最低能耗路径树仅剩余所述基站时，执行“选择所述初始最低能耗路径树中所述基站的子节点作为中继节点”。
可选的，所述根据所述通信能耗计算簇首到所述基站的最小权值路径，将所述最小权值路径作为所述簇首与所述基站的通信路径，并根据所述所述簇首与所述基站的通信路径确定所述节点与所述基站的通信路径，具体包括：
获取所述当前最低能耗路径树对应的当前路由状态下簇首或中继节点的负载估计值；
基于所述负载估计值，计算所述所述当前最低能耗路径树中任意两个所述节点所建立的连接边的权值，生成连接边的第二权值矩阵；
根据所述连接边的第二权值矩阵计算各个所述簇首到所述基站的最小权值通信路由。
可选的，所述确定所有所述节点按照所述节点与所述基站的通信路径将所述节点信息上传至所述基站，之后还包括：
判断所述簇首和所述中继节点的能量是否低于将所述节点信息上传至所述基站的节点对应的能量阈值，得到第三判断结果；所述能量阈值为在上一轮节点信息传输过程中，将所述节点信息上传至所述基站的节点的剩余能量的50％；
若所述第三判断结果表示为所述簇首和所述中继节点的能量低于将所述节点信息上传至所述基站的节点对应的能量阈值，执行“利用所述基站收集无线传输网络中的节点信息，并根据所述节点信息构建初始最低能耗路径树”；
若所述第三判断结果表示为所述簇首和所述中继节点的能量未低于将所述节点信息上传至所述基站的节点对应的能量阈值，按照上一轮节点信息传输过程中的所述节点与所述基站的通信路径进行通信。
一种无线传感器网络的分簇路由系统，包括：
初始最低能耗路径树构建模块，用于利用所述基站收集无线传输网络中的节点信息，并根据所述节点信息构建初始最低能耗路径树；所述节点信息包括节点位置、节点能量以及节点id；
一次更新后的最低能耗路径树确定模块，用于计算所述初始最低能耗路径树中除所述基站外的节点的第一簇首竞争系数，逐一进行第一批簇首选择和节点入簇，构建第一分簇树并更新所述初始最低能耗路径树，确定一次更新后的最低能耗路径树；
二次更新后的最低能耗路径树确定模块，用于计算所述一次更新后的最低能耗路径树中除所述基站外的节点的第二簇首竞争系数，逐一进行第二批簇首选择和节点入簇，构建第二分簇树并更新所述一次更新后的最低能耗路径树，确定二次更新后的最低能耗路径树；
第三入簇竞争系数确定模块，用于根据所述第一分簇树以及第二分簇树计算已有簇首对于所述二次更新后的最低能耗路径树中除所述基站外的节点的第三入簇竞争系数；
第一判断模块，用于判断所述第三入簇竞争系数是否为-∞，得到第一判断结果；
中继节点选择模块，用于若所述第一判断结果表示为所述第三入簇竞争系数为-∞，将未入簇的节点按照所述初始最低能耗路径树中的路径与基站进行通信，并选择所述初始最低能耗路径树中所述基站的子节点作为中继节点；
通信能耗计算模块，用于计算簇首以及所述中继节点之间的通信能耗；
节点与基站的通信路径确定模块，用于根据所述通信能耗计算簇首到所述基站的最小权值路径，将所述最小权值路径作为所述簇首与所述基站的通信路径，并根据所述所述簇首与所述基站的通信路径确定所述节点与所述基站的通信路径；
上传模块，用于确定所有所述节点按照所述节点与所述基站的通信路径将所述节点信息上传至所述基站；
最低能耗路径树更新模块，用于若所述第一判断结果表示为所述第三入簇竞争系数不为-∞，依照所述第三入簇竞争系数对所述二次更新后的最低能耗路径树内的节点进行入簇操作，每当一个所述二次更新后的最低能耗路径树内的节点完成入簇，更新所述二次更新后的最低能耗路径树内的节点加入的分簇树以及所述二次更新后的最低能耗路径树。
可选的，所述初始最低能耗路径树构建模块，具体包括：
第一权值矩阵生成单元，用于根据所述节点信息计算任意两个所述节点所建立的连接边的权值，生成连接边的第一权值矩阵；
最小权值通信路由计算单元，用于根据所述连接边的第一权值矩阵计算存活节点到所述基站的最小权值通信路由；
初始最低能耗路径树构建单元，用于根据所述存活节点到所述基站的最小权值通信路由，将所述存活节点的下一跳节点作为所述存活节点的父节点，构建以所述基站为根节点的初始最低能耗路径树。
根据本发明提供的具体实施例，本发明公开了以下技术效果：本发明提供了一种无线传感器网络的分簇路由方法及系统，基于最低能耗路径树进行簇的分批逐次构建，在簇首选择与分簇树构建过程的同时完成簇内节点与簇首的通信路由的规划，并在不同簇首选择阶段的选择簇首，依据分簇状况对未入簇节点进行入簇，从而降低了近基站节点能耗，缓解了“能量空洞”的问题。
附图说明
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1为本发明所提供的无线传感器网络的分簇路由方法流程图；
图2为本发明所提供的另一种无线传感器网络的分簇路由方法流程图；
图3为图2中第一批簇首选择与节点入簇,构分簇树并更新最低能耗路径树的方法流程图；
图4为图2中第二批簇首选择与节点入簇,构建分簇树并更新最低能耗路径树的方法流程图；
图5为图2中节点入簇，分簇树的更新与最低能耗路径树的更新的方法流程图；
图6为无线传感器网络运行至轮数为1000时得到的节点死亡与轮数关系示意图；
图7为无线传感器网络运行至轮数为1000时得到的网络丢包率与轮数关系示意图；
图8为无线传感器网络运行至轮数为1000时得到的网络吞吐量与轮数关系示意图；
图9为无线传感器网络运行至轮数为1000时得到的网络剩余与轮数关系示意图；
图10为本发明所提供的无线传感器网络的分簇路由系统结构图。
具体实施方式
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
本发明的目的是提供一种无线传感器网络的分簇路由方法及系统，能够降低近基站节点能耗，缓解“能量空洞”的问题。
为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。
图1为本发明所提供的无线传感器网络的分簇路由方法流程图，如图1所示，一种无线传感器网络的分簇路由方法，包括：
步骤101：利用所述基站收集无线传输网络中的节点信息，并根据所述节点信息构建初始最低能耗路径树；所述节点信息包括节点位置、节点能量以及节点id；
所述步骤101具体包括：根据所述节点信息计算任意两个所述节点所建立的连接边的权值，生成连接边的第一权值矩阵；根据所述连接边的第一权值矩阵计算存活节点到所述基站的最小权值通信路由；根据所述存活节点到所述基站的最小权值通信路由，将所述存活节点的下一跳节点作为所述存活节点的父节点，构建以所述基站为根节点的初始最低能耗路径树。
步骤102：计算所述初始最低能耗路径树中除所述基站外的节点的第一簇首竞争系数，逐一进行第一批簇首选择和节点入簇，构建第一分簇树并更新所述初始最低能耗路径树，确定一次更新后的最低能耗路径树；
所述步骤102具体包括：选取所述第一簇首竞争系数满足簇首竞争系数阈值范围内最大的第一簇首竞争系数对应的节点作为簇首；以所述簇首为根节点的子树作为第一分簇树，并保留所述第一分簇树内的通信路径；删除所述第一分簇树中的节点以及节点关联的边从所述初始最低能耗路径树中，确定一次更新后的最低能耗路径树。
所述删除所述第一分簇树中的节点以及节点关联的边从所述初始最低能耗路径树中，确定一次更新后的最低能耗路径树，之后还包括：
若所述最大的第一簇首竞争系数小于所述簇首竞争系数阈值范围的下限，且已选出的簇首数量未达到簇首数量阈值，同时所述无线传感器网络内仍存在未入簇的节点，执行步骤103。
若已选出的簇首数量超出簇首数量阈值且无线传感器网络中仍存在未入簇的节点，执行“步骤104。
若所述一次更新后的最低能耗路径树仅剩余所述基站时，执行步骤106。
步骤103：计算所述一次更新后的最低能耗路径树中除所述基站外的节点的第二簇首竞争系数，逐一进行第二批簇首选择和节点入簇，构建第二分簇树并更新所述一次更新后的最低能耗路径树，确定二次更新后的最低能耗路径树；
所述步骤103具体包括：判断所述第二簇首竞争系数是否均为0，若是，执行步骤104；若否，选取所述第二簇首竞争系数内最大的第二簇首竞争系数对应的节点作为簇首；以所述簇首为根节点的子树作为第二分簇树，并保留所述第二分簇树内的通信路径；删除所述第二分簇树中的节点以及节点关联的边从所述一次更新后的最低能耗路径树中，确定二次更新后的最低能耗路径树。
所述更新所述二次更新后的最低能耗路径树内的节点加入的分簇树以及所述二次更新后的最低能耗路径树，之后还包括：获取更新后的当前最低能耗路径树；若所述当前最低能耗路径树仅剩余所述基站时，执行“选择所述初始最低能耗路径树中所述基站的子节点作为中继节点”。
步骤104：根据所述第一分簇树以及第二分簇树计算已有簇首对于所述二次更新后的最低能耗路径树中除所述基站外的节点的第三入簇竞争系数；
步骤105：判断所述第三入簇竞争系数是否为-∞，若是，执行步骤106，若否，执行步骤110。
步骤106：将未入簇的节点按照所述初始最低能耗路径树中的路径与基站进行通信，并选择所述初始最低能耗路径树中所述基站的子节点作为中继节点。
步骤107：计算簇首以及所述中继节点之间的通信能耗。
步骤108：根据所述通信能耗计算簇首到所述基站的最小权值路径，将所述最小权值路径作为所述簇首与所述基站的通信路径，并根据所述所述簇首与所述基站的通信路径确定所述节点与所述基站的通信路径。
所述步骤108具体包括：获取所述当前最低能耗路径树对应的当前路由状态下簇首或中继节点的负载估计值；基于所述负载估计值，计算所述所述当前最低能耗路径树中任意两个所述节点所建立的连接边的权值，生成连接边的第二权值矩阵；根据所述连接边的第二权值矩阵计算各个所述簇首到所述基站的最小权值通信路由。
步骤109：确定所有所述节点按照所述节点与所述基站的通信路径将所述节点信息上传至所述基站。
所述步骤109之后还包括：判断所述簇首和所述中继节点的能量是否低于将所述节点信息上传至所述基站的节点对应的能量阈值；所述能量阈值为在上一轮节点信息传输过程中，将所述节点信息上传至所述基站的节点的剩余能量的50％；若是，执行步骤101；若否，按照上一轮节点信息传输过程中的所述节点与所述基站的通信路径进行通信。
步骤110：依照所述第三入簇竞争系数对所述二次更新后的最低能耗路径树内的节点进行入簇操作，每当一个所述二次更新后的最低能耗路径树内的节点完成入簇，更新所述二次更新后的最低能耗路径树内的节点加入的分簇树以及所述二次更新后的最低能耗路径树。
基于本发明所提供的无线传感器网络的分簇路由方法，作为本发明可选的另一种无线传感器网络的分簇路由方法，如图2所示，具体包括如下步骤：
步骤s1：基站收集节点的信息，将无线传感器网络抽象为简单图，任意两点间的无线信道抽象为以传输单位数据能耗为边权的边，通过dijstra算法计算得到各节点到基站的路径，并由这些路径建立以基站为根节点的初始最低能耗路径树。
步骤s2：依据最低能耗路径树，计算节点的簇首竞争系数，逐一进行第一批簇首选择和节点入簇，构建第一分簇树并更新初始最低能耗路径树，更新后的初始最低能耗路径树为一次更新后的最低能耗路径树，本发明中最低能耗路径树与分簇树始终互斥，两者不含相同的顶点或边。
步骤s3：依据当前最低能耗路径树，计算节点的簇首竞争系数并进行第二批簇首选择和节点入簇，构建第二分簇树并更新一次更新后的最低能耗路径树，一次更新后的最低能耗路径树为二次更新后的最低能耗路径树；最低能耗路径树的每次更新均是对上一次的最低能耗路径树进行更新。
步骤s4：依据步骤s2，s3构建的分簇树，计算已有簇首对于当前最低能耗路径树中除根节点外的节点的入簇竞争系数，依照入簇竞争系数对这些节点进行入簇操作，每当一个节点完成入簇，则更新该节点加入的分簇树及当前网络的最低能耗路径树，当节点的入簇竞争系数均为-∞时，将初始时最低能耗路径树中节点到基站的路径作为无线传感器网络中节点与基站通信的路径，或当最低能耗路径树中仅有基站时，该步骤结束进入步骤s5。
步骤s5：选择初始最低能耗路径树中基站的子节点作为中继节点；计算簇首节点、中继节点间的通信能耗，将其作为两节点间的边权值，采用dijstra算法计算簇首节点到基站的最小权值路径，并将其作为簇首与基站的通信路径。
步骤s6：节点按照所得路径将数据上传至基站，下一轮开始时，若存在簇首和中继节点的能量低于该节点对应的阈值et(i)(该节点在上一轮开始时的剩余能量的50％)，则返回步骤s1，否则，节点继续按照上一轮的路径与基站进行通信。
进一步地，步骤s1具体包括以下步骤：
步骤s11：基站向分布在无线传感器网络监测区域内的节点广播节点信息收集请求，节点收到请求后采用泛洪法将节点的位置、节点的能量、节点的id信息发送到基站。
步骤s12：基站根据收集到的节点信息计算任意两节点所建立连接边的权值，生成第一权值矩阵w，节点i与节点j间的关联边的权值计算公式为：
节点i与基站bs间的关联边的权值计算公式为：
其中，节点i与节点j均为当前无线传感器网络监测区域中剩余能量大于零的节点，即为存活节点，当i＝j时，w(i,j)＝ ∞，eelec为接收电路和发射电路处理单位比特数据的能耗，εmp为多路径传输信道模型的衰减系数，εfs为自由信道传输模型的衰减系数，d(i,j)为节点i到节点j的欧式距离，d(i,bs)为节点i到基站bs的欧氏距离，packet(i)为当前路由结果下预测节点i所需转发的数据包数量，d0为距离阈值，计算方式如下：
步骤s13：根据步骤s12得到的连接边的权值矩阵w，采用dijstra算法计算存活节点到基站的最小权值路由。
步骤s14：根据步骤s13得到的最小权值路由，将节点的下一跳节点作为该节点的父节点，依照此规律建立初始的最低能耗路径树，该树以基站作为根节点。
在本发明中，如图3所示，步骤s2具体包括以下步骤：
步骤s21：计算当前最低能耗路径树中除基站外的节点的簇首竞争系数，节点i在本步骤中的簇首竞争系数计算公式为：
其中，k(i)为节点i的汇聚介数，计算公式如下：
其中，m(i)为在当前最低能耗路径树中以节点i为根节点的子树中的节点数量，nalive为无线传感器网络中剩余能量大于零的节点的数量，称为网络中的存活节点数。
步骤s22：选择簇首竞争系数满足
步骤s23：将步骤s22得到的分簇树中的节点和节点关联的边从当前最低能耗路径树中删除，得到更新后的最低能耗路径树，返回步骤s21。
在本发明中，如图4所示，进一步地，步骤s3具体包括以下步骤：
步骤s31：若已选簇首的数量等于或大于nalive×p且网络中仍在存在未入簇的节点，进入步骤s4；若当前最低能耗路径树仅剩基站时，进入步骤s5；否则，计算当前最低能耗路径树中非基站节点的簇首竞争系数，节点i在步骤s3中的簇首竞争系数计算公式为：
其中e(i)为节点i的当前剩余能量；e0为节点的初始能量；xm，ym为矩形无线传感器网络范围的边长；d(i,bs)表示节点i到基站的欧式距离。
步骤s32：若当前最低能耗路径树中节点的簇首竞争系数都为0，则结束第二批簇首选择，进入步骤s4；否则，选择最大簇首竞争系数对应的节点作为簇首，并将当前最低能耗路径树中以该节点为根节点的子树作为一个分簇树，并保留分簇树内的通信路径，分簇树内的节点为一个分簇。
步骤s33：将步骤s32得到的分簇树内的节点和节点关联边从当前最低能耗路径树中删除，得到更新后的最低能耗路径树，返回步骤s31。
在本发明中，如图5所示，步骤s4具体包括以下步骤：
步骤s41：计算当前最低能耗路径树中除基站外的节点的入簇竞争系数，簇首chj对节点i的入簇竞争系数计算公式为:
其中e(chj)为簇首chj的当前剩余能量；d(i,chj)为节点i到簇首chj的欧式距离；e0为节点的初始能量。
步骤s42：若最大入簇竞争系数为-∞，则此时未入簇节点按照初始最低能耗路径树中的路径与基站进行通信，进入步骤s5；否则，将最大入簇竞争系数对应的节点i加入对应的簇首j的分簇中，找到节点i与簇首j所在分簇树中最近的节点h，节点i与节点h建立直接通信路径，节点i通过节点h与簇首通信，此时，将节点i从当前最低能耗路径树中删去，最低能耗路径树被更新。
步骤s43：若当前最低能耗路径树中仅剩下基站，执行步骤s5，否则，返回步骤s41。
进一步地，步骤s5具体包括以下步骤：
步骤s51：选择初始最低能耗最低路径树中基站的子节点作为中继节点；
步骤s52：计算任意两节点间的边的权值，得到权值矩阵w，簇首chi与簇首chj间边的权值计算公式为：
簇首chi与中继节点rej间边的权值计算公式为：
中继节点rej与簇首chi间边的权值计算公式为：
中继节点rei与中继节点rej间边的权值计算公式为：
簇首chi与基站间bs边的权值计算公式为：
中继节点rei与基站bs间边的权值计算公式为：
其中，当i＝j时w(i,j)＝ ∞，上式中，load(chi),load(rei)分别为当前路由状况下簇首chi或中继节点rei可能承担的负载；
步骤s53：依据w矩阵，采用dijstra算法得到各簇首到基站的最小权值通信路由。
下面以具体实例进一步阐述本发明的技术方案：
如表1所示，表1为应用于无线传感器网络的分簇路由方法的仿真参数表，100个节点在无线传感器网络监测区域内随机分布，基站位于无线传感器网络监测区域的中心位置。
表1
节点收发m比特数据的能耗计算方式如下：
节点发送m比特数据产生能耗：
节点接收m比特数据产生能耗：
erx＝eelec×m
节点融合m比特数据产生能耗：
ea＝eda×m
初始化网络环境：100个无线传感器节点随机分均匀布在500米×500米的监测区域内，每个无线传感器节点知道自己的地理位置并具有唯一的id；基站部署在在监测区域中部，坐标为(250,250)，簇首百分比p＝0.1。
采用matlab作为仿真工具，系统仿真环境参数设置如下：
a)100个无线传感器节点随机均匀分布在500米×500米的区域内，横坐标范围(0,500)，纵坐标范围(0,500)，且所有无线传感器节点都不具备移动性。
b)基站静止，位置分别为(250,250)。
c)相关参数设置如表1所示。
d)每轮每个无线传感器节点能采集到的一个数据量为2500比特的数据包；
e)通信信道为理想状态不考虑碰撞等。
f)能耗计算按照上文所述方式.
以上参数并不恒定，对于不同的仿真内容可以根据需要改变某些参数。
为分析本发明在无线传感器网络性能上的提升，将本发明(mecpt-ca)与wendirabiner等提出的leach，jocelynediniozackogbadouissa等人提出的hgc以及wangj等人提出的ec-pso在同等仿真条件下进行仿真，得到图6-图9所示结果，对仿真结果的对比分析如下：
在上述环境下，图6为无线传感器网络运行至轮数为1000时得到的节点死亡与轮数关系示意图。可以看出，本发明下分批的簇首选择方法得到的簇首中心程度低，产生的能量浪费少，可延长网络寿命，节点入簇方法使得产生的簇规模合理，实现负载均衡，因此节点死亡时间较为集中，即网络能耗分布较为均衡，且无线传感器网络的有效工作轮数(当网络中超过60％的节点死亡时，产生大量丢包，被视为无效工作轮数)较多。
在上述环境下，图7为无线传感器网络运行至轮数为1000时得到的网络丢包率与轮数关系示意图。可以看出，在无线传感器网络处于有效工作轮数时，本发明采用的分簇与节点入簇过程考虑簇的规模与负载的均衡，因而网络丢包率小。
上述环境下，图8为无线传感器网络运行至轮数为1000时得到的网络吞吐量与轮数关系示意图。可以看出，本发明下的网络吞吐量较大。由于网络中簇间通信路由规划进一步考虑了节点的负载与能量，实现网络中节点间能量分布的均衡，使得节点寿命延长，因而网络吞吐量得到提升。
上述环境下，图9为无线传感器网络运行至轮数为1000时得到的网络剩余与轮数关系示意图。可以看出，本发明下节点与基站通信过程中低中心程度的簇首减少了实际通信距离，减少了不必要的能耗，因而在前500轮时的网络能量大于对比算法，在前300轮左右本发明下的网络能耗减少速度小于对比算法。
图10为本发明所提供的无线传感器网络的分簇路由系统结构图，如图10所示，一种无线传感器网络的分簇路由系统，包括：
初始最低能耗路径树构建模块1001，用于利用所述基站收集无线传输网络中的节点信息，并根据所述节点信息构建初始最低能耗路径树；所述节点信息包括节点位置、节点能量以及节点id。
所述初始最低能耗路径树构建模块1001，具体包括：第一权值矩阵生成单元，用于根据所述节点信息计算任意两个所述节点所建立的连接边的权值，生成连接边的第一权值矩阵；最小权值通信路由计算单元，用于根据所述连接边的第一权值矩阵计算存活节点到所述基站的最小权值通信路由；初始最低能耗路径树构建单元，用于根据所述存活节点到所述基站的最小权值通信路由，将所述存活节点的下一跳节点作为所述存活节点的父节点，构建以所述基站为根节点的初始最低能耗路径树。
一次更新后的最低能耗路径树确定模块1002，用于计算所述初始最低能耗路径树中除所述基站外的节点的第一簇首竞争系数，逐一进行第一批簇首选择和节点入簇，构建第一分簇树并更新所述初始最低能耗路径树，确定一次更新后的最低能耗路径树。
二次更新后的最低能耗路径树确定模块1003，用于计算所述一次更新后的最低能耗路径树中除所述基站外的节点的第二簇首竞争系数，逐一进行第二批簇首选择和节点入簇，构建第二分簇树并更新所述一次更新后的最低能耗路径树，确定二次更新后的最低能耗路径树。
第三入簇竞争系数确定模块1004，用于根据所述第一分簇树以及第二分簇树计算已有簇首对于所述二次更新后的最低能耗路径树中除所述基站外的节点的第三入簇竞争系数。
第一判断模块1005，用于判断所述第三入簇竞争系数是否为-∞，得到第一判断结果。
中继节点选择模块1006，用于若所述第一判断结果表示为所述第三入簇竞争系数为-∞，将未入簇的节点按照所述初始最低能耗路径树中的路径与基站进行通信，并选择所述初始最低能耗路径树中所述基站的子节点作为中继节点。
通信能耗计算模块1007，用于计算簇首以及所述中继节点之间的通信能耗。
节点与基站的通信路径确定模块1008，用于根据所述通信能耗计算簇首到所述基站的最小权值路径，将所述最小权值路径作为所述簇首与所述基站的通信路径，并根据所述所述簇首与所述基站的通信路径确定所述节点与所述基站的通信路径。
上传模块1009，用于确定所有所述节点按照所述节点与所述基站的通信路径将所述节点信息上传至所述基站。
最低能耗路径树更新模块1010，用于若所述第一判断结果表示为所述第三入簇竞争系数不为-∞，依照所述第三入簇竞争系数对所述二次更新后的最低能耗路径树内的节点进行入簇操作，每当一个所述二次更新后的最低能耗路径树内的节点完成入簇，更新所述二次更新后的最低能耗路径树内的节点加入的分簇树以及所述二次更新后的最低能耗路径树。
随着无线传感器网络的应用规模的扩大，网络中的无线传感器数量和分布范围都逐步扩大，目前的分簇路由方法对于大规模的无线传感器网络适用性不高。而本发明针对大规模无线传感器网络提出一种无线传感器网络分簇路由方法及系统，缓解了无线传感器网络能量空洞，延长网络寿命，增加网络吞吐量，降低网络丢包率。
本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的系统而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。
本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处。综上所述，本说明书内容不应理解为对本发明的限制。
1.一种无线传感器网络的分簇路由方法，其特征在于，包括：
利用所述基站收集无线传输网络中的节点信息，并根据所述节点信息构建初始最低能耗路径树；所述节点信息包括节点位置、节点能量以及节点id；
计算所述初始最低能耗路径树中除所述基站外的节点的第一簇首竞争系数，逐一进行第一批簇首选择和节点入簇，构建第一分簇树并更新所述初始最低能耗路径树，确定一次更新后的最低能耗路径树；
计算所述一次更新后的最低能耗路径树中除所述基站外的节点的第二簇首竞争系数，逐一进行第二批簇首选择和节点入簇，构建第二分簇树并更新所述一次更新后的最低能耗路径树，确定二次更新后的最低能耗路径树；
根据所述第一分簇树以及第二分簇树计算已有簇首对于所述二次更新后的最低能耗路径树中除所述基站外的节点的第三入簇竞争系数；
判断所述第三入簇竞争系数是否为-∞，得到第一判断结果；
若所述第一判断结果表示为所述第三入簇竞争系数为-∞，将未入簇的节点按照所述初始最低能耗路径树中的路径与基站进行通信，并选择所述初始最低能耗路径树中所述基站的子节点作为中继节点；
计算簇首以及所述中继节点之间的通信能耗；
根据所述通信能耗计算簇首到所述基站的最小权值路径，将所述最小权值路径作为所述簇首与所述基站的通信路径，并根据所述所述簇首与所述基站的通信路径确定所述节点与所述基站的通信路径；
确定所有所述节点按照所述节点与所述基站的通信路径将所述节点信息上传至所述基站；
若所述第一判断结果表示为所述第三入簇竞争系数不为-∞，依照所述第三入簇竞争系数对所述二次更新后的最低能耗路径树内的节点进行入簇操作，每当一个所述二次更新后的最低能耗路径树内的节点完成入簇，更新所述二次更新后的最低能耗路径树内的节点加入的分簇树以及所述二次更新后的最低能耗路径树。
2.根据权利要求1所述的无线传感器网络的分簇路由方法，其特征在于，所述利用所述基站收集无线传输网络中的节点信息，并根据所述节点信息构建初始最低能耗路径树，具体包括：
根据所述节点信息计算任意两个所述节点所建立的连接边的权值，生成连接边的第一权值矩阵；
根据所述连接边的第一权值矩阵计算存活节点到所述基站的最小权值通信路由；
根据所述存活节点到所述基站的最小权值通信路由，将所述存活节点的下一跳节点作为所述存活节点的父节点，构建以所述基站为根节点的初始最低能耗路径树。
3.根据权利要求1所述的无线传感器网络的分簇路由方法，其特征在于，所述计算所述初始最低能耗路径树中除所述基站外的节点的第一簇首竞争系数，逐一进行第一批簇首选择和节点入簇，构建第一分簇树并更新所述初始最低能耗路径树，确定一次更新后的最低能耗路径树，具体包括：
选取所述第一簇首竞争系数满足簇首竞争系数阈值范围内最大的第一簇首竞争系数对应的节点作为簇首；
以所述簇首为根节点的子树作为第一分簇树，并保留所述第一分簇树内的通信路径；
删除所述第一分簇树中的节点以及节点关联的边从所述初始最低能耗路径树中，确定一次更新后的最低能耗路径树。
4.根据权利要求3所述的无线传感器网络的分簇路由方法，其特征在于，所述删除所述第一分簇树中的节点以及节点关联的边从所述初始最低能耗路径树中，确定一次更新后的最低能耗路径树，之后还包括：
若所述最大的第一簇首竞争系数小于所述簇首竞争系数阈值范围的下限，并且已选出的簇首数量未达到簇首数量阈值，同时所述无线传感器网络内仍存在未入簇的节点，执行“计算所述一次更新后的最低能耗路径树中除所述基站外的节点的第二簇首竞争系数，逐一进行第二批簇首选择和节点入簇，构建第二分簇树并更新所述一次更新后的最低能耗路径树，确定二次更新后的最低能耗路径树”；
若已选出的簇首数量超出簇首数量阈值且无线传感器网络中仍存在未入簇的节点，执行“根据所述第一分簇树以及第二分簇树计算已有簇首对于所述二次更新后的最低能耗路径树中除所述基站外的节点的第三入簇竞争系数”；
若所述一次更新后的最低能耗路径树仅剩余所述基站时，执行“选择所述初始最低能耗路径树中所述基站的子节点作为中继节点”。
5.根据权利要求1所述的无线传感器网络的分簇路由方法，其特征在于，所述计算所述一次更新后的最低能耗路径树中除所述基站外的节点的第二簇首竞争系数，逐一进行第二批簇首选择和节点入簇，构建第二分簇树并更新所述一次更新后的最低能耗路径树，确定二次更新后的最低能耗路径树，具体包括：
判断所述第二簇首竞争系数是否均为0，得到第二判断结果；
若所述第二判断结果表示为所述第二簇首竞争系数均为0，执行“根据所述第一分簇树以及第二分簇树计算已有簇首对于所述二次更新后的最低能耗路径树中除所述基站外的节点的第三入簇竞争系数”；
若所述第二判断结果表示为所述第二簇首竞争系数不均为0，选取所述第二簇首竞争系数内最大的第二簇首竞争系数对应的节点作为簇首；
以所述簇首为根节点的子树作为第二分簇树，并保留所述第二分簇树内的通信路径；
删除所述第二分簇树中的节点以及节点关联的边从所述一次更新后的最低能耗路径树中，确定二次更新后的最低能耗路径树。
6.根据权利要求5所述的无线传感器网络的分簇路由方法，其特征在于，所述更新所述二次更新后的最低能耗路径树内的节点加入的分簇树以及所述二次更新后的最低能耗路径树，之后还包括：
获取更新后的当前最低能耗路径树；
若所述当前最低能耗路径树仅剩余所述基站时，执行“选择所述初始最低能耗路径树中所述基站的子节点作为中继节点”。
7.根据权利要求6所述的无线传感器网络的分簇路由方法，其特征在于，所述根据所述通信能耗计算簇首到所述基站的最小权值路径，将所述最小权值路径作为所述簇首与所述基站的通信路径，并根据所述所述簇首与所述基站的通信路径确定所述节点与所述基站的通信路径，具体包括：
获取所述当前最低能耗路径树对应的当前路由状态下簇首或中继节点的负载估计值；
基于所述负载估计值，计算所述所述当前最低能耗路径树中任意两个所述节点所建立的连接边的权值，生成连接边的第二权值矩阵；
根据所述连接边的第二权值矩阵计算各个所述簇首到所述基站的最小权值通信路由。
8.根据权利要求1所述的无线传感器网络的分簇路由方法，其特征在于，所述确定所有所述节点按照所述节点与所述基站的通信路径将所述节点信息上传至所述基站，之后还包括：
判断所述簇首和所述中继节点的能量是否低于将所述节点信息上传至所述基站的节点对应的能量阈值，得到第三判断结果；所述能量阈值为在上一轮节点信息传输过程中，将所述节点信息上传至所述基站的节点的剩余能量的50％；
若所述第三判断结果表示为所述簇首和所述中继节点的能量低于将所述节点信息上传至所述基站的节点对应的能量阈值，执行“利用所述基站收集无线传输网络中的节点信息，并根据所述节点信息构建初始最低能耗路径树”；
若所述第三判断结果表示为所述簇首和所述中继节点的能量未低于将所述节点信息上传至所述基站的节点对应的能量阈值，按照上一轮节点信息传输过程中的所述节点与所述基站的通信路径进行通信。
9.一种无线传感器网络的分簇路由系统，其特征在于，包括：
初始最低能耗路径树构建模块，用于利用所述基站收集无线传输网络中的节点信息，并根据所述节点信息构建初始最低能耗路径树；所述节点信息包括节点位置、节点能量以及节点id；
一次更新后的最低能耗路径树确定模块，用于计算所述初始最低能耗路径树中除所述基站外的节点的第一簇首竞争系数，逐一进行第一批簇首选择和节点入簇，构建第一分簇树并更新所述初始最低能耗路径树，确定一次更新后的最低能耗路径树；
二次更新后的最低能耗路径树确定模块，用于计算所述一次更新后的最低能耗路径树中除所述基站外的节点的第二簇首竞争系数，逐一进行第二批簇首选择和节点入簇，构建第二分簇树并更新所述一次更新后的最低能耗路径树，确定二次更新后的最低能耗路径树；
第三入簇竞争系数确定模块，用于根据所述第一分簇树以及第二分簇树计算已有簇首对于所述二次更新后的最低能耗路径树中除所述基站外的节点的第三入簇竞争系数；
第一判断模块，用于判断所述第三入簇竞争系数是否为-∞，得到第一判断结果；
中继节点选择模块，用于若所述第一判断结果表示为所述第三入簇竞争系数为-∞，将未入簇的节点按照所述初始最低能耗路径树中的路径与基站进行通信，并选择所述初始最低能耗路径树中所述基站的子节点作为中继节点；
通信能耗计算模块，用于计算簇首以及所述中继节点之间的通信能耗；
节点与基站的通信路径确定模块，用于根据所述通信能耗计算簇首到所述基站的最小权值路径，将所述最小权值路径作为所述簇首与所述基站的通信路径，并根据所述所述簇首与所述基站的通信路径确定所述节点与所述基站的通信路径；
上传模块，用于确定所有所述节点按照所述节点与所述基站的通信路径将所述节点信息上传至所述基站；
最低能耗路径树更新模块，用于若所述第一判断结果表示为所述第三入簇竞争系数不为-∞，依照所述第三入簇竞争系数对所述二次更新后的最低能耗路径树内的节点进行入簇操作，每当一个所述二次更新后的最低能耗路径树内的节点完成入簇，更新所述二次更新后的最低能耗路径树内的节点加入的分簇树以及所述二次更新后的最低能耗路径树。
10.根据权利要求9所述的无线传感器网络的分簇路由系统，其特征在于，所述初始最低能耗路径树构建模块，具体包括：
第一权值矩阵生成单元，用于根据所述节点信息计算任意两个所述节点所建立的连接边的权值，生成连接边的第一权值矩阵；
最小权值通信路由计算单元，用于根据所述连接边的第一权值矩阵计算存活节点到所述基站的最小权值通信路由；
初始最低能耗路径树构建单元，用于根据所述存活节点到所述基站的最小权值通信路由，将所述存活节点的下一跳节点作为所述存活节点的父节点，构建以所述基站为根节点的初始最低能耗路径树。
技术总结