物聯(lián)網(wǎng)下自組織無線網(wǎng)絡(luò)Ad Hoc算法的新技術(shù)設(shè)計

李瑞江

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

關(guān)鍵詞： Ad Hoc網(wǎng)絡(luò)； 信道分配； 抗毀性； 相交面積

中圖分類號： 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 引 言

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

1 信道分配的著色模型

1.1 建立理論模型

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

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

目標函數(shù)：

[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為偶數(shù) 0， x0為奇數(shù) （ 8 ）x0=ceil1 000rcosα （ 9 ）]

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

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

1.2 著色模型

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

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

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

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

2 抗毀性分析

抗毀性是網(wǎng)絡(luò)系統(tǒng)的一個重要技術(shù)，抗毀性的能力是衡量中斷部分節(jié)點之間的通信需要破壞的鏈接數(shù)量?？箽缘姆治鲂枰獜酿ぞ鄱群瓦B通度兩個角度進行分析。本文只討論在去除了一部分節(jié)點之后網(wǎng)絡(luò)的連通度。一般而言，網(wǎng)絡(luò)的連通度和抗毀性之間成正比。

2.1 抗毀性算法

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

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

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

2.2 設(shè)計的抗毀性分析

在前文所述的算法中，可以實現(xiàn)對節(jié)點的求解，并能夠計算出在去除一些節(jié)點之后的網(wǎng)絡(luò)連通度。在這個過程中，網(wǎng)絡(luò)節(jié)點的連通具有一定的規(guī)律可循，因此從數(shù)學(xué)概率理論的角度，可以計算出網(wǎng)絡(luò)節(jié)點的連通概率。

根據(jù)以上算法可求得從節(jié)點集合中隨機地抽掉2%，5%，10%，15%等數(shù)量的節(jié)點后網(wǎng)絡(luò)的連通度，就可以求得該網(wǎng)絡(luò)節(jié)點的連通概率，表1給出了模型的抗毀性算法應(yīng)用的結(jié)果。

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

表1 模型的抗毀性算法應(yīng)用

[公共面積＼&抽調(diào)節(jié)點＼&總通信

節(jié)點數(shù)＼&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 總 結(jié)

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

參考文獻

[1] 劉冰，劉全，禹華鋼.Ad Hoc網(wǎng)絡(luò)中的區(qū)域劃分和資源分配問題[J].數(shù)學(xué)的實踐與認識，2007，37（14）：16?24.

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

[3] 胡興雨，張學(xué)義，吳俊，等.移動Ad Hoc網(wǎng)絡(luò)拓撲結(jié)構(gòu)抗毀性測度模型[J].計算機工程與應(yīng)用，2011（2）：78?80.

[4] 盧曉珊，賀永金，何偉，等.Ad Hoc網(wǎng)絡(luò)中的區(qū)域劃分和資源分配研究[J].數(shù)學(xué)的實踐與認識，2009，39（8）：53?60.

[5] 徐武，雷劍，陶紅亮.Ad Hoc網(wǎng)絡(luò)中的覆蓋和互聯(lián)問題研究[J].景德鎮(zhèn)高專學(xué)報，2009（2）：29?30.

[6] 任治國.Ad Hoc網(wǎng)絡(luò)中的區(qū)域劃分和資源分配問題[J].咸寧學(xué)院學(xué)報，2012，32（6）：44?46.

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

[8] 余旭濤，張在琛，畢光國.一種Ad Hoc網(wǎng)絡(luò)可靠性度量：網(wǎng)絡(luò)均衡度[J].應(yīng)用科學(xué)學(xué)報，2005，23（6）：582?585.

[9] 田方，劉福杰，常義林.無線Ad Hoc網(wǎng)絡(luò)關(guān)鍵技術(shù)研究[J].計算機與網(wǎng)絡(luò)，2002（20）：50?52.

[10] 王華，薛濤，崔云平，等.Ad Hoc網(wǎng)絡(luò)技術(shù)[J].硅谷，2012（17）：9?10.