WSN協(xié)議matlab編程教程-無線傳感器網(wǎng)絡(luò)路由協(xié)議

ID:288219 · 發(fā)表于 2018-3-6 15:16

一、Leach協(xié)議與NS的關(guān)系

二、算法設(shè)計(jì)思想

三、簇頭建立算法流程圖

四、難點(diǎn)解決

五、算法運(yùn)行結(jié)果分析

參考文獻(xiàn)

一、Leach協(xié)議與NS的關(guān)系

為了實(shí)現(xiàn)leach 協(xié)議，對(duì)ns進(jìn)行擴(kuò)展。在ns中增加了一個(gè)事件驅(qū)動(dòng)模擬器支持模擬無線傳感器網(wǎng)絡(luò)協(xié)議。這些擴(kuò)展包括MAC協(xié)議，用于計(jì)算和交互的能量分配模型和leach協(xié)議的體系結(jié)構(gòu)。

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以通過簡(jiǎn)單的Nodes, Links, Agents和Applications 描述。Nodes相當(dāng)于網(wǎng)絡(luò)中的終端主機(jī)， Links 是用于Nodes交互的連接器, Agent用來實(shí)現(xiàn)不同網(wǎng)絡(luò)協(xié)議，是支持分組產(chǎn)生和丟棄的節(jié)點(diǎn)。Applications用來產(chǎn)生數(shù)據(jù)和實(shí)現(xiàn)不同的應(yīng)用函數(shù)。一旦網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)建立起來后，模擬通過啟動(dòng)節(jié)點(diǎn)上的Applications運(yùn)行。

為了在ns中支持無線傳感器網(wǎng)絡(luò)，在ns中增加了 mobile nodes, MAC協(xié)議和信道傳播模型Channel 。

Applications類的頭文件用Tcl語言寫的，節(jié)點(diǎn)中的其他函數(shù)功能用C++語言寫成的。

數(shù)據(jù)包的發(fā)送過程：

Applications創(chuàng)建數(shù)據(jù)包（data packets）,然后發(fā)送給Agent. Agent執(zhí)行協(xié)議棧中運(yùn)輸層和網(wǎng)絡(luò)層的功能，將數(shù)據(jù)包發(fā)送給CMUTrace,。CMUTrace將packets的統(tǒng)計(jì)數(shù)據(jù)寫到trace 文件，然后將packets發(fā)至Connector。Connector將數(shù)據(jù)包傳送給用于數(shù)據(jù)鏈路處理的鏈路層(LL).經(jīng)過一小段時(shí)間的延遲后，數(shù)據(jù)包由LL發(fā)送給Queue緩沖隊(duì)列。如果是還沒有傳送過的數(shù)據(jù)包，Queue將以隊(duì)列進(jìn)行存儲(chǔ)。然后Queue將數(shù)據(jù)包出隊(duì)列，發(fā)送到MAC層。然后開始運(yùn)行MAC（媒體訪問控制）協(xié)議。最終，packets被發(fā)送到網(wǎng)絡(luò)接口層(Network Interface),網(wǎng)絡(luò)接口層將packets加上正確的傳輸能量，然后將packets發(fā)送到Channel. Channel將packets進(jìn)行拷貝，并發(fā)往連接信道的每一個(gè)節(jié)點(diǎn)。

發(fā)送過程可參考如下圖1

數(shù)據(jù)包的接收過程：

數(shù)據(jù)包被節(jié)點(diǎn)的網(wǎng)絡(luò)接口接收，并被向上傳送至MAC層，Link-Layer, Connector, CMUTrace, 和Agent 函數(shù). Agent 對(duì)數(shù)據(jù)包進(jìn)行判定，并將數(shù)據(jù)包到達(dá)的信息通知給Application.

接收過程與發(fā)送過程傳輸?shù)穆窂较喾础?/font>

二、算法設(shè)計(jì)思想

Leach協(xié)議跨越幾個(gè)層次實(shí)現(xiàn)的協(xié)議，Leachapp應(yīng)用在最高層Application。它是自適應(yīng)分簇拓?fù)渌惴āＶ芷趫?zhí)行，每輪循環(huán)分為簇頭的建立階段和穩(wěn)定的數(shù)據(jù)通信階段。

（1）簇頭建立階段：初始階段，每個(gè)節(jié)點(diǎn)從0和1中隨機(jī)產(chǎn)生一個(gè)數(shù)，如果這個(gè)數(shù)小于閥值T（n），該節(jié)點(diǎn)就成為當(dāng)前輪的簇頭。

其中，P是期望的簇頭數(shù)在所有節(jié)點(diǎn)中占的百分比，r是選舉輪數(shù)，r mod (1/p)代表這一輪循環(huán)中當(dāng)選過簇頭的節(jié)點(diǎn)個(gè)數(shù)，G是這一輪循環(huán)中未當(dāng)選過簇頭的節(jié)點(diǎn)集合。

每個(gè)節(jié)點(diǎn)自主選擇是否成為當(dāng)前輪的簇頭并通過廣播的形式報(bào)告給其他節(jié)點(diǎn)。簇頭通過CSMA MAC協(xié)議進(jìn)行廣播，所有的簇頭以相同的傳輸能量進(jìn)行廣播。

簇頭建立起來之后，每個(gè)非簇頭節(jié)點(diǎn)要決定在當(dāng)前輪中自己屬于哪個(gè)簇頭。非簇頭節(jié)點(diǎn)根據(jù)收到的廣播信號(hào)強(qiáng)度決定加入哪個(gè)簇頭。非簇頭節(jié)點(diǎn)決定了自己屬于哪個(gè)簇頭后，必須通知簇頭節(jié)點(diǎn)它是該簇的成員。非簇頭節(jié)點(diǎn)同樣通過CSMA MAC協(xié)議將自己加入該簇的信息報(bào)告給簇頭節(jié)點(diǎn)。

簇頭節(jié)點(diǎn)收到所有的非簇頭節(jié)點(diǎn)加入的信息后，基于本簇內(nèi)加入的節(jié)點(diǎn)數(shù)目創(chuàng)建TDMA調(diào)度，通知每個(gè)節(jié)點(diǎn)什么時(shí)間可以傳輸數(shù)據(jù)。

在leach協(xié)議中，具體通過calculatePi()函數(shù)計(jì)算門限值thresh.

double LeachApp::calculatePi()

{

register int n = config_.numberNodes_; //節(jié)點(diǎn)個(gè)數(shù)

register int k = config_.desiredClusters_; //期望簇頭數(shù)

double thresh; //閥值

if (hasBeenClusterHead())

thresh = 0; //已經(jīng)是簇頭，本輪中不再成為簇頭

else if (n - k * round_ < 1)

thresh = 1; //將節(jié)點(diǎn)設(shè)置為簇頭

else

thresh = (double) k / (n - k * round_);

return thresh;

}

（2）數(shù)據(jù)傳輸階段：

一個(gè)簇內(nèi)的信息傳輸會(huì)影響相鄰簇。為了減少這種信號(hào)干擾，各個(gè)簇內(nèi)的信息交互通過不同的CDMA編碼。簇頭可以決定本簇中節(jié)點(diǎn)所用的CDMA編碼。這個(gè)用于當(dāng)前階段的CDMA編碼在廣播簇頭的時(shí)候發(fā)送給簇內(nèi)節(jié)點(diǎn)。具體在advertiseClusterHead()中實(shí)現(xiàn)。

此外，簇頭根據(jù)本簇內(nèi)的節(jié)點(diǎn)個(gè)數(shù)創(chuàng)建TDMA調(diào)度。具體的，簇頭在findBestCluster()函數(shù)中調(diào)用createSchedule()，而由createSchedule()函數(shù)具體創(chuàng)建TDMA調(diào)度。

當(dāng)簇內(nèi)節(jié)點(diǎn)收到這個(gè)消息后，它們會(huì)在各自的時(shí)間槽內(nèi)發(fā)送數(shù)據(jù)。簇頭節(jié)點(diǎn)收到所有的數(shù)據(jù)后執(zhí)行信號(hào)處理函數(shù)壓縮數(shù)據(jù)為一個(gè)信號(hào)，并將這個(gè)合成的信號(hào)發(fā)給基站。

三、簇頭建立算法流程圖

簇頭的建立是在decideClusterHead()函數(shù)實(shí)現(xiàn)。具體流程圖如圖1

圖1 簇頭建立算法流程圖

四、難點(diǎn)解決

1. CDMA編碼問題

Leach協(xié)議中不同簇內(nèi)用不同的CDMA編碼，同一個(gè)簇內(nèi)采用同一個(gè)CDMA編碼進(jìn)行數(shù)據(jù)傳輸。如果以各個(gè)簇頭為結(jié)點(diǎn)，建立完全圖。為了使各個(gè)簇采用不同的編碼，利用PCA邊著色。

所謂PCA邊著色問題，指在完全圖中給節(jié)點(diǎn)的每條鄰接邊分配不同的碼。每個(gè)節(jié)點(diǎn)用一個(gè)碼在其鄰接邊（即鏈路）上進(jìn)行發(fā)送或接收數(shù)據(jù)。

以下，圖2是PCA著色問題的一個(gè)示例。

圖2 PCA邊著色示意圖

如果記PCA需要的最大可用碼數(shù)為：＃（PCA）

根據(jù)圖論知識(shí)：

＃（PCA）<=2⊿-1 ，其中⊿指圖中節(jié)點(diǎn)的最大度數(shù)

例如：在圖2中，節(jié)點(diǎn)的最大度數(shù)為6，故⊿為6

在leach協(xié)議中，假定期望的簇頭數(shù)為n，再加上匯聚節(jié)點(diǎn)，所以，節(jié)點(diǎn)的最大度數(shù)⊿為（n＋1）。因此，

＃（PCA）<=2(n＋1)－1=2n+1

在leachApp.cc程序中，簇頭建立后，簇頭決定本簇內(nèi)的CDMA編碼。這是在廣播簇頭時(shí)確定的，即advertiseClusterHead()函數(shù)中。

numCodesAvail = 2 * config_.spreading_ - 1; //計(jì)算最大可用碼

clusterCode = (mac_->myADVnum() % numCodesAvail) + 1; //設(shè)置CDMA編碼

在leachApp.cc程序中，struct leachConfig中對(duì)desiredClusters_（期望的簇頭數(shù)）和config_.spreading進(jìn)行了定義。

在initializeConfig()函數(shù)中語句：

config_.spreading_ = config_.desiredClusters_ + 1

在LeachApp的構(gòu)造函數(shù)LeachApp(int nNodes, int nClusters, double maxDist) 中語句：config_.desiredClusters_ = nClusters

在TCL腳本中

set val(n_common) 10 //普通節(jié)點(diǎn)個(gè)數(shù)可任意設(shè)置，此處設(shè)為10

set val(n_ch) 0 //簇頭數(shù)初始值為0

set val(n_ch) [expr int($val(n_common) * 2 / 10)] //對(duì)期望的簇頭數(shù)進(jìn)行了設(shè)置，為普通節(jié)點(diǎn)個(gè)數(shù)的20％（即上式中的 2/10）

因此，可以計(jì)算得出numCodesAvail

在mac-sensor.h中，

int myADVnum_; // 收到的廣播消息，即鄰近的簇頭節(jié)點(diǎn)的個(gè)數(shù)

inline int & myADVnum() { return myADVnum_; }

myADVnum()是在MAC層中計(jì)算求得。啟動(dòng)運(yùn)行后，計(jì)算每個(gè)簇頭的鄰近簇頭發(fā)來的ADV。

因此，可求得clusterCode

2. TDMA調(diào)度

在findBestCluster()函數(shù)中，當(dāng)判定節(jié)點(diǎn)是簇頭節(jié)點(diǎn)時(shí)需要createScheduler。在createScheduler函數(shù)中，如果簇內(nèi)節(jié)點(diǎn)不空，就需要?jiǎng)?chuàng)建TDMA時(shí)分復(fù)用幀。

frameTime 表示該簇頭節(jié)點(diǎn)分配的一個(gè)時(shí)間幀；

clusterNodes_.size() 表示一個(gè)簇內(nèi)的節(jié)點(diǎn)個(gè)數(shù)

config_.ssSlotTime_ 表示一個(gè)時(shí)間幀內(nèi)的小的時(shí)隙

lstRndDelay 表示緩沖時(shí)間

xmitTime_ 表示簇內(nèi)所有節(jié)點(diǎn)的數(shù)據(jù)發(fā)送時(shí)間

createScheduler函數(shù)主要語句如下：

frameTime_ = (5 + clusterNodes_.size()) * config_.ssSlotTime_; //計(jì)算時(shí)間幀

lstRndDelay_ = Random::uniform(0, 0.01); //隨機(jī)選取緩沖時(shí)間

xmitTime_ = config_.ssSlotTime_ * (clusterNodes_.size()) + lstRndDelay_;

Scheduler::instance().schedule(

eventHandler_,

new LeachEvent(&LeachApp::sendDataToBS),

xmitTime_);

3. clearClusterChoices()

由于各個(gè)簇頭形成和建立起來的時(shí)間不同，而簇頭建立起來后需要廣播ADV, 通知其他節(jié)點(diǎn)加入。簇頭廣播的ADV會(huì)被網(wǎng)絡(luò)中的所有節(jié)點(diǎn)接收到，即簇頭和普通節(jié)點(diǎn)都能收到先建立起來的簇頭發(fā)來的ADV。普通節(jié)點(diǎn)收到簇頭發(fā)來的通知包后都會(huì)將該數(shù)據(jù)包加入自己的一個(gè)接收隊(duì)列。對(duì)后來建立起來的簇頭來說，一旦自己成為簇頭，就會(huì)刪除其他簇頭發(fā)來的廣播包；對(duì)沒有成為簇頭的普通節(jié)點(diǎn)來說，需要出接收的簇頭隊(duì)列中選出一個(gè)距離最近的簇頭加入，然后刪除接收隊(duì)列中的廣播包。

在decideClusterHead()函數(shù)中，當(dāng)節(jié)點(diǎn)成為簇頭后，需要執(zhí)行clearClusterChoices(), 函數(shù)clearClusterChoices()主要語句如下：

for (CHs::iterator it = clusterChoices_.begin(); it != clusterChoices_.end(); it++)

{

chadv element = (chadv) *it;

if (element.object != NULL)

delete element.object;

}

而普通節(jié)點(diǎn)則需要在findBestCluster()中找到最優(yōu)簇頭（即距離最近的簇頭）后，執(zhí)行clearClusterChoices()

4. 一些定義

（1）virtual double TxTime(int n) { return n * 8.0 / 1000000.0; }

TxTime指以1 Mbps的速度傳輸n bit數(shù)據(jù)所需要的時(shí)間

（2） double lstRndDelay_; // 上次隨機(jī)延遲時(shí)間

int currentCH_; //當(dāng)前簇頭

int currentCHMAC_; //當(dāng)前簇頭所用的MAC協(xié)議

bool listenADV_; // 是否收聽ADV

bool listenJOINREQ_; // 是否監(jiān)聽加入請(qǐng)求

五、算法運(yùn)行結(jié)果分析

1．場(chǎng)景介紹

用ns模擬每個(gè)節(jié)點(diǎn)向基站傳輸數(shù)據(jù)

Basic Configuration:

圖3 Basic Configuration配置圖

Access Point:

圖4 Access Point配置圖

Common Node:

圖5 Common Node配置圖

輸出得到TCL文件。在ns環(huán)境下運(yùn)行該TCL文件，得到trace文件。

2. trace 文件分析

trace的功能是詳細(xì)記錄模擬的過程，可以根據(jù)用戶的需要記錄模擬過程中的任何一個(gè)細(xì)節(jié)。所有對(duì)模擬的分析是基于trace文件。截取一部分文件代碼如下：

s -t 0.007580973 -Hs 1 -Hd -2 -Ni 1 -Nx 48.64 -Ny 86.26 -Nz 0.00 -Ne 10.000000 -Nl AGT -Nw --- -Ma 0 -Md 1000000 -Ms 0 -Mt 0 -Is 1.0 -Id -1.0 -It rca -Il 4 -If 0 -Ii 0 -Iv 32

r -t 0.007580973 -Hs 1 -Hd -2 -Ni 1 -Nx 48.64 -Ny 86.26 -Nz 0.00 -Ne 10.000000 -Nl RTR -Nw --- -Ma 0 -Md 1000000 -Ms 0 -Mt 0 -Is 1.0 -Id -1.0 -It rca -Il 4 -If 0 -Ii 0 -Iv 32

s -t 0.007580973 -Hs 1 -Hd -2 -Ni 1 -Nx 48.64 -Ny 86.26 -Nz 0.00 -Ne 10.000000 -Nl RTR -Nw --- -Ma 0 -Md 1000000 -Ms 0 -Mt 0 -Is 1.0 -Id -1.0 -It rca -Il 4 -If 0 -Ii 0 -Iv 32

在文件分析中主要用到t, Ni, Ne這幾個(gè)數(shù)據(jù)。其中，t 后面的數(shù)字代表時(shí)間，Ni后面的數(shù)字代表節(jié)點(diǎn)ID，Ne后面的數(shù)字代表節(jié)點(diǎn)能量

使用語言gwak, 繪圖工具gnuplot. 上述場(chǎng)景中生成的trace文件名為：trace.tr

去掉所有以N開頭的行數(shù)，該行為統(tǒng)計(jì)數(shù)據(jù)，得到文件trace1.tr

單個(gè)節(jié)點(diǎn)能量變化統(tǒng)計(jì)：

以節(jié)點(diǎn)1為例,提取所有Ni等于1的節(jié)點(diǎn)的時(shí)間和相應(yīng)能量，存入文件1.txt.

在gawk環(huán)境中，輸入代碼如下：

gawk ‘$9==/1/{print $3,$17}’trace1.tr >1.txt

得到統(tǒng)計(jì)數(shù)據(jù)如下：

0.007580973 10.000000

0.007605973 10.000000

2.461346376 9.963363

2.461371376 9.963363

3.536372973 9.945803

3.536397973 9.945803

在gnuplot環(huán)境中輸入：

gnuplot ‘1.txt’ using 1:2

得到的能量變化圖如下圖所示：

圖6 節(jié)點(diǎn)1能量變化圖

(2) 工作節(jié)點(diǎn)能量統(tǒng)計(jì)：

從trace.tr文件中提取普通節(jié)點(diǎn)的數(shù)據(jù)。

gawk ‘$1~/N/ { print $3,$5,&7 }’ trace.tr >n.txt //第3列代表時(shí)間，第5列代表節(jié)點(diǎn)ID，第7列代表能量值

gawk ‘$2!=0 { print $1,$3}’n.txt >2.txt //去掉sink節(jié)點(diǎn)，sink節(jié)點(diǎn)ID為0

再從2.txt中進(jìn)行能量統(tǒng)計(jì)，統(tǒng)計(jì)時(shí)間間隔為0.5秒

gawk ‘{ if($1<0.5) sum+=$2 };

END { print sum }’ 2.txt >3.txt

gawk ‘{ if($1<1.0) sum+=$2 };