李瑞江

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

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

中圖分類(lèi)號(hào)： TN958?34； TP391.4 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

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

1 信道分配的著色模型

1.1 建立理論模型

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

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

目標(biāo)函數(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ù)含義解釋?zhuān)篬mrow]為第一行中一跳覆蓋區(qū)的個(gè)數(shù)；[d]為每增加一行增加覆蓋區(qū)域的高度；[nrank]為要覆蓋整個(gè)正方形所需圓的行數(shù)；[β0]為當(dāng)相交圓公共部分的面積恰好占總圓面積的[a0%]時(shí)的弦割角；[β1]為三圓共點(diǎn)弦割角的邊界值；[α]為相交弦所對(duì)圓心角的一半；[w]為受在該區(qū)域內(nèi)圓弦心距的數(shù)量控制；[ceil]為向上取整數(shù)；[a0%]為相交圓的公共部分占圓面積的比例。

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

1.2 著色模型

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

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

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

當(dāng)[a=18]時(shí)，通過(guò)計(jì)算得出需要圓的數(shù)量為64個(gè)，信道的數(shù)量為79個(gè)。此時(shí)的著色信道如圖3所示。

2 抗毀性分析

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

2.1 抗毀性算法

對(duì)抗毀性的計(jì)算需要依照一定的約束條件進(jìn)行，其具體算法見(jiàn)圖4。

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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