无线感测器之集中式平衡树演算法静态规划资料传输方法

摘要

一种无线感测器之集中式平衡树演算法静态规划资料传输方法，系先将无线感测器网路系统之各无线感测器节点逐一分层，然后进行第一次拓朴，再透过一阶负载平衡树演算法进行资料回传路径的规划，使各层感测器节点得知回传路径的父节点，使闸道器辖下形成复数个子树。在一阶负载平衡树路由演算法完成路径规划后，为避免各子树之第一层无线感测器节点负载发生不平衡状态，系先对负载最大的子树，找出其他子树中与负载最大子树内节点有通信连结且负载最小的子树。考虑同时与负载最大子树及负载最小子树有通信连结的所有节点，评估这些节点之负载量，若有符合更换父节点条件，则将该节点的父节点切换为负载最小子树中与其通信连结的感测器节点。

主权项

一种无线感测器之集中式平衡树演算法静态规划资料传输方法，至少包括下列步骤：步骤1：先利用一闸道器将复数个无线感测器节点资料收集完全，以建构出一无线网感测器网路并进行分层，接着执行一网路拓朴；步骤2：藉由一主控平台接收该网路拓朴并透过一阶负载平衡树演算法规划各层中之各个无线感测器节点之资料回传路径，以订定各层中之各个无线感测器节点回传资料之父节点，使该闸道器辖下形成复数个子树；步骤3：当该复数个子树之第一层节点出现负载值(系于一子树中，某一节点正接收其他节点资讯时连结之节点数量即为负载值)不平衡时，系于该复数个子树中先选择一负载最大子树i>Tree/i>(max)；步骤4：再于其他子树中选择出一负载最小子树i>Tree/i>(min)，并找出该负载最小子树i>Tree/i>(min)与该负载最大子树i>Tree/i>(max)内有通信连结之节点是否仅为一个；步骤5：若仅为一个，则计算该有通信连结之节点之一节点负载，并利用该主控平台判断并计算该最大负载子树i>Tree/i>(max)内之节点负载值i>T/i>(max)扣除该最小负载子树i>Tree/i>(min)内之节点负载值i>T/i>(min)后是否大于该负载最大子树i>Tree/i>(max)中各个有连结之节点之该节点负载；以及步骤6：若计算之结果为大于该节点负载时，即将该负载最大子树i>Tree/i>(max)中符合计算结果之节点切换到该负载最小子树i>Tree/i>(min)中，以改变该负载最大子树i>Tree/i>(max)中与该负载最小子树i>Tree/i>(min)具有通信连结之节点的父节点。如申请专利范围第1项所述之无线感测器之集中式平衡树演算法静态规划资料传输方法，其中更包含下列步骤：若该最大负载子树i>Tree/i>(max)及该最小负载子树i>Tree/i>(min)中没有任何一个节点计算之结果系大于该节点负载时，则针对与该最大负载子树i>Tree/i>(max)之节点有通信连结的其他子树中进行搜寻，找出一负载第二小子树@sIMGCHAR!d10013.TIF@eIMG!，并再次进行计算该最大负载子树i>Tree/i>(max)内之节点负载值i>T/i>(max)扣除该负载第二小子树@sIMGCHAR!d10014.TIF@eIMG!内之节点负载值@sIMGCHAR!d10015.TIF@eIMG!后是否大于两子树间有通信连结之该节点负载，又若两子树中仍无符合的节点，则再于更小负载之子树中寻找，依此类推，直到找到有通信连结且符合计算之子树，并进行父节点之切换。如申请专利范围第1项或第2项所述之无线感测器之集中式平衡树演算法静态规划资料传输方法，其中该一阶负载平衡树系以节点之负载量及其上下层节点之间的关系，决定节点间建立连线的优先顺序。如申请专利范围第1项或第2项所述之无线感测器之集中式平衡树演算法静态规划资料传输方法，其中该一阶负载平衡树由最下层节点开始，于最下层的所有感测器节点中选择一个节点，由可连结节点的上层中选择适当的节点当作子节点的父节点，以转传资料。如申请专利范围第1项或第2项所述之无线感测器之集中式平衡树演算法静态规划资料传输方法，其中该无线感测器节点负载系为所有需经由该节点传递资讯的节点数加上其本身节点的加总个数和。一种无线感测器之集中式平衡树演算法静态规划资料传输方法，主要包括：步骤1：先利用一闸道器将复数个无线感测器节点资料收集完全，以建构出一无线感测器网路之分层，然后执行第一次网路拓朴；步骤2：藉由一主控平台接收该网路拓朴并透过一阶负载平衡树演算法规划各层中之各个无线感测器节点之资料回传路径，已订定各层中之各个无线感测器节点回传资料之父节点，使闸道器辖下形成复数个子树；步骤3：当该复数个子树之第一层节点出现负载值不平衡时，系于该复数个子树中先选择一负载最大子树i>Tree/i>(max)；步骤4：再于其他子树中选择出一负载最小子树i>Tree/i>(min)，并找出该负载最小子树i>Tree/i>(min)与该负载最大子树i>Tree/i>(max)内有通信连结之节点是否为复数个；步骤5：若有通信连结之节点为复数个，则计算出各个有连结之节点之节点负载，并利用该主控平台判断并计算该最大负载子树i>Tree/i>(max)内之节点负载值i>T/i>(max)扣除该最小负载子树i>Tree/i>(min)内之节点负载值i>T/i>(min)后的二分之一是否接近该节点负载；以及步骤6：若计算之结果为接近该节点负载时，即将该负载最大子树i>Tree/i>(max)中符合计算结果之节点切换到该负载最小子树i>Tree/i>(min)中，以改变该负载最大子树i>Tree/i>(max)中与该负载最小子树i>Tree/i>(min)具有通信连结之节点的父节点。如申请专利范围第6项所述之无线感测器之集中式平衡树演算法静态规划资料传输方法，其中更包含下列步骤：若该最大负载子树i>Tree/i>(max)及该最小负载子树i>Tree/i>(min)中没有任何一个节点计算之结果系接近该节点负载时，则针对与该最大负载子树i>Tree/i>(max)之节点有通信连结的其他子树中进行搜寻，找出一负载第二小子树@sIMGCHAR!d10016.TIF@eIMG!，并再次进行计算该最大负载子树i>Tree/i>(max)内之节点负载值i>T/i>(max)扣除该负载第二小子树@sIMGCHAR!d10017.TIF@eIMG!内之节点负载值@sIMGCHAR!d10018.TIF@eIMG!后的二分之一是否接近两子树间有通信连结之该节点负载，又若两子树中仍无符合的节点，则再于更小负载之子树中寻找，依此类推，直到找到有通信连结且符合计算之子树，并进行父节点之切换。如申请专利范围第6项或第7项所述之无线感测器之集中式平衡树演算法静态规划资料传输方法，其中该一阶负载平衡树以节点之负载量及其上下层节点之间的关系，决定节点间建立连线的优先顺序。如申请专利范围第6项或第7项所述之无线感测器之集中式平衡树演算法静态规划资料传输方法，其中该一阶负载平衡树由最下层节点开始，于最下层的所有感测器节点中选择一个节点，由可连结节点的上层中选择适当的节点当作子节点的父节点，以转传资料。如申请专利范围第6项或第7项所述之无线感测器之集中式平衡树演算法静态规划资料传输方法，其中该无线感测器节点负载系为所有需经由该节点传递资讯的节点数加上其本身节点的加总个数和。