基于超圖的熱計量表物聯(lián)網(wǎng)分簇算法

陳云云

摘要：為了提高熱表物聯(lián)網(wǎng)中熱表數(shù)據(jù)傳送的準確性和及時性，文章把超圖理論引入熱表物聯(lián)網(wǎng)中，提出了一種基于超圖的熱表物聯(lián)網(wǎng)分簇算法，此算法是把物聯(lián)網(wǎng)采集數(shù)據(jù)的這種網(wǎng)絡(luò)拓撲結(jié)構(gòu)看成是一個超圖模型，在超圖模型劃分的簇域中舉出一個簇頭，它作為本地基站將簇內(nèi)節(jié)點傳給它進行數(shù)據(jù)融合后再傳給基站，提高數(shù)據(jù)傳輸?shù)某晒β?，降低了?jié)點消耗的能量，延長了網(wǎng)絡(luò)壽命。最后通過仿真，將基于超圖的熱表物聯(lián)網(wǎng)分簇算法與傳統(tǒng)經(jīng)典的LEACH算法進行比較，實驗結(jié)果表明該算法能夠有效地提高數(shù)據(jù)傳輸成功率，并減少節(jié)點能量消耗。

關(guān)鍵詞：超圖；熱量表；物聯(lián)網(wǎng)；分簇算法

隨著中國經(jīng)濟建設(shè)和熱力事業(yè)的蓬勃發(fā)展，物聯(lián)網(wǎng)應(yīng)用到熱力系統(tǒng)成為人們關(guān)注的焦點，把物聯(lián)網(wǎng)理念引入熱力系統(tǒng)之后，很大程度上提高了熱力系統(tǒng)的信息化水平，特別是對熱表數(shù)據(jù)抄送具有十分重要的意義。如何對熱量表采集的數(shù)據(jù)進行處理，使數(shù)據(jù)能夠快速、準確地傳送到管理主機，一直是目前研究熱表物網(wǎng)者迫切需要解決的問題。超圖作為一般化圖的推廣自1973年berge在文獻[1]中系統(tǒng)提出之后就備受人們的關(guān)注，關(guān)于超圖理論的應(yīng)用也越來越廣泛。為了使熱表傳感器在傳送數(shù)據(jù)時降低能量的消耗，同時提高數(shù)據(jù)傳送的快速準確，本文將超圖理論引入熱表物聯(lián)網(wǎng)中，提出了一種基于超圖的熱表物聯(lián)網(wǎng)數(shù)據(jù)分簇算法。

基于超圖的熱表物聯(lián)網(wǎng)分簇算法設(shè)計的重點是降低能量的消耗，把物聯(lián)網(wǎng)采集數(shù)據(jù)的這種網(wǎng)絡(luò)拓撲結(jié)構(gòu)看成是一個超圖模型，在超圖模型劃分的簇域中舉出一個簇頭，它作為本地基站將簇內(nèi)節(jié)點傳給它進行數(shù)據(jù)融合后再傳給基站，提高數(shù)據(jù)傳輸?shù)某晒β?，降低了?jié)點消耗的能量，延長了網(wǎng)絡(luò)壽命。

1 基于超圖的熱表物聯(lián)網(wǎng)信息處理方案

基于超圖的熱表物聯(lián)網(wǎng)分簇算法是一種層次型拓撲結(jié)構(gòu)，將熱表傳感器網(wǎng)絡(luò)的拓撲結(jié)構(gòu)抽象為超圖模型，此模型根據(jù)一定的規(guī)則要求劃分為簇域，在簇域中選取簇頭作為數(shù)據(jù)控制的中心節(jié)點，將簇內(nèi)的數(shù)據(jù)在本地進行數(shù)據(jù)融合后再轉(zhuǎn)發(fā)給基站更近的簇頭或直接發(fā)送到基站，這樣減少了數(shù)據(jù)轉(zhuǎn)發(fā)的次數(shù)，并節(jié)省了網(wǎng)絡(luò)中節(jié)點傳輸?shù)哪芰俊?/p>

I.I 超圖定義

定義1：設(shè)V={v₁，v₂，v₃…v_n}是一個集合，集合里有n個結(jié)點，ξ={e₁，e₂，e₃…e_n）也是一個集合，且滿足 ，可以稱H=（V，ξ）是在v上的超圖。

定理1：如果超圖為超樹，當且僅當其對應(yīng)的二分圖G是樹。

由于頂點和超邊的二元關(guān)系的復(fù)雜性，一個連通超圖H的生成樹T并不總是存在的。

1.2 超圖模型

用超圖 來抽象表示一個層次型的傳感器網(wǎng)絡(luò)。其中 是節(jié)點的集合，并且其中的每個節(jié)點對應(yīng)每個傳感器節(jié)點， 是超邊的集合，把監(jiān)測的網(wǎng)絡(luò)結(jié)構(gòu)看作是超邊，把 記為主干超邊，則 ，其中M為 的頭節(jié)點， 為E，的網(wǎng)關(guān)節(jié)點，作用是與其他連接 為E，的剩余節(jié)點。根據(jù)已有的網(wǎng)格劃分算法網(wǎng)絡(luò)簇結(jié)構(gòu)可以分為2類：

（l）相鄰的網(wǎng)格之間有共同的網(wǎng)關(guān)節(jié)點，即 。

（2）相鄰的網(wǎng)絡(luò)之間無共同的網(wǎng)關(guān)節(jié)點，節(jié)點之間進行通信可以通過網(wǎng)關(guān)，即 。

根據(jù)定理1可以推出，給定一個連通超圖，依據(jù)（1）劃分的網(wǎng)格來生成超樹是不可能的，如果基于（l）來劃分網(wǎng)絡(luò)，可能出現(xiàn)的分簇情況如圖1所示，抽象的超圖如圖2所示。如果基于方式（2）來劃分網(wǎng)格，抽象的超圖如圖3所示，可以選擇2個網(wǎng)格之間節(jié)點連接權(quán)值最小的2個節(jié)點作為2個網(wǎng)關(guān)節(jié)點，這2個網(wǎng)關(guān)節(jié)點連成一條邊，稱為超邊e，以連接2個主干超邊?；诜绞剑?）劃分網(wǎng)格可以生成超樹T。

1.3 方案描述

本文提出的基于超圖的熱表物聯(lián)網(wǎng)分簇算法，其設(shè)計思想是簇首的選取是通過計算簇內(nèi)結(jié)點權(quán)值的大小來確定，權(quán)值最大的作為簇首，具體的算法描述是把熱表區(qū)域劃分為n個正方形區(qū)域，如圖4所示。

首先用標定的方法標定坐標點（在正方形的中心），標定好之后，依據(jù)各個坐標點與傳感器距離的長短，把傳感器加入到簇域內(nèi)。

劃分好簇域后，在每個簇域內(nèi)任意選取一個標記點H，選取之后，首先計算H的權(quán)值，然后再計算域內(nèi)其他結(jié)點的權(quán)值，把這幾個權(quán)值進行比較，選取權(quán)值最大的節(jié)點為簇頭，最后簇頭節(jié)點作為中心節(jié)點進行數(shù)據(jù)的廣播。

在劃分好的簇域中，本文把簇域內(nèi)的簇頭看作是一個路由器，簇域內(nèi)的每個節(jié)點把采集到的數(shù)據(jù)直接傳送給路由器節(jié)點（也就是簇頭節(jié)點），路由器收到數(shù)據(jù)之后，對數(shù)據(jù)進行分析、處理和轉(zhuǎn)發(fā)，也就是說把熱表傳感器的所有數(shù)據(jù)匯聚到基站，然后通過無線網(wǎng)絡(luò)發(fā)送到熱力公司。

2 算法分析和仿真

仿真的監(jiān)測環(huán)境設(shè)置在lOOmXlOOm區(qū)域內(nèi)，設(shè)置監(jiān)測區(qū)域的上方是匯聚的結(jié)點，即（100，300）。設(shè)置通信圓半徑為15.6m，每個節(jié)點的初始能量IOJ，本文對基于超圖的熱表物聯(lián)網(wǎng)分簇算法（HCTA）進行仿真，并與經(jīng)典的LEACH算法進行比較，主要評價基于超圖的熱表物聯(lián)網(wǎng)熱表傳感器算法性能：數(shù)據(jù)傳輸成功。

首先計算傳輸數(shù)據(jù)的成功率，如圖5所示。通過仿真可以得到HCTA算法數(shù)據(jù)傳輸成功率較LEACH算法高。這是因為在超圖算法中劃分了多個簇域，在每個簇域中計算節(jié)點的權(quán)值，把權(quán)值最大的記為簇頭，把簇頭看作是路由器給基站發(fā)送數(shù)據(jù)，當路由器的能量低到一定值后，給基站發(fā)送特定的數(shù)據(jù)，基站對數(shù)據(jù)進行分析來判斷網(wǎng)絡(luò)運行的情況，從而判斷是否重新選取簇頭，這樣做使得在通信的過程中平衡了網(wǎng)絡(luò)的能量，從而使網(wǎng)絡(luò)能夠持續(xù)運行，而LEACH算法中簇頭的選取是隨意的，如果基站與簇頭通信的過程中判斷需要重新選取簇頭，則簇頭的選取是無規(guī)則的，任意選取，最后導(dǎo)致多個簇頭與基站進行數(shù)據(jù)傳輸，這樣做使得在通信的過程中過多地消耗了網(wǎng)絡(luò)的能量，從而使網(wǎng)絡(luò)不能夠持續(xù)運行，數(shù)據(jù)傳輸?shù)某晒β氏陆怠?/p>

3 結(jié)論

把超圖理論引入熱表物聯(lián)網(wǎng)之后，降低了熱表傳感器各個節(jié)點消耗的能量，延長了網(wǎng)絡(luò)壽命，從而保證了數(shù)據(jù)傳送的準確性和實時性。文中把物聯(lián)網(wǎng)大規(guī)模的無線傳感器網(wǎng)絡(luò)拓撲抽象為超圖模型，提供高效網(wǎng)絡(luò)服務(wù)。通過仿真可以看出，此算法優(yōu)于經(jīng)典的LEACH算法，不但能夠有效地提高數(shù)據(jù)傳輸成功率，而且能夠減少節(jié)點消耗的能量。