面向智慧家居的異構自組織網絡分簇算法＊

鄧曉平，馬路娟

(山東建筑大學信息與電氣工程學院，山東 濟南 250101)

0 引言

隨著5G 的商用，作為5G 重要應用場景之一的智慧家居受到了學術界和工業界的廣泛關注。據預測，我國智慧家居市場規模2022 年有望超過250 億美元，占全球市場份額的25%左右[1]。然而，隨著數據流量和連接數量的爆發性增長，原有的集中式架構不能滿足大量設備的接入需求，支持設備隨時接入和退出的自組織網絡成為智慧家居領域的研究熱點[2]。基于分簇的層次化自組織網絡架構可以減少網絡中的通信量，提高網絡的可擴展性，并降低節點移動性帶來的影響。

低功耗自適應集簇分層型協議(Low Energy Adaptive Clustering Hierarchy,LEACH)是分簇算法的典型代表，其基本思想是以循環的方式隨機選擇簇頭節點，將整個網絡的能量負荷平均分配到每個節點，從而達到降低網絡能源消耗、提高網絡生存周期的目的[3]。在此之后，一系列基于LEACH 的改進型算法被提出[4-6]。Ahmed[7]根據路徑成本和節點之間的連接數來選擇每個簇的簇頭。Mustafa[8]提出了三層架構LEACH 協議。韓廣輝[9]在簇頭選取時引入了節點的剩余能量以及網絡的平均能量，使剩余能量比網絡平均能量高的節點優先充當簇頭。李芳芳[10]采用分布式自協商和集中式相結合的成簇算法。近幾年也有一些其他分簇算法被提出。Ahmad[11]提出了一種啟發式的分簇算法，提高了簇的有效性和可靠性，并降低了控制開銷。已有分簇算法大都針對無線傳感器網絡提出，基于節點平等性假設，并且以降低能耗為目標，不適用于節點異構、時延和到達率敏感的智慧家居網絡。

為進一步改善設備的到達率和時延均衡性，本文在充分調研分析智慧家居網絡的特點基礎上，提出了適合智慧家居網絡的分簇算法，其創新性與貢獻具體如下：

⑴在分簇算法中，分簇算法自動適應家庭拓撲，避免了簇頭和成員節點之間穿墻通信造成信號的嚴重衰減；

⑵在簇頭決策階段，提出了對節點進行多維度優先級劃分的方法，確保了選出的簇頭具有更好的通信能力和計算能力、更長的生命周期、更低的失效率；

⑶在數據發送階段，給出了基于業務特征選擇信道分配策略，降低了傳輸時延；

⑷部署構造了仿真環境，并進行了性能驗證。仿真結果表明，與傳統的LEACH 分簇算法相比，所給出的異構自組織網絡分簇算法更加適合具有突發數據的智慧家居網絡，并且設備的時延更加均衡。

1 智慧家居網絡特點分析

要設計適合智慧家居網絡的分簇算法，有必要對這種網絡的特點進行分析，其特點主要體現在以下幾方面。

1.1 異構性

智慧家居網絡是一個典型的異構網絡，網絡中的設備在通信能力、計算能力、存儲能力等方面都存在很大差異。已有的分簇算法大都基于同構網絡，即所有節點都是完全一致的。即使在某些算法中，考慮了網絡的異構性，也是只考慮了節點的初始能量不同，不符合智慧家居網絡的實際情況。

1.2 覆蓋范圍較小

家庭網絡覆蓋范圍相對較小，一般只有幾十平米，最多幾百平米。并且，我們可以很容易得到家庭戶型圖和固定設備的擺放位置，為分簇算法提供依據。

1.3 數據流具有突發性和不均勻性

無線傳感網節點不斷采集周邊環境的數據，通過固定的周期上傳數據，數據流是均勻分布的。但是對于家庭網絡來說，既有周期上傳的數據，也有突發的數據。

2 面向智慧家居網絡的分簇算法

本文所給出的分簇算法的過程分為初始化階段、分簇階段和數據傳輸階段。初始化階段分為區域劃分階段和簇劃分階段，分簇階段分為簇頭選舉階段和簇形成階段，數據傳輸階段分成很多幀，每一幀分為突發時隙階段和固定時隙階段，幀結構如圖1所示。

圖1 幀結構

2.1 算法假設

適合智慧家居網絡的分簇算法基于以下合理假設。

⑴房子的戶型圖和設備在房間中的位置已知。

⑵ 將家庭中的設備按照能量供給方式分為兩類：常帶電設備和充電設備，假設固定設備都是常帶電設備，定義為A 類設備，移動設備都是充電設備，定義為B 類設備。假設節點知道自己屬于哪一類，并且B類設備可以感知自己的剩余能量。

⑶ 將家庭中的設備按照通信距離遠近分為兩類：I類設備和II類設備，I類設備指的是使用移動蜂窩網通信的設備，II 類設備指的是使用Wi-Fi、藍牙、Zigbee和D2D通信的設備。

⑷用一個計算能力系數C 來表示設備的計算能力，C是介于0到1之間的一個小數，0表示該設備不具有計算能力，1 表示該設備具有整個家庭網絡中最強的計算能力。假設節點知道自己的計算能力系數。

⑸將整個家庭中的設備按照是否定期上傳數據分為兩類：周期設備和突發設備。假設節點知道自己屬于哪一類，并且周期設備知道自己的上傳周期是多長。

2.2 初始化

初始化工作的第一步是利用設備的地理位置信息，以房間為單位將設備劃分成不同的區域，小房間劃分成一個區域，大房間劃分成多個區域，每個區域就是一個簇，給每個簇進行編號。簇半徑按照圖2所示方法予以確定，該方法將整個家庭網絡按照房間劃分成大小不等的矩形區域，小房間被劃分成一個區域，大房間被劃分成多個區域。每個矩形區域都能被完全包含在半徑為Ri的圓中，要求：Ri≤R0,i=1,2,3,4,5,6。

圖2 簇的劃分

2.3 簇形成

簇頭選舉只在已經劃分好的區域內進行，不需要跟基站進行通信，只需要在簇頭選舉完成后通知基站，處理本地化，降低了基站負載，縮短了簇頭選舉時間。在選舉簇頭的過程中，充分考慮家庭網絡的異構性，每個區域根據設備類型不同和應用場景不同采用不同的簇頭選擇標準。并且基于節點地理位置選擇簇頭，使選出的簇頭與簇成員之間具有更小距離。

⑴設備篩選

只有I類設備參與簇頭選舉，II類設備在簇頭選舉階段關閉自己的通信模塊，不參與簇頭選舉，如果簇中存在A 類設備，B 類設備不參與簇頭選舉，當簇中不存在A類設備時，才在B類設備中選擇簇頭，這個過程稱為設備篩選，如圖3 所示。當存在A 類設備的家庭網絡中發生斷電時，A 類設備將完全失效，重新在B 類設備中選擇簇頭。

圖3 設備篩選流程圖

⑵計算競爭值

如果是A 類設備競選簇頭，就不考慮移動速度和剩余能量，將計算能力C 節點位置系數L 按照一定系數加權。位置系數是按照節點在簇中所處地理位置決定的，越靠近簇中心的設備位置系數越大，位于簇的圓心位置的設備位置系數為1，位于圓周上的設備位置系數為0，如圖4 所示為簇i內設備位置系數的計算方法，設備1 的位置系數是1，設備3 的位置系數是0，設備2 的系數。設備i的競爭值Wi=w1Ci+w2Li，其中w1+w2=1，w1和w2的值根據具體的應用場景來確定。選擇競爭值最大的設備作為本簇的簇頭。

圖4 位置系數示意圖

如果是B 類設備競爭簇頭，就要考慮移動速度和剩余能量，分別將移動速度和剩余能量歸一化為速度系數和能量系數。速度系數用S來表示，固定設備的速度系數為1，定義整個家庭網絡中具有最大速度Vmax的設備速度系數為0，設備i的速度為Vi時速度系數。假設整個網絡的充電設備中具有最大剩余能量Emax的設備能量系數是1，能量為0 的設備能量系數是0，則具有剩余能量Ei的設備能量系數Ni=EiEmax。設備i的競爭值Wi=w1Ci+w2Li+w3Si+w4Ni，其中w1+w2+w3+w4=1，w1，w2，w3，w4的值根據具體應用場景來確定。選擇競爭值最大的設備作為本簇的簇頭。

每個設備將自己的競爭值在簇內進行廣播。如果接收到其他節點的競爭值大于自己的競爭值，則關閉通信模塊直到簇頭選舉階段結束；如果在整個簇頭選舉階段，一直沒有收到比自己大的競爭值，則該節點當選為簇頭，并在簇頭選舉階段結束后廣播自己當選簇頭這一結果。

簇內成員節點收到本簇簇頭的當選廣播后，向簇頭發送加入請求，簇頭收到后予以確認，加入到自己的簇成員列表中，如圖5所示。

圖5 簇形成流程圖

2.4 數據傳輸

在家庭環境中，能量不再是首要考慮的問題，因此應盡量使用單跳傳輸，降低傳輸時延，包括簇頭與基站的通信，簇頭與成員的通信，一個簇內成員之間的通信，簇頭與簇頭的通信等。使用CDMA 來避免不同簇之間相互干擾，給每個簇分配不同的擴頻碼，如圖6所示。

圖6 擴頻碼分配

將整個數據傳輸階段分為很多幀，每一幀包括m個突發時隙和n個固定時隙，突發時隙用來傳輸突發數據，固定時隙用來傳輸周期上傳的數據，突發時隙和固定時隙所占一個幀的比例根據本簇內業務需求靈活確定。固定時隙階段每個時隙固定分配給某個周期上傳數據的設備，在每個幀的這個時隙到來時該設備上傳數據；突發時隙階段的時隙可以靈活分配，允許一個設備占用多個時隙，如圖7，設備1 和設備2是突發設備，設備3、4、5是周期設備。

圖7 時隙分配圖

3 仿真分析

3.1 仿真場景

以某智慧家居公司的實際部署構建仿真場景，房屋戶型圖和節點分布如圖8所示。

圖8 仿真場景

家庭內的設備包括以下類型，括號內的數字表示該類型設備的數量。

⑴ I 類A：冰箱⑵、彩電⑶、洗衣機⑵、空調⑷、熱水器⑴；

⑵I類B：手機⑸；

⑶II 類A：溫濕度傳感器⑻、光照傳感器⑹、可燃氣體探測器⑴、紅外探測器⑴、燈⑾、門磁⑹、微波爐⑴、電炊具⑴、洗碗機⑴、智能浴缸⑴、智能抽水馬桶⑴、電表⑴、水表⑴、燃氣表⑴、抽油煙機⑴、加濕機⑴；

⑷II類B：PDA+筆記本電腦⑷。

3.2 參數設置

信號穿透不同障礙物的衰減值如表1所示。

表1 損耗附加值取值表

能耗與功率設置如表2所示。

表2 能耗與功率設置

數據上傳周期及數據包大小如表3所示。

表3 家庭內各設備數據上傳周期及數據包大小

3.3 仿真結果

智慧家居環境更關注的性能是時延和可靠性，因此我們選擇時延和到達率作為本次仿真的性能評價指標，并將適合智慧家居的分簇算法（SH）與經典分簇算法LEACH進行比較。

當突發時隙在每個幀中設置為三個，突發數據大小為1.5*106bits 時，端到端時延和到達率的仿真結果圖9和圖10所示。

圖9 端到端時延對比圖

從圖9 可以看出，對于I 類設備和II 類A設備而言，兩種算法的時延差別不大，但是對于II 類B 設備，SH 算法比LEACH 算法的時延降低了36%，這是因為對II 類B 設備來說，數據包大而且傳輸速率低，在LEACH 算法中一個幀無法完成一個數據包的傳輸。而在適合智慧家居的分簇算法中，數據包比較大的突發數據可以占用長達三個時隙的突發時隙，保證任何數據都可以在一個幀內傳輸完成，因此時延較低。從圖10 可以看出，對于所有設備,適合智慧家居的分簇算法都達到了100%，這是因為在分簇的過程中采用了先分簇再選擇簇頭的方法，保證一個簇中的所有設備都處于同一房間中，避免了設備之間穿墻通信造成的較大衰減，而且使得一個簇內的設備距離較近，提高了成員設備與簇頭的可達性。

圖10 到達率對比圖

將突發數據包大小分別設置為3*106bits，4.5*106bits，6*106bits，7.5*106bits，9*106bits，突發時隙分別設置為6，9，12，15，18 個，觀察端到端時延的均衡性變化規律，結果如圖11和圖12所示。

圖11 LEACH算法設備端到端時延

圖12 適合智慧家居的分簇算法設備端到端時延

在LEACH算法中，A類設備對突發數據包的大小不敏感，B類設備隨著突發數據包的增大而增大，尤其是對于II類B設備，當數據包變為原來的五倍時，時延也變為原來的五倍。

適合智慧家居的分簇算法中，四種設備的時延都會隨著突發數據包的增大而增大，其中B 類設備的時延增長率更快，當突發數據包為原來的5 倍時，I 類B設備和II類B設備的時延分別為原來的三倍和四倍。

綜合以上時延和到達率的仿真結果，與LEACH算法相比，適合智慧家居的分簇算法可以顯著提升到達率和降低時延，并且使不同類型設備之間的時延更加均衡。

4 結論

針對智慧家居網絡的特點，本文提出了一種基于節點異構性和地理位置的智慧家居網絡分簇算法，并且基于智慧家居實際部署進行了仿真分析。根據仿真試驗結果，可以得出以下結論：①通過將簇的范圍限制在一個房間之內，并且選擇具有蜂窩網絡通信能力的設備作為簇頭，可以使設備的到達率達到100%；②通過在數據幀中設置突發時隙，可以顯著降低具有突發數據的設備時延；③采用固定時隙和突發時隙相結合的幀結構，可以提高不同類型設備的時延均衡性。本論文給出的算法為進一步提高實際智慧家居系統中無線通信模塊的網絡性能提供了基礎。