物聯網下自組織無線網絡Ad Hoc算法的新技術設計

李瑞江

摘 要： 為了進一步改進自組織無線網絡Ad Hoc的抗毀性，建立了信道分配的著色模型，對[α=0.585 7]進行了信道分配模型分析，在[a=18]時，所需的圓數量為64個，信道的數量為79個。進行算法求解分析，得出抽掉的節點數越多，網絡的抗毀性越差，結果分析還發現5%相交面積的抗毀性小于18%相交情況的抗毀性，體現設計模型的抗毀性優勢明顯。

關鍵詞： Ad Hoc網絡； 信道分配； 抗毀性； 相交面積

中圖分類號： TN958?34； TP391.4 文獻標識碼： A 文章編號： 1004?373X（2015）11?0024?03

A new technical design of Ad Hoc algorithm for self?organized

wireless networks under Internet of Things

LI Rui?jiang

（Xinjiang Institute of Light Industry Technology， Urumchi 830000， China）

Abstract： To further improve the Ad Hoc anti?destroying ability of self?organized wireless networks， the recolor model of channel allocation is established. When [α=]0.585 7， the model of channel allocation is analyzed. When [a=18，] the demand of circle number is 64 and the channel number is 79. The algorithm solution analysis is carried out in anti?destroying ability analysis. A conclusion is obtained that the more number of nodes are removed， the worse network anti?destroying ability is. The result analysis shows that the anti?destroying ability of 5% intersection area is less than 18% intersection area， the obvious advantages of anti?destroying ability is reflected by the designed model.

Keywords： Ad Hoc network； channel allocation； anti?destroying ability； intersection area

0 引 言

隨著社會經濟發展和技術進步，Ad Hoc網絡已經成為網絡技術發展的一個熱點。對于大型公司野外任務和部隊野外訓練而言，有一個能夠實時傳遞信息并實現信息初步處理的系統是十分重要的。Ad Hoc網絡能夠較為良好地完成這個任務，而且該網絡有諸多優點，例如不需要基站建設，不需要特定的交換路由節點，并且實現了隨機組建系統和接入形式的靈活和穩定。因此，這個系統在實際生活中有很多應用[1?5]。但是受發射信號的功率和信道的一定限制，導致節點通信因依靠無線信號傳輸而受到限制。因此要建立中間點作為中轉點以實現信息的共享[6?9]。因此，在系統建立過程中就要面臨一個重要的問題，即如何建立中介點，以多大的距離為標準建立中間點。在這個網絡系統中，實行先到先服務，因此避免了信號沖突導致的通信不暢等問題[10]。基于這一背景，本文介紹基于Ad Hoc網絡中的信道分配模型建立及其抗毀性研究，并具體分析其應用前景。

1 信道分配的著色模型

1.1 建立理論模型

在一個1 000[×]1 000（面積單位）的正方形區域內構建一個Ad Hoc網絡，用最少個半徑都是100的圓完全覆蓋，要求相鄰兩個圓的公共面積不小于一個圓面積的[a0%（a0=5 or a0=18）]。要使圓域被完全覆蓋就必會有大量重合部分，盡量減少重合部分的面積且不會引起通信盲區是解決該問題的關鍵點。如圖1所示，設定變量角度[α，][β，]分別從橫向和縱向來確定圓的個數。

約束條件：正方形面積和圓面積的重合部分面積最小化，但是要保證相交圓的面積占總面積的比重，如[a%，]再有就是不能出現通信故障和通信盲區。在這些條件基礎上建立如下模型：

目標函數：

[Min Z=mrow×nrank+ceilnrank2×w]

[s.t. mrow=ceil1 0002rcosα（ 1 ）d=（2?r?sinβ）2-（r?cosα）2（ 2 ） nrank=ceil1 000d（ 3 ）90°-β090°π-sinβ0cosβ0=π×a0%（ 4 ） β1=90°-α2 （ 5 ）Max（β0，β1）≤β<π（ 6 ）0<α≤π2 （ 7 ）w= 1， x0為偶數 0， x0為奇數 （ 8 ）x0=ceil1 000rcosα （ 9 ）]

參數含義解釋：[mrow]為第一行中一跳覆蓋區的個數；[d]為每增加一行增加覆蓋區域的高度；[nrank]為要覆蓋整個正方形所需圓的行數；[β0]為當相交圓公共部分的面積恰好占總圓面積的[a0%]時的弦割角；[β1]為三圓共點弦割角的邊界值；[α]為相交弦所對圓心角的一半；[w]為受在該區域內圓弦心距的數量控制；[ceil]為向上取整數；[a0%]為相交圓的公共部分占圓面積的比例。

模型解釋：方程（1）限定了每一行有多少個圓。具體表示方法如下：方程（2）和（3）表示完全覆蓋正方形需要多少個圓。方程（4）表示相交圓面積在整個圓中正好是[a%]時的弦割角大小。方程（5）表示當3個圓具有一個共同點的時候，弦割角的大小。方程（6）描述了弦割角的取值范圍，只有在這個范圍內方程才是有意義的。方程（7）是一個限定范圍，表示相交弦所對的圓心角的[12]應該在的取值范圍。方程（8）和（9）表示通信區內一跳覆蓋區的數量。

1.2 著色模型

著色模型中，對公式的設計和計算的準確性要求很高。把[a=6，]10分別代入之前的模型，利用數學軟件進行求解，可以得出，把[a=6]時，需要圓至少40個。

所謂信道分配，即對信息資源進行分配。根據著色模型基本理論，將[n]個圓劃分成[K]個部分，將每兩個圓的共有部分設計成為信息的通道，將會產生[K]個顏色。而且[K]是最小值，即無法再劃分為[K-1]個子集。[K]也是需要顏色的最少數目。這個過程需要求出圖的獨立集合，并從中挑選出最小值，這就是求出顏色數量的基本方法。

圖2所示的著色圖，是通過上述算法計算出[α=0.585 7]時的信道安排。不同的顏色表示的是不同的信道，著色會有差異；而公共部分沒有著色的區域是不同信道表示的最好方式，在實踐中有很大的應用空間。

當[a=18]時，通過計算得出需要圓的數量為64個，信道的數量為79個。此時的著色信道如圖3所示。

2 抗毀性分析

抗毀性是網絡系統的一個重要技術，抗毀性的能力是衡量中斷部分節點之間的通信需要破壞的鏈接數量。抗毀性的分析需要從黏聚度和連通度兩個角度進行分析。本文只討論在去除了一部分節點之后網絡的連通度。一般而言，網絡的連通度和抗毀性之間成正比。

2.1 抗毀性算法

對抗毀性的計算需要依照一定的約束條件進行，其具體算法見圖4。

首先假設節點的表示方法，[P（A，B）]表示[A～B]的最大獨立軌條數。獨立軌表示的是[A～B]公共內的距離。假設[G]是一個非平凡的連通示意圖，[{V1][V1]是[G]的點割集或[G?V1]是平凡圖}為[G]的點連通度。即[K（G）]是使得[G]不連通或成為平凡圖所必須刪除的頂點的最小個數。這個假設在實踐中被證明是有效的。接下來，將重點分析[A～B]的最大軌數的計算方法。連通的條件是在[G]圖中的[v]頂點能夠正常地發揮其設計作用，而非成為虛設點。

下面將分析圖4表示的計算內容。假設[K（G）]的趨勢是向正無窮大，然后在此基礎上分析圖中每一個頂點。如果[A]和[B]是不相鄰的，中間具有很寬的范圍，那么求[P（A，B）]可以采取求最大流的方法進行求解。而在對其進行一系列的分析之后，筆者發現，割頂集合的建立就會為頂連通度的實現提供前提。

2.2 設計的抗毀性分析

在前文所述的算法中，可以實現對節點的求解，并能夠計算出在去除一些節點之后的網絡連通度。在這個過程中，網絡節點的連通具有一定的規律可循，因此從數學概率理論的角度，可以計算出網絡節點的連通概率。

根據以上算法可求得從節點集合中隨機地抽掉2%，5%，10%，15%等數量的節點后網絡的連通度，就可以求得該網絡節點的連通概率，表1給出了模型的抗毀性算法應用的結果。

由此得出結論，節點越多，抗毀性越強，否則反之。而縱向的比較能夠得出結論，相交面積越小，抗毀性越強。這兩個結論是整個系統的一個設計基礎和實現系統功能最重要的部分。而相交面積的擴大沒有帶來面積內節點數量的增加，因此導致圓的個數也在不斷增加。將這兩個結論代入表格中的數據進行進一步的檢驗，可以證明其準確性。

表1 模型的抗毀性算法應用

[公共面積＼&抽調節點＼&總通信

節點數＼&2%＼&5%＼&10%＼&15%＼&5%＼&99.998 4%＼&99.94%＼&99.20%＼&96.75%＼&155＼&18%＼&99.75%＼&99.48%＼&97.41%＼&92.95%＼&225＼&]

3 總 結

Ad Hoc網絡中的信道分配模型建立及其抗毀性的研究涉及的變量多，計算方法復雜多變，并需要很多的限制條件。而且按區域的分布劃分信道，有一個潛在的問題，即每一個節點的發射信號面積之間有重合部分，因此導致了一定程度的資源浪費。因此該系統面臨著一個新的挑戰，即如何調整系統設計方式，并實現一定的技術進步以達到資源利用率的最大化和最優化。

參考文獻

[1] 劉冰，劉全，禹華鋼.Ad Hoc網絡中的區域劃分和資源分配問題[J].數學的實踐與認識，2007，37（14）：16?24.

[2] 劉耀斌.基于平面拼裝的Ad Hoc網絡抗毀性研究及其信道分配[J].吉林大學學報：理學版，2008，46（6）：1159?1163.

[3] 胡興雨，張學義，吳俊，等.移動Ad Hoc網絡拓撲結構抗毀性測度模型[J].計算機工程與應用，2011（2）：78?80.

[4] 盧曉珊，賀永金，何偉，等.Ad Hoc網絡中的區域劃分和資源分配研究[J].數學的實踐與認識，2009，39（8）：53?60.

[5] 徐武，雷劍，陶紅亮.Ad Hoc網絡中的覆蓋和互聯問題研究[J].景德鎮高專學報，2009（2）：29?30.

[6] 任治國.Ad Hoc網絡中的區域劃分和資源分配問題[J].咸寧學院學報，2012，32（6）：44?46.

[7] 趙耀培，張福強，董茜.Ad Hoc網絡技術研究進展[J].信息技術與信息化，2005（3）：9?12.

[8] 余旭濤，張在琛，畢光國.一種Ad Hoc網絡可靠性度量：網絡均衡度[J].應用科學學報，2005，23（6）：582?585.

[9] 田方，劉福杰，常義林.無線Ad Hoc網絡關鍵技術研究[J].計算機與網絡，2002（20）：50?52.

[10] 王華，薛濤，崔云平，等.Ad Hoc網絡技術[J].硅谷，2012（17）：9?10.