网络拓扑分簇处理方法和处理系统的制作方法
专利名称：网络拓扑分簇处理方法和处理系统的制作方法
技术领域：
本发明实施例涉及通信领域，尤其是一种网络拓扑分簇处理方法和处理系统。
背景技术：
无线传感器网络(Wireless Sensor Network, WSN)是一种具有集信息采集、信息 处理、信息传输功能的综合智能无线通信系统，它由大量的传感器节点构成，每个节点包括 微处理器、内存、传感器、电池和微型无线电收发机等功能模块。由于传感器节点体积微小，所以只能配置更加微小的电源，所以传感器网络要尽 可能降低能量消耗率，高效利用节点能量，从而提高网络寿命。现有的无线传感器网络由一个汇聚节点和大量部署在监测区域的传感器节点构 成，通过无线通信方式形成一个多跳的自组织网络。传感器节点感知、采集和处理监测区域 中感知对象的信息，监测的数据沿着其他传感器节点逐跳传输到达汇聚节点。分簇拓扑型的无线传感器网络，将整个网络划分为多个区域，每个区域称为一个 簇，依据一定分簇处理方法选择某个节点作为簇头，簇头收集簇内节点的数据并进行融合。现有的分簇处理方法是一种利用自适应分簇拓扑Leach算法的处理方法进行周 期性的处理，每次循环重新成为簇头，通过产生随机数的方式来选择簇头，节点产生一个 0 1的随机数，如果这个数小于阈值T(n)，则发布自己成为簇头的公告消息。如果节点已 经当选过簇头则把T(n)设置为0，这样该节点不会再次当选簇头。在后续的循环中，需要周 期性地在没有当选过簇头的节点中重新选择簇头，重新成为簇头。现有的分簇处理方法需要频繁轮换簇头，重新成为簇头，因此处理一段时间后需 要占用的时间很多，而且消耗能量也很多。
发明内容
本发明实施例提供了一种网络拓扑分簇处理方法和处理系统，以实现网络拓扑分 簇处理，并且占用时间少，消耗能量少。本发明实施例提供了一种网络拓扑分簇处理方法，用于多节点网络中，所述多节 点网络包括多个节点，所述网络拓扑分簇方法包括所述多个节点分别向各自的邻居节点发送第一广播信息；所述多个节点在收到其他节点发送的所述第一广播信息后，返回一个第一广播信 息的应答信息；所述多个节点在收到其他节点发送的所述第一广播信息的应答信息后，分别根据 各自所接收的所述应答信息的数量统计各自的节点度；所述多个节点中的剩余能量大于第一阈值的节点，向其邻居节点发送包含其自身 的节点度的第二广播信息；所述多个节点分别接收其他节点发送来的第二广播信息，并将其自身的节点度和 其他节点的节点度进行比较，如果所述多个节点中的一个确认其自身的节点度大于其他所有节点的节点度，则所述节点度最大的节点发布成为簇头的公告信息。本发明实施例还提供了一种网络拓扑分簇处理方法，包括向其他节点发送第一广播信息；根据接收到的所述第一广播消息的应答消息，统计节点度；接收其它节点发送的第二广播信息，所述第二广播信息中包含其他节点的节点度 fn息；根据接收到的其他节点的第二广播消息，比较其他第二广播消息的节点度和自身 的节点度，如果自身的节点度最大则发布成为簇头的公告信息。本发明实施例还提供了一种网络拓扑分簇处理系统，包括发送模块，用于向其他节点发送第一广播信息；统计模块，用于根据接收到的所述第一广播消息的应答消息，统计节点度；接收模块，用于接收其它节点发送的第二广播信息，所述第二广播信息中包含其 他节点的节点度信息；比较模块，用于根据接收到的其他节点的第二广播消息，比较其他第二广播消息 的节点度和自身的节点度，如果自身的节点度最大则发布成为簇头的公告信息。所以本发明实施例网络拓扑分簇处理方法和处理系统，根据节点的剩余能量和节 点的节点度来选择节点作为簇头节点，而不必使用复杂的簇头节点选择算法来进行簇头节 点的选择，因此占用时间少，消耗能量少。
图1为本发明网络拓扑分簇处理方法实施例一的流程图；图2为本发明网络拓扑分簇处理方法实施例二的流程图；图3为本发明网络拓扑分簇处理方法实施例的示意图。
具体实施例方式下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。分簇拓扑型的无线传感器网络，将整个网络划分为多个区域，每个区域称为一个 簇，依据一定的网络拓扑分簇处理方法选择某个节点作为簇头节点，簇头节点收集簇内节 点的数据并进行融合。如图1所示，为本发明网络拓扑分簇处理方法实施例一的流程图，本实施例的网 络拓扑分簇方法用于多节点网络中，而多节点网络包括多个节点，本实施例的网络拓扑分 簇方法包括如下步骤步骤101，多个节点分别向各自的邻居节点发送第一广播信息；可以是多个节点以统一的发射功率分别向各自的邻居节点发送一个包含自己ID
的第一广播信息；步骤102，多个节点在收到其他节点发送的第一广播信息后，返回一个第一广播信息的应答信息；步骤103，多个节点在收到其他节点发送的第一广播信息的应答信息后，分别根据各自所接收的应答信息的数量统计各自的节点度(node degree, ND)；
节点度用于表示一个节点可直接通信的节点的个数；步骤104，多个节点中的剩余能量大于第一阈值的节点，向其邻居节点发送包含其 自身的节点度的第二广播信息；当然，在一定情况下，也可以不考虑剩余能量，而是所有节点均向邻居节点发送包 含其自身节点度的第二广播信息。步骤105，多个节点分别接收其他节点发送来的第二广播信息，并将其自身的节点 度和其他节点的节点度进行比较，如果多个节点中的一个确认其自身的节点度大于其他所 有节点的节点度，则节点度最大的节点发布成为簇头的公告信息。在步骤105中，多个节点将自身的节点度和其他节点的节点度进行比较后，如果 所述多个节点中的节点发现自身的节点度不是最大则记录邻居节点中节点度最大的节点， 并等待该节点发布成为簇头的公告信息；而多个节点中的节点如果接收到邻居节点中节点 度最大的节点发送的其他节点成为簇头的应答信息，则重新比较未发送应答信息的邻居节 点的节点度和自身的节点度；如果自身节点度最大则发布成为簇头的公告消息；如果自身 节点度不是最大则记录该节点度最大的节点，并等待该节点度最大的节点发布成为簇头的 公告消息。并且如果多个节点中的一个确认自身的节点度和其他节点度同为最大，如果没有 接收到其他成为簇头的公告信息，则所述节点度最大的节点发布成为簇头的公告信息。所以本发明网络拓扑分簇处理方法实施例一，根据节点的剩余能量和节点的节点 度来选择节点作为簇头节点，而不必使用复杂的簇头节点选择算法来进行簇头节点的选 择，因此占用时间少，消耗能量少。如图2所示，为本发明网络拓扑分簇处理方法实施例二的流程图，具体包括如下 步骤步骤201，向其他节点发送第一广播消息；具体的是可以设置一个适当的全网节点统一的发射功率，全网的节点以统一的发 射功率向周围节点发送一个包含自己ID的第一广播信息Msgl(IDl)；所述第一广播信息中包含发送节点的ID信息，用于其他接收到该第一广播信息 的节点得知是哪一个节点发送的该第一广播消息；步骤202，每一个节点接收到其他节点发送的第一广播信息Msgl(IDl)后返回一 个携带自己ID的第一广播信息应答信息Ackl (ID1,ID2)；节点根据接收到的其他节点发出 的第一广播消息的应答消息Ackl(IDl，ID2)，统计自身的节点度；所述第一广播信息应答信息包含发送该第一广播信息的节点的ID信息，以及发 送该第一广播信息应答信息节点的ID信息，用于在发送该第一广播消息的节点接收到该 第一广播消息的应答消息之后，根据该发送第一个广播消息应答信息节点的ID信息的唯 一性统计节点度；每一个节点根据接收到的第一广播消息的应答消息Ackl (ID1，ID2)，因为每一个 节点的ID是唯一的，因此可以根据该应答消息统计处节点度，也就是接收到的应答消息中 ID2的个数，由此可以确定邻居节点；步骤203，如果节点的剩余能量(Power Available, PA)大于第一阈值，则广播包 含自己节点度的第二广播消息Msg2 (ID1，ND1)；
所述第二广播消息包含发送该第二广播消息的节点的ID信息和节点度；当然如果节点的剩余能量小于设置的第一阈值则不广播第二广播消息；步骤204，接收其它节点发送的第二广播信息，PA大于第一阈值的每个节点根据 接收到的其他节点发送的第二广播消息Msg2(IDl，ND1)，比较其他节点发送的第二广播消 息中的其他节点的节点度和其自身的节点度，如果自身的节点度最大则发布一个成为簇头 的公告信息Msg3(IDl)给周围节点；如果判断出自己的节点度不是最大，则记录邻居节点中节点度最大的节点的ID， 并等待该节点发布成为簇头的公告信息；有一种情况是节点判断出自身的节点度和其他节点的节点度同为最大，按照发送 簇头的公告信息Msg3的时间顺序来选择，即如果没有接收到其他的成为簇头的公告信息， 则该节点发送成为簇头的公告信息Msg3，也就是该节点是第一发送成为簇头的公告信息 Msg3,而其他同样是最大节点度的其他节点不是第一发送成为簇头的公告信息Msg3，当然 会收到第一发送的成为簇头的公告信息Msg3，而该节点不会再发送成为簇头的公告信息， 虽然该节点也是最大节点度的节点。步骤205，接收到成为簇头公告信息Msg3的节点向其他节点发送公告信息Msg3的 应答信息 Ack3(IDl，ID2)；所述应答信息Ack3中包含发送公告信息Msg3的节点的ID信息，和发送该应答信 息Ack3的节点的ID信息，用于该发送公告信息Msg3的节点接收该应答信息Ack3，并得知 是发送给自身的应答信息Ack3 ；步骤206，PA大于第一阈值的节点如果接收到邻居节点中节点度最大的节点发送 的其他节点成为簇头的应答信息ACK3，则重新比较未发送应答信息的邻居节点的节点度和 自身的节点度；如果自身节点度最大则发布成为簇头的公告消息；如果自身节点度不是最 大则记录该节点度最大的节点，并等待该节点度最大的节点发布成为簇头的公告消息；已 经接收过成为簇头的公告信息并发送应答消息的节点不作响应，否则返回公告信息的应答 消息；步骤204中记载了如果节点一判断出自己的节点度不是最大，则记录邻居节点中 节点度最大的节点二的ID，当然会等待该节点二发布成为簇头的公告消息，但是如果节点 二判断自己的节点大并非是最大(因为每个节点的邻节点是不同的，收到的节点度广播也 不同)，所以会接收到节点度最大的节点三发送的成为簇头的公告消息，并向节点三和节 点一返回成为簇头消息的应答消息；此时节点一重新比较未发送应答信息的邻居节点的节 点度和自身的节点度；如果自身节点度最大则发布成为簇头的公告消息；如果自身节点度 不是最大则记录该节点度最大的节点，并等待该节点度最大的节点发布成为簇头的公告消 息；步骤207，重复步骤206直到所有的节点都成簇。如图3所示，为本发明网络拓扑分簇处理方法实施例的示意图，图中，节点A的ND 为9，节点B的ND为7，节点C的ND为6，节点B为节点A的邻节点，可以互相通信；节点B 是节点C的邻节点，可以互相通信，但是节点C和节点A不能通信。假设节点A、B和C的PA均大于第一阈值，所以在统计完毕自己的节点度后都需要 广播包含自己节点度的第二广播消息。节点A、B和C接收到这些第二广播消息后，节点A发现自身的节点度最大，所以发送成为簇头的公告信息。节点B发现节点A的ND比自身的大，因此不发送成为簇头的公告信息，而且会接 收到节点A发送的成为簇头的公告信息，然后返回一个成为簇头的公告信息的应答消息， 这个应答消息里面具有簇头A的ID，这个应答消息会被节点A和节点C接收到，节点A成为 簇头节点，而节点B成为簇头节点A所成为簇头的节点；节点C因为发现节点B的ND大于自己的ND，所以节点C也不会发送成为簇头的公 告信息，而且节点C无法接收节点A发送的成为簇头的公告信息，等待B发送成为簇头的公 告信息，但是节点C却收到节点B发送的成为簇头的公告信息的应答消息，该应答消息里面 具有节点A的ID，此时节点C得知节点C成为簇头节点，节点B成为簇头节点A下的节点， 此时节点C会再次比较自身节点度和未发送应答消息的其他节点的节点度的大小，如果自 身的节点度最大则发布成为簇头的公告信息；已经接收过成为簇头公告信息并发送应答消 息的节点(即已经成为其他簇头节点下的节点，例如节点B)不作响应，否则返回公告信息 的应答消息；如此往复，直到所有的节点都成簇。当簇头节点的剩余能量低于第一阈值的时候，则重新开始上述步骤的网络拓扑分 簇处理。如果簇内节点有数据需要发送给汇聚节点时，则簇内节点主动将数据发送给簇头 节点，簇头节点将簇内节点的数据打包后经过一定路由发送给汇聚节点。而簇头节点与簇头节点之间可以直接通信，帮助转发数据包，也可以通过某个交 叠的地理位置上的节点进行通信和数据转发。所以本发明网络拓扑分簇处理方法实施例二，根据节点的剩余能量和节点的节点 度来选择节点作为簇头节点，所以不需要使用复杂的算法来进行簇头选择，所以簇头节点 选择的占用时间少。并且簇头节点收集簇内节点的数据并进行融合，减少了数据通信量 ’大 部分簇内节点可以在没有数据业务时处于休眠状态，节省了能量，可以大大地延长整个网 络的寿命。本发明网络拓扑分簇处理系统实施例一，用于多节点网络中，多节点网络包括多 个节点，网络拓扑分簇处理系统实施例一具体包括第一发送模块，用于多个节点分别向各自的邻居节点发送第一广播信息；返回模块，用于多个节点在收到其他节点发送的第一广播信息后，返回一个第一 广播信息的应答信息；统计模块，用于多个节点在收到其他节点发送的第一广播信息的应答信息后，分 别根据各自所接收的应答信息的数量统计各自的节点度；第二发送模块，用于多个节点中的剩余能量大于第一阈值的节点，向其邻居节点 发送包含其自身的节点度的第二广播信息；比较模块，用于多个节点分别接收其他节点发送来的第二广播信息，并将其自身 的节点度和其他节点的节点度进行比较，如果多个节点中的一个确认其自身的节点度大于 其他所有节点的节点度，则节点度最大的节点发布成为簇头的公告信息。所以本发明网络拓扑分簇处理系统实施例一，根据节点的剩余能量和节点的节点 度来选择节点作为簇头节点，而不必使用复杂的簇头节点选择算法来进行簇头节点的选 择，因此占用时间少。
本发明网络拓扑分簇处理系统实施例二具体包括发送模块，用于向其他节点发送第一广播信息；统计模块，用于根据接收到的第一广播消息的应答消息，统计节点度；接收模块，用于接收其它节点发送的第二广播信息，第二广播信息中包含其他节 点的节点度信息；比较模块，用于当自身的剩余能量大于第一阈值时，根据接收到的其他节点的第 二广播消息，比较其他第二广播消息的节点度和自身的节点度，如果自身的节点度最大则 发布成为簇头的公告信息。第一广播信息中包括发送节点的ID。需要注意的是，仅当节点的剩余能量大于第 一阈值的情况，节点发布第二广播信息，而当节点的剩余能量不足第一阈值的时候，节点不 会发布成为簇头的公告信息。所以本发明网络拓扑分簇处理系统实施例二，根据节点的剩余能量和节点的节点 度来选择节点作为簇头节点，而不需要使用复杂的算法，因此簇头节点选择的占用时间少。 并且簇头节点收集簇内节点的数据并进行融合，减少了数据通信量；大部分簇内节点可以 在没有数据业务时处于休眠状态，节省了能量，可以大大地延长整个网络的寿命。最后所应说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参 照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明 的技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围。
9
权利要求
一种网络拓扑分簇处理方法，用于多节点网络中，所述多节点网络包括多个节点，其特征在于，所述网络拓扑分簇处理方法包括所述多个节点分别向各自的邻居节点发送第一广播信息；所述多个节点在收到其他节点发送的第一广播信息后，返回第一广播信息的应答信息；所述多个节点在收到其他节点发送的第一广播信息的应答信息后，分别根据各自所接收的所述应答信息的数量统计各自的节点度；所述多个节点中的剩余能量大于第一阈值的节点，向其邻居节点发送包含其自身的节点度的第二广播信息；所述多个节点分别接收其他节点发送来的第二广播信息，并将其自身的节点度和其他节点的节点度进行比较，如果所述多个节点中的一个确认其自身的节点度大于其他所有节点的节点度，则所述节点度最大的节点发布成为簇头的公告信息。
2.根据权利要求1所述的网络拓扑分簇处理方法，其特征在于所述多个节点分别向各 自的邻居节点发送第一广播信息包括所述多个节点向各自的邻居节点发送一个包含自己 ID的第一广播信息。
3. —种网络拓扑分簇处理方法，其特征在于包括 向其他节点发送第一广播消息；根据接收到的所述第一广播消息的应答消息，统计节点度；接收其它节点发送的第二广播消息，所述第二广播消息中包含其他节点的节点度信息；当自身的剩余能量大于第一阈值时，根据接收到的其他节点的第二广播消息，比较其 他第二广播消息的节点度和自身的节点度，如果自身的节点度最大则发布成为簇头的公告 fn息o
4.根据权利要求3所述的网络拓扑分簇处理方法，其特征在于所述向其他节点发送第 一广播消息包括向其他节点发送包含自身I D的第一广播信息。
5.根据权利要求3所述的网络拓扑分簇处理方法，其特征在于所述如果自身的节点度 最大则发布成为簇头的公告信息包括当自身的节点度和其他节点的节点度同为最大时， 如果没有接收到其他成为簇头的公告信息则发送成为簇头的公告信息。
6.根据权利要求3所述的网络拓扑分簇处理方法，其特征在于所述比较其他第二广播 消息的节点度和自身的节点度后还包括，如果自身的节点度不是最大则记录邻居节点中节 点度最大的节点，并等待该节点发布成为簇头的公告信息。
7. —种网络拓扑分簇处理系统，其特征在于，包括 发送模块，用于向其他节点发送第一广播信息；统计模块，用于根据接收到的所述第一广播消息的应答消息，统计节点度； 接收模块，用于接收其它节点发送的第二广播信息，所述第二广播信息中包含其他节 点的节点度信息；比较模块，用于当自身的剩余能量大于第一阈值时，根据接收到的其他节点的第二广 播消息，比较其他第二广播消息的节点度和自身的节点度，如果自身的节点度最大则发布 成为簇头的公告信息。
8.根据权利要求7所述的网络拓扑分簇处理系统，其特征在于，所述第一广播信息中 包括发送节点的ID。
全文摘要
本发明实施例涉及网络拓扑分簇处理方法和处理系统，网络拓扑分簇处理方法具体包括向其他节点发送第一广播信息；根据接收到的所述第一广播消息的应答消息，统计节点度；接收其它节点发送的第二广播信息，所述第二广播信息中包含其他节点的节点度信息；根据接收到的其他节点的第二广播消息，比较其他第二广播消息的节点度和自身的节点度，如果自身的节点度最大则发布成为簇头的公告信息。所以本发明实施例网络拓扑分簇处理方法和处理系统，根据节点的剩余能量和节点的节点度来选择节点作为簇头节点，而不必使用复杂的簇头节点选择算法来进行簇头节点的选择，因此占用时间少，消耗能量少。
文档编号H04W84/18GK101801113SQ200910005310
公开日2010年8月11日 申请日期2009年2月5日 优先权日2009年2月5日
发明者张兴炜 申请人:华为技术有限公司
技术领域：
本发明实施例涉及通信领域，尤其是一种网络拓扑分簇处理方法和处理系统。
背景技术：
无线传感器网络(Wireless Sensor Network, WSN)是一种具有集信息采集、信息 处理、信息传输功能的综合智能无线通信系统，它由大量的传感器节点构成，每个节点包括 微处理器、内存、传感器、电池和微型无线电收发机等功能模块。由于传感器节点体积微小，所以只能配置更加微小的电源，所以传感器网络要尽 可能降低能量消耗率，高效利用节点能量，从而提高网络寿命。现有的无线传感器网络由一个汇聚节点和大量部署在监测区域的传感器节点构 成，通过无线通信方式形成一个多跳的自组织网络。传感器节点感知、采集和处理监测区域 中感知对象的信息，监测的数据沿着其他传感器节点逐跳传输到达汇聚节点。分簇拓扑型的无线传感器网络，将整个网络划分为多个区域，每个区域称为一个 簇，依据一定分簇处理方法选择某个节点作为簇头，簇头收集簇内节点的数据并进行融合。现有的分簇处理方法是一种利用自适应分簇拓扑Leach算法的处理方法进行周 期性的处理，每次循环重新成为簇头，通过产生随机数的方式来选择簇头，节点产生一个 0 1的随机数，如果这个数小于阈值T(n)，则发布自己成为簇头的公告消息。如果节点已 经当选过簇头则把T(n)设置为0，这样该节点不会再次当选簇头。在后续的循环中，需要周 期性地在没有当选过簇头的节点中重新选择簇头，重新成为簇头。现有的分簇处理方法需要频繁轮换簇头，重新成为簇头，因此处理一段时间后需 要占用的时间很多，而且消耗能量也很多。
发明内容
本发明实施例提供了一种网络拓扑分簇处理方法和处理系统，以实现网络拓扑分 簇处理，并且占用时间少，消耗能量少。本发明实施例提供了一种网络拓扑分簇处理方法，用于多节点网络中，所述多节 点网络包括多个节点，所述网络拓扑分簇方法包括所述多个节点分别向各自的邻居节点发送第一广播信息；所述多个节点在收到其他节点发送的所述第一广播信息后，返回一个第一广播信 息的应答信息；所述多个节点在收到其他节点发送的所述第一广播信息的应答信息后，分别根据 各自所接收的所述应答信息的数量统计各自的节点度；所述多个节点中的剩余能量大于第一阈值的节点，向其邻居节点发送包含其自身 的节点度的第二广播信息；所述多个节点分别接收其他节点发送来的第二广播信息，并将其自身的节点度和 其他节点的节点度进行比较，如果所述多个节点中的一个确认其自身的节点度大于其他所有节点的节点度，则所述节点度最大的节点发布成为簇头的公告信息。本发明实施例还提供了一种网络拓扑分簇处理方法，包括向其他节点发送第一广播信息；根据接收到的所述第一广播消息的应答消息，统计节点度；接收其它节点发送的第二广播信息，所述第二广播信息中包含其他节点的节点度 fn息；根据接收到的其他节点的第二广播消息，比较其他第二广播消息的节点度和自身 的节点度，如果自身的节点度最大则发布成为簇头的公告信息。本发明实施例还提供了一种网络拓扑分簇处理系统，包括发送模块，用于向其他节点发送第一广播信息；统计模块，用于根据接收到的所述第一广播消息的应答消息，统计节点度；接收模块，用于接收其它节点发送的第二广播信息，所述第二广播信息中包含其 他节点的节点度信息；比较模块，用于根据接收到的其他节点的第二广播消息，比较其他第二广播消息 的节点度和自身的节点度，如果自身的节点度最大则发布成为簇头的公告信息。所以本发明实施例网络拓扑分簇处理方法和处理系统，根据节点的剩余能量和节 点的节点度来选择节点作为簇头节点，而不必使用复杂的簇头节点选择算法来进行簇头节 点的选择，因此占用时间少，消耗能量少。
图1为本发明网络拓扑分簇处理方法实施例一的流程图；图2为本发明网络拓扑分簇处理方法实施例二的流程图；图3为本发明网络拓扑分簇处理方法实施例的示意图。
具体实施例方式下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。分簇拓扑型的无线传感器网络，将整个网络划分为多个区域，每个区域称为一个 簇，依据一定的网络拓扑分簇处理方法选择某个节点作为簇头节点，簇头节点收集簇内节 点的数据并进行融合。如图1所示，为本发明网络拓扑分簇处理方法实施例一的流程图，本实施例的网 络拓扑分簇方法用于多节点网络中，而多节点网络包括多个节点，本实施例的网络拓扑分 簇方法包括如下步骤步骤101，多个节点分别向各自的邻居节点发送第一广播信息；可以是多个节点以统一的发射功率分别向各自的邻居节点发送一个包含自己ID
的第一广播信息；步骤102，多个节点在收到其他节点发送的第一广播信息后，返回一个第一广播信息的应答信息；步骤103，多个节点在收到其他节点发送的第一广播信息的应答信息后，分别根据各自所接收的应答信息的数量统计各自的节点度(node degree, ND)；
节点度用于表示一个节点可直接通信的节点的个数；步骤104，多个节点中的剩余能量大于第一阈值的节点，向其邻居节点发送包含其 自身的节点度的第二广播信息；当然，在一定情况下，也可以不考虑剩余能量，而是所有节点均向邻居节点发送包 含其自身节点度的第二广播信息。步骤105，多个节点分别接收其他节点发送来的第二广播信息，并将其自身的节点 度和其他节点的节点度进行比较，如果多个节点中的一个确认其自身的节点度大于其他所 有节点的节点度，则节点度最大的节点发布成为簇头的公告信息。在步骤105中，多个节点将自身的节点度和其他节点的节点度进行比较后，如果 所述多个节点中的节点发现自身的节点度不是最大则记录邻居节点中节点度最大的节点， 并等待该节点发布成为簇头的公告信息；而多个节点中的节点如果接收到邻居节点中节点 度最大的节点发送的其他节点成为簇头的应答信息，则重新比较未发送应答信息的邻居节 点的节点度和自身的节点度；如果自身节点度最大则发布成为簇头的公告消息；如果自身 节点度不是最大则记录该节点度最大的节点，并等待该节点度最大的节点发布成为簇头的 公告消息。并且如果多个节点中的一个确认自身的节点度和其他节点度同为最大，如果没有 接收到其他成为簇头的公告信息，则所述节点度最大的节点发布成为簇头的公告信息。所以本发明网络拓扑分簇处理方法实施例一，根据节点的剩余能量和节点的节点 度来选择节点作为簇头节点，而不必使用复杂的簇头节点选择算法来进行簇头节点的选 择，因此占用时间少，消耗能量少。如图2所示，为本发明网络拓扑分簇处理方法实施例二的流程图，具体包括如下 步骤步骤201，向其他节点发送第一广播消息；具体的是可以设置一个适当的全网节点统一的发射功率，全网的节点以统一的发 射功率向周围节点发送一个包含自己ID的第一广播信息Msgl(IDl)；所述第一广播信息中包含发送节点的ID信息，用于其他接收到该第一广播信息 的节点得知是哪一个节点发送的该第一广播消息；步骤202，每一个节点接收到其他节点发送的第一广播信息Msgl(IDl)后返回一 个携带自己ID的第一广播信息应答信息Ackl (ID1,ID2)；节点根据接收到的其他节点发出 的第一广播消息的应答消息Ackl(IDl，ID2)，统计自身的节点度；所述第一广播信息应答信息包含发送该第一广播信息的节点的ID信息，以及发 送该第一广播信息应答信息节点的ID信息，用于在发送该第一广播消息的节点接收到该 第一广播消息的应答消息之后，根据该发送第一个广播消息应答信息节点的ID信息的唯 一性统计节点度；每一个节点根据接收到的第一广播消息的应答消息Ackl (ID1，ID2)，因为每一个 节点的ID是唯一的，因此可以根据该应答消息统计处节点度，也就是接收到的应答消息中 ID2的个数，由此可以确定邻居节点；步骤203，如果节点的剩余能量(Power Available, PA)大于第一阈值，则广播包 含自己节点度的第二广播消息Msg2 (ID1，ND1)；
所述第二广播消息包含发送该第二广播消息的节点的ID信息和节点度；当然如果节点的剩余能量小于设置的第一阈值则不广播第二广播消息；步骤204，接收其它节点发送的第二广播信息，PA大于第一阈值的每个节点根据 接收到的其他节点发送的第二广播消息Msg2(IDl，ND1)，比较其他节点发送的第二广播消 息中的其他节点的节点度和其自身的节点度，如果自身的节点度最大则发布一个成为簇头 的公告信息Msg3(IDl)给周围节点；如果判断出自己的节点度不是最大，则记录邻居节点中节点度最大的节点的ID， 并等待该节点发布成为簇头的公告信息；有一种情况是节点判断出自身的节点度和其他节点的节点度同为最大，按照发送 簇头的公告信息Msg3的时间顺序来选择，即如果没有接收到其他的成为簇头的公告信息， 则该节点发送成为簇头的公告信息Msg3，也就是该节点是第一发送成为簇头的公告信息 Msg3,而其他同样是最大节点度的其他节点不是第一发送成为簇头的公告信息Msg3，当然 会收到第一发送的成为簇头的公告信息Msg3，而该节点不会再发送成为簇头的公告信息， 虽然该节点也是最大节点度的节点。步骤205，接收到成为簇头公告信息Msg3的节点向其他节点发送公告信息Msg3的 应答信息 Ack3(IDl，ID2)；所述应答信息Ack3中包含发送公告信息Msg3的节点的ID信息，和发送该应答信 息Ack3的节点的ID信息，用于该发送公告信息Msg3的节点接收该应答信息Ack3，并得知 是发送给自身的应答信息Ack3 ；步骤206，PA大于第一阈值的节点如果接收到邻居节点中节点度最大的节点发送 的其他节点成为簇头的应答信息ACK3，则重新比较未发送应答信息的邻居节点的节点度和 自身的节点度；如果自身节点度最大则发布成为簇头的公告消息；如果自身节点度不是最 大则记录该节点度最大的节点，并等待该节点度最大的节点发布成为簇头的公告消息；已 经接收过成为簇头的公告信息并发送应答消息的节点不作响应，否则返回公告信息的应答 消息；步骤204中记载了如果节点一判断出自己的节点度不是最大，则记录邻居节点中 节点度最大的节点二的ID，当然会等待该节点二发布成为簇头的公告消息，但是如果节点 二判断自己的节点大并非是最大(因为每个节点的邻节点是不同的，收到的节点度广播也 不同)，所以会接收到节点度最大的节点三发送的成为簇头的公告消息，并向节点三和节 点一返回成为簇头消息的应答消息；此时节点一重新比较未发送应答信息的邻居节点的节 点度和自身的节点度；如果自身节点度最大则发布成为簇头的公告消息；如果自身节点度 不是最大则记录该节点度最大的节点，并等待该节点度最大的节点发布成为簇头的公告消 息；步骤207，重复步骤206直到所有的节点都成簇。如图3所示，为本发明网络拓扑分簇处理方法实施例的示意图，图中，节点A的ND 为9，节点B的ND为7，节点C的ND为6，节点B为节点A的邻节点，可以互相通信；节点B 是节点C的邻节点，可以互相通信，但是节点C和节点A不能通信。假设节点A、B和C的PA均大于第一阈值，所以在统计完毕自己的节点度后都需要 广播包含自己节点度的第二广播消息。节点A、B和C接收到这些第二广播消息后，节点A发现自身的节点度最大，所以发送成为簇头的公告信息。节点B发现节点A的ND比自身的大，因此不发送成为簇头的公告信息，而且会接 收到节点A发送的成为簇头的公告信息，然后返回一个成为簇头的公告信息的应答消息， 这个应答消息里面具有簇头A的ID，这个应答消息会被节点A和节点C接收到，节点A成为 簇头节点，而节点B成为簇头节点A所成为簇头的节点；节点C因为发现节点B的ND大于自己的ND，所以节点C也不会发送成为簇头的公 告信息，而且节点C无法接收节点A发送的成为簇头的公告信息，等待B发送成为簇头的公 告信息，但是节点C却收到节点B发送的成为簇头的公告信息的应答消息，该应答消息里面 具有节点A的ID，此时节点C得知节点C成为簇头节点，节点B成为簇头节点A下的节点， 此时节点C会再次比较自身节点度和未发送应答消息的其他节点的节点度的大小，如果自 身的节点度最大则发布成为簇头的公告信息；已经接收过成为簇头公告信息并发送应答消 息的节点(即已经成为其他簇头节点下的节点，例如节点B)不作响应，否则返回公告信息 的应答消息；如此往复，直到所有的节点都成簇。当簇头节点的剩余能量低于第一阈值的时候，则重新开始上述步骤的网络拓扑分 簇处理。如果簇内节点有数据需要发送给汇聚节点时，则簇内节点主动将数据发送给簇头 节点，簇头节点将簇内节点的数据打包后经过一定路由发送给汇聚节点。而簇头节点与簇头节点之间可以直接通信，帮助转发数据包，也可以通过某个交 叠的地理位置上的节点进行通信和数据转发。所以本发明网络拓扑分簇处理方法实施例二，根据节点的剩余能量和节点的节点 度来选择节点作为簇头节点，所以不需要使用复杂的算法来进行簇头选择，所以簇头节点 选择的占用时间少。并且簇头节点收集簇内节点的数据并进行融合，减少了数据通信量 ’大 部分簇内节点可以在没有数据业务时处于休眠状态，节省了能量，可以大大地延长整个网 络的寿命。本发明网络拓扑分簇处理系统实施例一，用于多节点网络中，多节点网络包括多 个节点，网络拓扑分簇处理系统实施例一具体包括第一发送模块，用于多个节点分别向各自的邻居节点发送第一广播信息；返回模块，用于多个节点在收到其他节点发送的第一广播信息后，返回一个第一 广播信息的应答信息；统计模块，用于多个节点在收到其他节点发送的第一广播信息的应答信息后，分 别根据各自所接收的应答信息的数量统计各自的节点度；第二发送模块，用于多个节点中的剩余能量大于第一阈值的节点，向其邻居节点 发送包含其自身的节点度的第二广播信息；比较模块，用于多个节点分别接收其他节点发送来的第二广播信息，并将其自身 的节点度和其他节点的节点度进行比较，如果多个节点中的一个确认其自身的节点度大于 其他所有节点的节点度，则节点度最大的节点发布成为簇头的公告信息。所以本发明网络拓扑分簇处理系统实施例一，根据节点的剩余能量和节点的节点 度来选择节点作为簇头节点，而不必使用复杂的簇头节点选择算法来进行簇头节点的选 择，因此占用时间少。
本发明网络拓扑分簇处理系统实施例二具体包括发送模块，用于向其他节点发送第一广播信息；统计模块，用于根据接收到的第一广播消息的应答消息，统计节点度；接收模块，用于接收其它节点发送的第二广播信息，第二广播信息中包含其他节 点的节点度信息；比较模块，用于当自身的剩余能量大于第一阈值时，根据接收到的其他节点的第 二广播消息，比较其他第二广播消息的节点度和自身的节点度，如果自身的节点度最大则 发布成为簇头的公告信息。第一广播信息中包括发送节点的ID。需要注意的是，仅当节点的剩余能量大于第 一阈值的情况，节点发布第二广播信息，而当节点的剩余能量不足第一阈值的时候，节点不 会发布成为簇头的公告信息。所以本发明网络拓扑分簇处理系统实施例二，根据节点的剩余能量和节点的节点 度来选择节点作为簇头节点，而不需要使用复杂的算法，因此簇头节点选择的占用时间少。 并且簇头节点收集簇内节点的数据并进行融合，减少了数据通信量；大部分簇内节点可以 在没有数据业务时处于休眠状态，节省了能量，可以大大地延长整个网络的寿命。最后所应说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参 照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明 的技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围。
9
权利要求
一种网络拓扑分簇处理方法，用于多节点网络中，所述多节点网络包括多个节点，其特征在于，所述网络拓扑分簇处理方法包括所述多个节点分别向各自的邻居节点发送第一广播信息；所述多个节点在收到其他节点发送的第一广播信息后，返回第一广播信息的应答信息；所述多个节点在收到其他节点发送的第一广播信息的应答信息后，分别根据各自所接收的所述应答信息的数量统计各自的节点度；所述多个节点中的剩余能量大于第一阈值的节点，向其邻居节点发送包含其自身的节点度的第二广播信息；所述多个节点分别接收其他节点发送来的第二广播信息，并将其自身的节点度和其他节点的节点度进行比较，如果所述多个节点中的一个确认其自身的节点度大于其他所有节点的节点度，则所述节点度最大的节点发布成为簇头的公告信息。
2.根据权利要求1所述的网络拓扑分簇处理方法，其特征在于所述多个节点分别向各 自的邻居节点发送第一广播信息包括所述多个节点向各自的邻居节点发送一个包含自己 ID的第一广播信息。
3. —种网络拓扑分簇处理方法，其特征在于包括 向其他节点发送第一广播消息；根据接收到的所述第一广播消息的应答消息，统计节点度；接收其它节点发送的第二广播消息，所述第二广播消息中包含其他节点的节点度信息；当自身的剩余能量大于第一阈值时，根据接收到的其他节点的第二广播消息，比较其 他第二广播消息的节点度和自身的节点度，如果自身的节点度最大则发布成为簇头的公告 fn息o
4.根据权利要求3所述的网络拓扑分簇处理方法，其特征在于所述向其他节点发送第 一广播消息包括向其他节点发送包含自身I D的第一广播信息。
5.根据权利要求3所述的网络拓扑分簇处理方法，其特征在于所述如果自身的节点度 最大则发布成为簇头的公告信息包括当自身的节点度和其他节点的节点度同为最大时， 如果没有接收到其他成为簇头的公告信息则发送成为簇头的公告信息。
6.根据权利要求3所述的网络拓扑分簇处理方法，其特征在于所述比较其他第二广播 消息的节点度和自身的节点度后还包括，如果自身的节点度不是最大则记录邻居节点中节 点度最大的节点，并等待该节点发布成为簇头的公告信息。
7. —种网络拓扑分簇处理系统，其特征在于，包括 发送模块，用于向其他节点发送第一广播信息；统计模块，用于根据接收到的所述第一广播消息的应答消息，统计节点度； 接收模块，用于接收其它节点发送的第二广播信息，所述第二广播信息中包含其他节 点的节点度信息；比较模块，用于当自身的剩余能量大于第一阈值时，根据接收到的其他节点的第二广 播消息，比较其他第二广播消息的节点度和自身的节点度，如果自身的节点度最大则发布 成为簇头的公告信息。
8.根据权利要求7所述的网络拓扑分簇处理系统，其特征在于，所述第一广播信息中 包括发送节点的ID。
全文摘要
本发明实施例涉及网络拓扑分簇处理方法和处理系统，网络拓扑分簇处理方法具体包括向其他节点发送第一广播信息；根据接收到的所述第一广播消息的应答消息，统计节点度；接收其它节点发送的第二广播信息，所述第二广播信息中包含其他节点的节点度信息；根据接收到的其他节点的第二广播消息，比较其他第二广播消息的节点度和自身的节点度，如果自身的节点度最大则发布成为簇头的公告信息。所以本发明实施例网络拓扑分簇处理方法和处理系统，根据节点的剩余能量和节点的节点度来选择节点作为簇头节点，而不必使用复杂的簇头节点选择算法来进行簇头节点的选择，因此占用时间少，消耗能量少。
文档编号H04W84/18GK101801113SQ200910005310
公开日2010年8月11日 申请日期2009年2月5日 优先权日2009年2月5日
发明者张兴炜 申请人:华为技术有限公司
最新回复(0)