改進(jìn)APIT節(jié)點(diǎn)定位系統(tǒng)軟件軟件文檔

1、改進(jìn)apit節(jié)點(diǎn)定位系統(tǒng)軟件v1.0軟件文檔中國(guó)礦業(yè)大學(xué)2011年2月目 錄1 運(yùn)行環(huán)境12 改進(jìn)apit節(jié)點(diǎn)定位算法12.1 apit原理12.2 apit步驟12.3 網(wǎng)格掃描法22.4 apit的改進(jìn)42.4.1 引入計(jì)數(shù)器對(duì)apit算法進(jìn)行改進(jìn)52.4.2 擴(kuò)大鄰居節(jié)點(diǎn)的定義范圍52.4.3 迭代思想（unknown-to-anchor）52.5 改進(jìn)apit定位算法流程52.6 基于改進(jìn)apit算法的重心掃描法73 改進(jìn)apit節(jié)點(diǎn)定位算法仿真平臺(tái)83.1 真實(shí)事件在仿真中的特殊處理93.1.1 節(jié)點(diǎn)的真實(shí)坐標(biāo)與估計(jì)坐標(biāo)93.1.2 分布式算法在單機(jī)上的實(shí)現(xiàn)93.1.3 節(jié)點(diǎn)通信機(jī)制

2、103.1.4 接收信號(hào)強(qiáng)度的表示103.2 核心數(shù)據(jù)結(jié)構(gòu)104 軟件模塊設(shè)計(jì)124.1 文檔模塊134.2 顯示模塊134.3 控制模塊144.4 關(guān)鍵算法實(shí)現(xiàn)函數(shù)：165 軟件使用說(shuō)明185.1“顯示模塊”操作說(shuō)明185.2 節(jié)點(diǎn)操作185.3 “場(chǎng)景模式”操作195.4 “操作模式選擇”操作205.5 “定位步驟”操作206 技術(shù)支持221 運(yùn)行環(huán)境硬件環(huán)境：windows xp及后續(xù)windows操作系統(tǒng)上，硬件配置要求pentium 4以上cpu，512m以上內(nèi)存，80g以上硬盤(pán)。軟件環(huán)境：microsoft visual c+ 6.0。2 改進(jìn)apit節(jié)點(diǎn)定位算法2.1 apit原

3、理apit利用網(wǎng)絡(luò)中相對(duì)較高的節(jié)點(diǎn)密度來(lái)模擬節(jié)點(diǎn)移動(dòng)，利用無(wú)線(xiàn)信號(hào)的傳播特性來(lái)判斷是否遠(yuǎn)離或靠近錨節(jié)點(diǎn)，通常在給定方向上，一個(gè)節(jié)點(diǎn)距離另一個(gè)節(jié)點(diǎn)越遠(yuǎn)，接收到的信號(hào)就越弱。鄰居節(jié)點(diǎn) 通過(guò)交換各自接收到信號(hào)的強(qiáng)度，判斷距離某一信標(biāo)節(jié)點(diǎn) 的遠(yuǎn)近，從而模仿pit中節(jié)點(diǎn)移動(dòng)。apit理論：如果m節(jié)點(diǎn)不存在同時(shí)遠(yuǎn)離或接近于a，b，c的鄰居節(jié)點(diǎn)，則判定m位于abc內(nèi)部，否則的話(huà)，判定m位于abc外部。2.2 apit步驟apit定位具體步驟：收集信息：未知節(jié)點(diǎn)收集鄰居錨節(jié)點(diǎn)的信息，如位置、標(biāo)識(shí)號(hào)、接收到的信號(hào)強(qiáng)度等等，鄰居節(jié)點(diǎn)之間交換各自接收到的信標(biāo)節(jié)點(diǎn)的信息；apit：測(cè)試未知節(jié)點(diǎn)是否在不同的信標(biāo)節(jié)點(diǎn)組成

4、的三角形內(nèi)部；計(jì)算重疊區(qū)域：統(tǒng)計(jì)包含未知節(jié)點(diǎn)的三角形，計(jì)算所有三角形的重疊區(qū)域；計(jì)算未知節(jié)點(diǎn)位置：計(jì)算重疊區(qū)域的質(zhì)心位置，作為未知節(jié)點(diǎn)的位置。圖1是apit節(jié)點(diǎn)定位算法流程圖：圖1 apit節(jié)點(diǎn)定位算法流程圖2.3 網(wǎng)格掃描法網(wǎng)格掃描算法是傳統(tǒng)的apit的定位方法。對(duì)于每一個(gè)參考節(jié)點(diǎn)，根據(jù)檢測(cè)到的錨節(jié)點(diǎn)，采取不同的組合三角形，進(jìn)行定位，判斷節(jié)點(diǎn)在三角形的內(nèi)部還是三角形的外部，然后不斷重疊節(jié)點(diǎn)在三角形內(nèi)的區(qū)域，區(qū)域會(huì)越來(lái)越窄，最后逼近到一個(gè)相對(duì)很小的區(qū)域，再取這個(gè)圖形的質(zhì)心作為未知節(jié)點(diǎn)的估計(jì)位置。圖2 網(wǎng)格掃描法原理示意圖在圖2中，我們把這個(gè)偵聽(tīng)區(qū)域劃分成許多網(wǎng)格，網(wǎng)格陣列代表節(jié)點(diǎn)可能存在的最大

5、區(qū)域，每個(gè)網(wǎng)格的初始值為0。如果判斷出節(jié)點(diǎn)在三角形內(nèi)，相應(yīng)的三角形所在的網(wǎng)格區(qū)域的值加1；同樣，如果判斷出節(jié)點(diǎn)在三角形外，相應(yīng)的三角形所在的網(wǎng)格區(qū)域的值減1。網(wǎng)格掃描算法的流程圖如圖3所示：圖3 網(wǎng)格掃描算法流程圖2.4 apit的改進(jìn)從定位精度角度講，apit定位流程又可以分為兩大階段：第一階段是每個(gè)未知節(jié)點(diǎn)通過(guò)錨節(jié)點(diǎn)和未知節(jié)點(diǎn)廣播消息來(lái)收集周?chē)粗?jié)點(diǎn)和錨節(jié)點(diǎn)的信息，然后通過(guò)apit測(cè)試來(lái)建立自己的支持?jǐn)?shù)據(jù)集；第二階段是調(diào)用相應(yīng)的掃描算法來(lái)對(duì)支持?jǐn)?shù)據(jù)集進(jìn)行掃描，并最終獲得待定位節(jié)點(diǎn)的估計(jì)位置坐標(biāo)。第一階段，支持?jǐn)?shù)據(jù)集的純度主要取決于apit測(cè)試算法；第二階段，最終定位精度與掃描算法和int

6、oout錯(cuò)誤與outtoin錯(cuò)誤直接相關(guān)。為了提高最終的定位精度，我們通過(guò)對(duì)apit測(cè)試算法或掃描算法尋求相關(guān)的改進(jìn)或是創(chuàng)新來(lái)實(shí)現(xiàn)。2.4.1 引入計(jì)數(shù)器對(duì)apit算法進(jìn)行改進(jìn)關(guān)于apit定位算法的性能改進(jìn)主要是從apit算法的兩種錯(cuò)誤和節(jié)點(diǎn)定位數(shù)目的兩個(gè)方面出發(fā)考慮的我們將其命名為改進(jìn)的apit定位算法。.對(duì)于解決apit定位算法固有的兩種錯(cuò)誤：intoout錯(cuò)誤和outtoin錯(cuò)誤，提出了在節(jié)點(diǎn)內(nèi)部設(shè)置計(jì)數(shù)器的方法來(lái)盡量降低兩種錯(cuò)誤產(chǎn)生的概率，具體做法是：在節(jié)點(diǎn)內(nèi)部設(shè)置兩個(gè)計(jì)數(shù)器countera和counterb,對(duì)于一組錨節(jié)點(diǎn)組成的三角形，根據(jù)鄰居節(jié)點(diǎn)的信標(biāo)交換，運(yùn)用apit定位思想進(jìn)行

7、判決，如果根據(jù)接收信號(hào)強(qiáng)度ss判決未知節(jié)點(diǎn)在錨節(jié)點(diǎn)組成的這個(gè)三角形內(nèi)部的鄰居節(jié)點(diǎn)的數(shù)目是m，計(jì)數(shù)器countera等于m;如果判決未知節(jié)點(diǎn)在錨節(jié)點(diǎn)組成的這個(gè)三角形外部的鄰居節(jié)點(diǎn)的數(shù)目是n，計(jì)數(shù)器counterb等于n;如果mn,則我們認(rèn)為未知節(jié)點(diǎn)在這三個(gè)錨節(jié)點(diǎn)組成的三角形的內(nèi)部。然后采用相同的方法窮盡未知節(jié)點(diǎn)的所有錨節(jié)點(diǎn)組成的三角形區(qū)域。2.4.2 擴(kuò)大鄰居節(jié)點(diǎn)的定義范圍通常apit算法中所指的鄰居節(jié)點(diǎn)僅僅是指與待定位節(jié)點(diǎn)鄰近的普通節(jié)點(diǎn)，而不包括與待定位節(jié)點(diǎn)鄰近的錨節(jié)點(diǎn)。這就意味著錨節(jié)點(diǎn)只是負(fù)責(zé)發(fā)送自己的位置信息以及id值，而不需要記錄周?chē)ㄐ欧秶鷥?nèi)的錨節(jié)點(diǎn)的相關(guān)信息。這樣，待定位節(jié)點(diǎn)只能與周

8、圍的其他待定位節(jié)點(diǎn)交換信息，即：鄰居節(jié)點(diǎn)的范圍被限定為未知節(jié)點(diǎn)。然而，實(shí)際上從apit測(cè)試的定義來(lái)看，只要錨節(jié)點(diǎn)存儲(chǔ)了當(dāng)前要進(jìn)行測(cè)試的三角形區(qū)域的三個(gè)錨節(jié)點(diǎn)的信息，就完全有資格作為待定位節(jié)點(diǎn)的鄰居節(jié)點(diǎn)參與測(cè)試。當(dāng)然，前提是該錨節(jié)點(diǎn)并非當(dāng)前三角形區(qū)域的頂點(diǎn)之一。因此，錨節(jié)點(diǎn)除了可以作為參考節(jié)點(diǎn)提供位置參考以外，還可以作為apit測(cè)試階段的鄰居節(jié)點(diǎn)，用以向待定位節(jié)點(diǎn)提供其他錨節(jié)點(diǎn)的信號(hào)強(qiáng)度信息。2.4.3 迭代思想（unknown-to-anchor）為了使未知節(jié)點(diǎn)定位數(shù)據(jù)這個(gè)性能參數(shù)得到提高，我們引入了迭代的思想來(lái)考慮問(wèn)題，未知節(jié)點(diǎn)在通過(guò)定位算法獲得位置坐標(biāo)以后，晉升錨節(jié)點(diǎn)，向周?chē)従庸?jié)點(diǎn)廣播位

9、置信息并記錄周?chē)ㄐ欧秶鷥?nèi)的錨節(jié)點(diǎn)的相關(guān)信息。由于未知節(jié)點(diǎn)通過(guò)算法定位本省就存在誤差，在晉升為錨節(jié)點(diǎn)之后可能造成誤差的累積。為了不讓“滾雪球”現(xiàn)象再重演，使得定位精度可以得到一定的保障，我們?cè)O(shè)計(jì)未知節(jié)點(diǎn)晉升為錨節(jié)點(diǎn)是只充當(dāng)一次錨節(jié)點(diǎn)的較色，廣播一次自身的位置信息，然后退出定位過(guò)程，進(jìn)入休眠狀態(tài)，來(lái)保留剩余能量。2.5 改進(jìn)apit定位算法流程改進(jìn)apit定位算法流程如圖4所示：圖4 改進(jìn)apit定位算法流程2.6 基于改進(jìn)apit算法的重心掃描法三角形重心掃描算法步驟如下：假設(shè)m節(jié)點(diǎn)從對(duì)c個(gè)三角形區(qū)域中得到了k個(gè)有效的三角形區(qū)域。則依次求出這k個(gè)三角形區(qū)域的重心坐標(biāo)(x,y),(x,y。獲得k

10、個(gè)重心坐標(biāo)后，繼續(xù)從這k個(gè)重心坐標(biāo)中三個(gè)點(diǎn)一組組成新的一個(gè)三角形區(qū)域集合,如果k不能整除3的話(huà)，則剩下的1個(gè)或2個(gè)重心坐標(biāo)直接保留，進(jìn)入下一輪循環(huán)。這時(shí)，集合中三角形的個(gè)數(shù)為k%3個(gè)。再次對(duì)得到的k%3個(gè)三角形區(qū)域重復(fù)以上操作。最后，會(huì)得到1個(gè)或者2個(gè)坐標(biāo)值。如果是1個(gè)坐標(biāo)值的話(huà)，則直接將該坐標(biāo)值作為估計(jì)坐標(biāo)；如果是2個(gè)坐標(biāo)值的話(huà)，將這兩個(gè)坐標(biāo)值的平均值作為估計(jì)坐標(biāo)。三角形重心掃描算法的流程圖如圖5所示：圖5三角形重心掃描算法流程圖3 改進(jìn)apit節(jié)點(diǎn)定位算法仿真平臺(tái)ad-hoc無(wú)線(xiàn)傳感器網(wǎng)絡(luò)發(fā)展迅速，各種網(wǎng)絡(luò)方案和協(xié)議日趨復(fù)雜，網(wǎng)絡(luò)規(guī)模日趨龐大，對(duì)網(wǎng)絡(luò)研究人員而言，掌握網(wǎng)絡(luò)仿真的重要性不言而

11、喻。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)仿真能夠在一個(gè)可控制的環(huán)境里研究其應(yīng)用,包括操作系統(tǒng)和網(wǎng)絡(luò)協(xié)議棧,能夠仿真數(shù)量眾多的節(jié)點(diǎn),能夠觀(guān)察由不可預(yù)測(cè)的干擾和噪聲引起的難以琢磨的節(jié)點(diǎn)間的相互作用,獲取節(jié)點(diǎn)間詳細(xì)的細(xì)節(jié),從而提高節(jié)點(diǎn)投放后的網(wǎng)絡(luò)成功率,減少投放后的網(wǎng)絡(luò)維護(hù)工作。 目前，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)常用仿真工具有ns2、opnet、omnet+。為了驗(yàn)證和演示改進(jìn)apit定位算法的有效性，本設(shè)計(jì)用vc開(kāi)發(fā)了一個(gè)改進(jìn)apit節(jié)點(diǎn)定位算法專(zhuān)用仿真平臺(tái)。它能夠運(yùn)行apit定位算法并對(duì)其進(jìn)行演示。通過(guò)對(duì)仿真結(jié)果的分析，我們可以驗(yàn)證apit定位算法的有效性，并在相關(guān)的細(xì)節(jié)尋求改進(jìn)。平臺(tái)基于mfc開(kāi)發(fā)，使用了單文檔視圖結(jié)構(gòu)。3.1

12、 真實(shí)事件在仿真中的特殊處理在對(duì)網(wǎng)絡(luò)進(jìn)行仿真設(shè)計(jì)的時(shí)候，常需要對(duì)客觀(guān)世界中的一些物質(zhì)和事件進(jìn)行抽象化處理。例如，點(diǎn)到點(diǎn)的鏈路通常抽象表示為一個(gè)由帶寬和延時(shí)組成的隊(duì)列;而成幀(framing)、編碼、調(diào)制、傳輸過(guò)程中的差錯(cuò)則會(huì)用簡(jiǎn)單的數(shù)學(xué)模型表示，甚至忽略不計(jì)。另一方面，某些客觀(guān)存在的未知參數(shù)卻又要在建立仿真模型的過(guò)程中事先給定，這就成了一個(gè)悖論:如何事先給定將要求解的參數(shù)？由于我們仿真的對(duì)象是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)，而實(shí)驗(yàn)平臺(tái)僅僅是一臺(tái)計(jì)算機(jī)。因此，如何將無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的真實(shí)事件抽象成計(jì)算機(jī)語(yǔ)言，成為設(shè)計(jì)平臺(tái)時(shí)遇到的一大難題。下面將一一說(shuō)明對(duì)這些難題的解決方案。3.1.1 節(jié)點(diǎn)的真實(shí)坐標(biāo)與估計(jì)坐標(biāo)無(wú)

13、線(xiàn)傳感器網(wǎng)絡(luò)中總共有兩類(lèi)節(jié)點(diǎn)，錨節(jié)點(diǎn)和未知節(jié)點(diǎn)。錨節(jié)點(diǎn)的位置已知，而未知節(jié)點(diǎn)位置未知。我們定位的目的正是為了確定未知節(jié)點(diǎn)的估計(jì)坐標(biāo)。然而，仿真中，如果我們不知道未知節(jié)點(diǎn)的坐標(biāo)值，下面幾個(gè)工作都無(wú)法進(jìn)行：(1) 如何在顯示界面中對(duì)未知節(jié)點(diǎn)進(jìn)行顯示。(2) 如何計(jì)算未知節(jié)點(diǎn)接收信號(hào)強(qiáng)度值？(3) 如何知道未知節(jié)點(diǎn)是否在某錨節(jié)點(diǎn)的通信范圍內(nèi)？第一項(xiàng)工作是節(jié)點(diǎn)實(shí)時(shí)顯示的前提；第二項(xiàng)工作是apit算法中進(jìn)行apit測(cè)試的關(guān)鍵前提；第三項(xiàng)工作是節(jié)點(diǎn)廣播的前提。如果無(wú)法滿(mǎn)足這三個(gè)前提的話(huà)，那么仿真便無(wú)法進(jìn)行。為了解決上述問(wèn)題，我們引入了節(jié)點(diǎn)的真實(shí)坐標(biāo)與估計(jì)坐標(biāo)這兩個(gè)概念。由于任何一個(gè)節(jié)點(diǎn)的坐標(biāo)值都是客觀(guān)存在

14、的，這個(gè)客觀(guān)存在值，我們稱(chēng)為節(jié)點(diǎn)的真實(shí)坐標(biāo)。然而，對(duì)于未知節(jié)點(diǎn)來(lái)說(shuō)，其客觀(guān)存在值，在節(jié)點(diǎn)未完成定位前，對(duì)觀(guān)察者來(lái)說(shuō)是不可見(jiàn)的。定位的目的正是為了向觀(guān)察者報(bào)告這個(gè)客觀(guān)值的估計(jì)值，我們稱(chēng)之為節(jié)點(diǎn)的估計(jì)坐標(biāo)。由于錨節(jié)點(diǎn)本身坐標(biāo)已知，不需要進(jìn)行定位。因此，為了方便處理，我們假設(shè)其真實(shí)坐標(biāo)與估計(jì)坐標(biāo)一致。而對(duì)于未知節(jié)點(diǎn)來(lái)說(shuō)，在定位前，其真實(shí)坐標(biāo)是存在的但是不可見(jiàn)的，其估計(jì)坐標(biāo)值是不可知的。為了方便處理，在本平臺(tái)中，我們將其初始值設(shè)為(0,0)。3.1.2 分布式算法在單機(jī)上的實(shí)現(xiàn)每個(gè)傳感器節(jié)點(diǎn)都是一個(gè)微型化的嵌入式系統(tǒng)，多個(gè)節(jié)點(diǎn)可以并發(fā)的進(jìn)行操作;而該仿真平臺(tái)運(yùn)行于單機(jī)上，若要仿真多個(gè)節(jié)點(diǎn)，只能以輪循的

15、方式讓每個(gè)節(jié)點(diǎn)執(zhí)行各自的任務(wù)，節(jié)點(diǎn)間存在同步的問(wèn)題，雖然可以以每個(gè)節(jié)點(diǎn)一個(gè)線(xiàn)程的方式運(yùn)行，仍無(wú)法從根本上解決問(wèn)題。對(duì)此尚無(wú)好的解決方案，我們只能讓每個(gè)節(jié)點(diǎn)作為一個(gè)節(jié)點(diǎn)類(lèi)的實(shí)例，運(yùn)行各自的方法，節(jié)點(diǎn)實(shí)例間通過(guò)消息機(jī)制來(lái)模擬節(jié)點(diǎn)間通信。3.1.3 節(jié)點(diǎn)通信機(jī)制在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)間的通信均是通過(guò)廣播實(shí)現(xiàn)的。然而，在仿真中去實(shí)現(xiàn)節(jié)點(diǎn)廣播機(jī)制卻并不容易。廣播信息的發(fā)送與接送在軟件中的實(shí)現(xiàn)都需要仔細(xì)考慮，用恰當(dāng)?shù)挠?jì)算機(jī)語(yǔ)言去描述并實(shí)現(xiàn)。在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，分布式的節(jié)點(diǎn)雖然各自獨(dú)立，但是，它們所要進(jìn)行的工作基本上都是一樣的。如果對(duì)每個(gè)節(jié)點(diǎn)都創(chuàng)建一個(gè)線(xiàn)程，去模擬它們的并行工作狀態(tài)，在資源有限的單機(jī)上并不

16、現(xiàn)實(shí)。我們可以考慮設(shè)立一個(gè)全局的管理者，由其負(fù)責(zé)對(duì)所有的節(jié)點(diǎn)進(jìn)行廣播消息，接收消息。在本軟件平臺(tái)中，所有的節(jié)點(diǎn)信息均是存在文檔類(lèi)對(duì)象的一個(gè)cobarray數(shù)組中。因此，由文檔類(lèi)對(duì)象實(shí)例來(lái)?yè)?dān)當(dāng)此管理者最為恰當(dāng)。由于網(wǎng)絡(luò)中所有節(jié)點(diǎn)均需要廣播消息，因此，本平臺(tái)中我們?cè)O(shè)計(jì)由全局管理者去負(fù)責(zé)激發(fā)各節(jié)點(diǎn)發(fā)送消息。在收發(fā)消息時(shí)，由于廣播消息是面向所有節(jié)點(diǎn)的，所以，我們也設(shè)計(jì)由全局管理者負(fù)責(zé)每個(gè)節(jié)點(diǎn)的消息收發(fā)工作。我們利用了mfc的消息機(jī)制，在消息發(fā)送時(shí)，由節(jié)點(diǎn)調(diào)用sendmessage將信息發(fā)送給文檔類(lèi)對(duì)象(實(shí)際上消息是發(fā)給顯示窗口，然后再在顯示窗口中調(diào)用文檔類(lèi)對(duì)象進(jìn)行處理)。文檔類(lèi)對(duì)象在消息響應(yīng)函數(shù)對(duì)該消

17、息進(jìn)行處理。對(duì)廣播消息的處理主要是根據(jù)發(fā)送節(jié)點(diǎn)的類(lèi)型，來(lái)更新接收節(jié)點(diǎn)的鄰居節(jié)點(diǎn)以及參考節(jié)點(diǎn)的信息。具體原理見(jiàn)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。3.1.4 接收信號(hào)強(qiáng)度的表示在進(jìn)行apit測(cè)試時(shí)，待定位節(jié)點(diǎn)要與鄰居節(jié)點(diǎn)通過(guò)交換從相同的三個(gè)參考節(jié)點(diǎn)接收到的信號(hào)強(qiáng)度值來(lái)作出是否位于三角形外部的判斷。那么，如何在仿真平臺(tái)中去表示節(jié)點(diǎn)所接收到的信號(hào)強(qiáng)度呢？通過(guò)上一章對(duì)apit算法的介紹我們知道，apit是基于信號(hào)強(qiáng)度在傳播過(guò)程中單調(diào)減小的這樣一個(gè)前提。也就是說(shuō)，信號(hào)強(qiáng)度值與信號(hào)傳播距離應(yīng)該成反比。而對(duì)于編程者來(lái)說(shuō)，任何一個(gè)節(jié)點(diǎn)的真實(shí)坐標(biāo)都是已知的，所以，利用兩個(gè)節(jié)點(diǎn)間的真實(shí)距離的相關(guān)函數(shù)去表示接收信號(hào)強(qiáng)度是可取的。我們可

18、以采用一個(gè)特定值與兩點(diǎn)真實(shí)距離的商來(lái)表示接收節(jié)點(diǎn)所接收到的信號(hào)強(qiáng)度。本軟件中，這個(gè)特定值設(shè)為20000. 即：對(duì)于相距為100的兩個(gè)節(jié)點(diǎn)來(lái)說(shuō)，接收節(jié)點(diǎn)所接收到的信號(hào)強(qiáng)度值為200.3.2 核心數(shù)據(jù)結(jié)構(gòu)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的核心是節(jié)點(diǎn)。因此，如何用計(jì)算機(jī)語(yǔ)言描述一個(gè)節(jié)點(diǎn)的信息是設(shè)計(jì)本軟件平臺(tái)的一個(gè)關(guān)鍵。本軟件平臺(tái)中，節(jié)點(diǎn)類(lèi)只負(fù)責(zé)儲(chǔ)存定位所需的數(shù)據(jù)信息、定位結(jié)果和操作接口。定位算法的具體實(shí)現(xiàn)并不作為節(jié)點(diǎn)類(lèi)的成員函數(shù)。class cnode: public cobjectdeclare_serial(cnode) /串行化存儲(chǔ)宏public:cnode();cnode(cpoint real,bool m

19、_isanchor,int id);/重載構(gòu)造函數(shù)virtual cnode();void cnode:assertvalid() const;virtual void serialize(carchive& ar);/串行化儲(chǔ)存private: /私有屬性值int m_id;/節(jié)點(diǎn)id號(hào)nodetype m_type;/節(jié)點(diǎn)類(lèi)型cpoint m_estimate2;/通過(guò)兩種種不同算法得到的坐標(biāo)估計(jì)值cpoint m_real;/節(jié)點(diǎn)真實(shí)坐標(biāo)int m_range;/節(jié)點(diǎn)通信半徑;public: /公有屬性值：public:cobarray m_apit_area2; /經(jīng)改進(jìn)的apit測(cè)試

20、后得到的所在三角形區(qū)域集,作為網(wǎng)格掃描和計(jì)算的參數(shù)area1用來(lái)存儲(chǔ)原算法的結(jié)果area2用來(lái)存儲(chǔ)改進(jìn)后的結(jié)果 int intoout2;/二維數(shù)組用來(lái)存儲(chǔ)兩種不同算法出現(xiàn)intoout的錯(cuò)誤數(shù)int outtoin2;/索引對(duì)關(guān)系為：0:改進(jìn)的apit算法，1：原始apit算法bool isoriginaltested;/標(biāo)識(shí)是否已經(jīng)采用原始apit算法進(jìn)行過(guò)一輪測(cè)試bool iscumttested;/標(biāo)識(shí)是否已經(jīng)采用改進(jìn)的apit算法進(jìn)行過(guò)一輪apit測(cè)試carray m_ref_array; /存儲(chǔ)參考節(jié)點(diǎn)idcarray m_neighbor_array;/存儲(chǔ)鄰居節(jié)點(diǎn)idpubli

21、c:/訪(fǎng)問(wèn)接口int getid(void) const;int getrange(void) const;cpoint getreal(void) const;cpoint getestimate(int index) const;nodetype gettype(void) const;/操作接口/1.普通設(shè)置接口void settype(nodetype type);void setestimate(cpoint estimate,int index);void setrange(int range);void setreal(cpoint pt);/更改節(jié)點(diǎn)真實(shí)坐標(biāo)/2.擴(kuò)展操作int

22、 count_distance(cnode* pnode) ; /計(jì)算任意兩個(gè)id節(jié)點(diǎn)的真實(shí)距離(原理見(jiàn)論文)int count_strength(cnode* pnode) ; /計(jì)算所接收到的信號(hào)強(qiáng)度，可設(shè)為反比于距離int count_distance(cpoint& pt) const;/計(jì)算至某定點(diǎn)的距離int getneighborarrayindex(int n_id); /由id判斷是否已經(jīng)加入鄰居節(jié)點(diǎn),并返回所在索引值,若不在，則返回-1;int getrefarrayindex(int n_id); /由id判斷是否已經(jīng)加入?yún)⒖脊?jié)點(diǎn),并返回所在索引值,若不在，則返回-1;b

23、ool isinrefarray(int id);/判斷是否位于參考節(jié)點(diǎn)內(nèi)bool isinneighborarray(int id);/判斷是否位于鄰居節(jié)點(diǎn)內(nèi)void flushapitarea();/更新場(chǎng)景數(shù)據(jù)時(shí)用來(lái)清除原測(cè)試數(shù)據(jù)結(jié)果bool isintriangle(cpoint& pt1,cpoint& pt2,cpoint& pt3);/判斷節(jié)點(diǎn)真實(shí)坐標(biāo)是否位于指定三角形內(nèi)，在計(jì)算intoout以及outtoin時(shí)被調(diào)用；nodetype是一個(gè)枚舉類(lèi)型，定義如下：enum nodetypeanchor=0,/錨節(jié)點(diǎn)uncertain,/未定位節(jié)點(diǎn)novalid,/不可定位節(jié)點(diǎn)rou

24、ter/保留值;capitarea類(lèi)是用來(lái)存儲(chǔ)節(jié)點(diǎn)完成apit測(cè)試后所得到的三角形區(qū)域集合，其定義如下：class capitarea: public cobject declare_serial(capitarea)public:capitarea();capitarea(cpoint p1,cpoint p2,cpoint p3);virtual capitarea(); virtual void serialize(carchive& ar);cpoint pt1;cpoint pt2;cpoint pt3;cobarray和carray是mfc提供的動(dòng)態(tài)數(shù)組類(lèi)，前者可以?xún)?chǔ)存從cobje

25、ct類(lèi)派生的對(duì)象指針，支持串行化存儲(chǔ)。carray是普通數(shù)組類(lèi),僅支持一般類(lèi)型。詳細(xì)說(shuō)明見(jiàn)msdn。4 軟件模塊設(shè)計(jì)仿真平臺(tái)主要分為三個(gè)模塊，一個(gè)是用來(lái)儲(chǔ)存場(chǎng)景節(jié)點(diǎn)數(shù)據(jù)的文檔模塊，其對(duì)應(yīng)單文檔視圖結(jié)構(gòu)中的文檔類(lèi)；一個(gè)是用來(lái)控制仿真流程的控制板模塊；一個(gè)是顯示模塊，負(fù)責(zé)實(shí)時(shí)顯示當(dāng)前場(chǎng)景，并可對(duì)算法進(jìn)行相應(yīng)的演示。軟件的界面效果如圖6所示：圖6 軟件運(yùn)行界面4.1 文檔模塊作為對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的全局管理者，文檔模塊負(fù)責(zé)存儲(chǔ)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的指針，場(chǎng)景大小，當(dāng)前活動(dòng)節(jié)點(diǎn)id，并負(fù)責(zé)為新創(chuàng)建的節(jié)點(diǎn)分配一個(gè)唯一id。為了防止用戶(hù)重復(fù)添加相同節(jié)點(diǎn)，文檔類(lèi)模塊還要負(fù)責(zé)判斷所要添加的新節(jié)點(diǎn)是否已經(jīng)存在。為了方便用戶(hù)

26、重復(fù)利用特定場(chǎng)景數(shù)據(jù)進(jìn)行仿真，文檔模塊除了負(fù)責(zé)在程序運(yùn)行期間維護(hù)所有仿真數(shù)據(jù)以外，還要負(fù)責(zé)在用戶(hù)關(guān)閉程序時(shí)將當(dāng)前仿真場(chǎng)景數(shù)據(jù)以文件的形式存存儲(chǔ)至硬盤(pán)。文檔模塊存儲(chǔ)的對(duì)象由程序員指定。本軟件中，我們只將場(chǎng)景中的節(jié)點(diǎn)id，真實(shí)坐標(biāo)，通信范圍，估計(jì)坐標(biāo)值以及當(dāng)前添加節(jié)點(diǎn)數(shù)存儲(chǔ)至文件中。文件保存類(lèi)型為 .api 格式。4.2 顯示模塊顯示模塊負(fù)責(zé)為用戶(hù)顯示當(dāng)前仿真場(chǎng)景中的節(jié)點(diǎn)，坐標(biāo)等，并允許用戶(hù)通過(guò)鼠標(biāo)方式動(dòng)態(tài)添加節(jié)點(diǎn)。由于可能出現(xiàn)屏幕區(qū)域小于場(chǎng)景的情況，而導(dǎo)致用戶(hù)無(wú)法在當(dāng)前窗口范圍外添加節(jié)點(diǎn)，我們?cè)O(shè)定顯示模塊capitview類(lèi)直接從cscrollview類(lèi)派生，支持窗口橫向及縱向滾動(dòng)。由于仿真結(jié)果

27、與坐標(biāo)系無(wú)關(guān)，所以為了便于實(shí)現(xiàn)，顯示模塊采用的邏輯坐標(biāo)系為wm_text映射方式，即以客戶(hù)區(qū)左上角為原點(diǎn)，向下y增大，向右x增大。坐標(biāo)單位為一個(gè)像素，與設(shè)備坐標(biāo)系相同。顯示模塊界面如下圖所示：圖7 顯示模塊界面未知節(jié)點(diǎn)用黑色圓形區(qū)域標(biāo)記，錨節(jié)點(diǎn)用紅色圓形區(qū)域標(biāo)記。首次添加的節(jié)點(diǎn)的填充區(qū)域較其他節(jié)點(diǎn)大。當(dāng)鼠標(biāo)進(jìn)入到顯示模塊上方時(shí)，狀態(tài)欄會(huì)實(shí)時(shí)顯示鼠標(biāo)當(dāng)前所在的邏輯坐標(biāo)。上圖中的黑色框線(xiàn)是用來(lái)標(biāo)識(shí)當(dāng)前場(chǎng)景區(qū)域。用戶(hù)添加節(jié)點(diǎn)時(shí)，只需要在想要添加節(jié)點(diǎn)的位置用左鍵單擊一下，然后再單擊右鍵，選擇彈出菜單中的“添加至錨節(jié)點(diǎn)”或“添加至未知節(jié)點(diǎn)”便可實(shí)現(xiàn)節(jié)點(diǎn)的添加。由于可能出現(xiàn)當(dāng)前視圖大小不能夠完全顯示場(chǎng)景的

28、情況，所以，本軟件中設(shè)置了兩種顯示模式：普通模式和完整模式。在普通模式下，可以實(shí)現(xiàn)添加節(jié)點(diǎn)、拖動(dòng)節(jié)點(diǎn)、動(dòng)態(tài)顯示當(dāng)前鼠標(biāo)所在邏輯坐標(biāo)以及繪圖顯示等功能。但其顯示范圍受限于當(dāng)前窗口大小，用戶(hù)可能無(wú)法完整查看場(chǎng)景。在完整模式下，當(dāng)前視圖可以通過(guò)壓縮顯示比例，以將當(dāng)前仿真場(chǎng)景全部完整顯示出來(lái)。這樣可以方便用戶(hù)查看當(dāng)前場(chǎng)景中節(jié)點(diǎn)布置情況。需要注意的是，在完整模式下，普通模式下的一切與鼠標(biāo)有關(guān)的功能都被屏蔽。為了方便用戶(hù)添加節(jié)點(diǎn)，本顯示模塊增加了拖動(dòng)功能。用戶(hù)可以將鼠標(biāo)置于節(jié)點(diǎn)上方時(shí)，鼠標(biāo)光標(biāo)形狀會(huì)改變。用戶(hù)如果摁下左鍵，然后在顯示區(qū)域拖動(dòng)鼠標(biāo)，再至一個(gè)新的位置點(diǎn)松開(kāi)左鍵，便可以實(shí)現(xiàn)將原節(jié)點(diǎn)移動(dòng)到新位置。

29、需要注意的是，當(dāng)用戶(hù)移動(dòng)一個(gè)節(jié)點(diǎn)時(shí)，會(huì)導(dǎo)致除未知節(jié)點(diǎn)的估計(jì)坐標(biāo)以外的全部數(shù)據(jù)復(fù)位，以開(kāi)始新的仿真測(cè)試。另外，如果鼠標(biāo)移動(dòng)的位置超出了當(dāng)前的場(chǎng)景范圍，則程序會(huì)鎖定當(dāng)前鼠標(biāo)至合法的場(chǎng)景區(qū)域。4.3 控制模塊控制模塊主要完成以下三大功能：一是方便用戶(hù)對(duì)定位流程進(jìn)行控制，進(jìn)而加深用戶(hù)對(duì)apit算法的定位流程的了解。二是提供給用戶(hù)設(shè)置當(dāng)前仿真場(chǎng)景以及仿真模式的選擇。三是負(fù)責(zé)將當(dāng)前場(chǎng)景中的節(jié)點(diǎn)信息歸類(lèi)顯示到控制窗口的三個(gè)列表框當(dāng)中。它們分別是：錨節(jié)點(diǎn)，待定位節(jié)點(diǎn)以及已定位節(jié)點(diǎn)?？刂颇K如圖8所示：圖8 控制模塊界面當(dāng)用戶(hù)選中三個(gè)列表框中的某個(gè)節(jié)點(diǎn)時(shí)，程序會(huì)在控制模塊的另一個(gè)列表框內(nèi)顯示當(dāng)前選中節(jié)點(diǎn)的節(jié)點(diǎn)信

30、息。用戶(hù)單擊節(jié)點(diǎn)列表中某條內(nèi)容時(shí)，程序會(huì)彈出一個(gè)對(duì)該節(jié)點(diǎn)進(jìn)行重新設(shè)置的對(duì)話(huà)框，如圖9所示：圖9 設(shè)置對(duì)話(huà)框界面在該對(duì)話(huà)框中，可以對(duì)選中的節(jié)點(diǎn)進(jìn)行修改節(jié)點(diǎn)的真實(shí)坐標(biāo)，通信范圍。如果需要的話(huà)，還可以刪除當(dāng)前節(jié)點(diǎn)。場(chǎng)景大小也可以在此重設(shè)。需要注意的是，任何對(duì)當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)的改變都會(huì)導(dǎo)致程序?qū)⒊粗?jié)點(diǎn)的估計(jì)坐標(biāo)以外的全部數(shù)據(jù)復(fù)位，以開(kāi)始新的仿真測(cè)試。為了方便用戶(hù)操作，該對(duì)話(huà)框還可以一下同時(shí)重設(shè)所有錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的通信范圍。這在進(jìn)行對(duì)比仿真時(shí)比較方便。為了滿(mǎn)足用戶(hù)不同的要求，本程序設(shè)定了兩種操作模式供用戶(hù)選擇，一種是單節(jié)點(diǎn)操作模式，一種是集體操作模式。用戶(hù)通過(guò)勾選復(fù)選框來(lái)確定自己的選擇。在單節(jié)點(diǎn)操作

31、模式下，只有”錨節(jié)點(diǎn)廣播消息”和”尋找鄰居節(jié)點(diǎn)”這兩項(xiàng)操作是針對(duì)場(chǎng)景中所有的節(jié)點(diǎn)?！盿pit內(nèi)點(diǎn)測(cè)試”以及”apit區(qū)域標(biāo)記按鈕”以及”估計(jì)位置”這三個(gè)操作都是只針對(duì)當(dāng)前未知節(jié)點(diǎn)。在集體操作模式下，除”apit區(qū)域標(biāo)記”這項(xiàng)操作以外，所有的操作都是針對(duì)所有的未知節(jié)點(diǎn)。設(shè)定這兩種模式的出發(fā)點(diǎn)在于：有些用戶(hù)只需要快速獲得最后定位結(jié)果，對(duì)定位流程并不關(guān)心。4.4 關(guān)鍵算法實(shí)現(xiàn)函數(shù)：利用apit算法實(shí)現(xiàn)定位的核心步驟總共有三步:第一步就是通過(guò)錨節(jié)點(diǎn)以及未知節(jié)點(diǎn)廣播消息來(lái)更新各節(jié)點(diǎn)的鄰居節(jié)點(diǎn)以及參考節(jié)點(diǎn)。第二步就是利用各節(jié)點(diǎn)的鄰居節(jié)點(diǎn)以及參考節(jié)點(diǎn)信息進(jìn)行apit測(cè)試，更新每個(gè)節(jié)點(diǎn)的apitarea數(shù)據(jù)，

32、即通過(guò)apit測(cè)試確定未知節(jié)點(diǎn)位于哪些參考節(jié)點(diǎn)組成的三角形區(qū)域內(nèi)部。第三步就基于各節(jié)點(diǎn)更新后的apitarea數(shù)據(jù)，采用網(wǎng)絡(luò)掃描算法來(lái)計(jì)算出未知節(jié)點(diǎn)的apitarea區(qū)域集的交集的中心位置，即未知節(jié)點(diǎn)的估計(jì)坐標(biāo)值；或者采用自創(chuàng)的三角形中心掃描法(詳細(xì)說(shuō)明見(jiàn))，算出未知節(jié)點(diǎn)的估計(jì)位置。這三步順序進(jìn)行，前一步為后一步提供必要的計(jì)算數(shù)據(jù)。下面，我們將以核心步驟為線(xiàn)索，對(duì)軟件中的一些關(guān)鍵算法實(shí)現(xiàn)進(jìn)行說(shuō)明。核心步驟第一步，主要通過(guò)以下兩個(gè)函數(shù)來(lái)完成廣播消息的發(fā)送。void ccontrolview:onanchorbroadcast()void ccontrolview:onneighborsearch

33、()這兩個(gè)函數(shù)分別是對(duì)控制板上的“錨節(jié)點(diǎn)廣播消息”按鈕以及“尋找鄰居節(jié)點(diǎn)”按鈕的響應(yīng)函數(shù)。在這兩個(gè)響應(yīng)函數(shù)中，均是通過(guò)獲得文檔類(lèi)對(duì)象的指針(即網(wǎng)絡(luò)節(jié)點(diǎn)的全局管理者)，然后再利用該文檔指針獲得所有錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的指針。lresult sendmessage( hwnd hwnd, / handle of destination window uint msg, / message to send wparam wparam, / first message parameter lparam lparam / second message parameter);獲得各節(jié)點(diǎn)指針后，直接調(diào)用send

34、message()函數(shù)，便實(shí)現(xiàn)了消息的廣播。對(duì)于錨節(jié)點(diǎn)來(lái)說(shuō)，其第二個(gè)參數(shù)類(lèi)型為wm_msg_anchor,對(duì)于未知節(jié)點(diǎn)來(lái)說(shuō)，其第二個(gè)參數(shù)類(lèi)型為wm_msg_neighbor。第三個(gè)參數(shù)統(tǒng)一為節(jié)點(diǎn)的指針值。wm_msg_anchor以及wm_msg_neighbor的消息響應(yīng)函數(shù)將分別由顯示視圖窗口capitview截獲并作出相應(yīng)的處理。兩個(gè)消息響應(yīng)函數(shù)分別為：lresult capitview:onmymsganchor(wparam wparam, lparam lparam)lresult capitview:onmymsgneighbor(wparam wparam, lparam lp

35、aram)上文我們有說(shuō)到，廣播消息均發(fā)送到了文檔類(lèi)對(duì)象。而這里消息卻是直接發(fā)送到了capitview窗口。我們這樣處理的原因在于mfc提供的消息機(jī)制只允許將窗口消息發(fā)送給窗口類(lèi)對(duì)象，而文檔類(lèi)對(duì)象并非窗口。所以，不得已，我們只有通過(guò)中轉(zhuǎn)的方式，先將消息發(fā)送給capitview窗口，然后，再在capitview的消息響應(yīng)函數(shù)中調(diào)用文檔類(lèi)對(duì)象來(lái)對(duì)該消息進(jìn)行處理，從而間接地實(shí)現(xiàn)了將消息發(fā)送給文檔類(lèi)對(duì)象在onmymsganchor及onmymsgneighbor函數(shù)中，均使用了循環(huán)的方式對(duì)各節(jié)點(diǎn)的鄰居節(jié)點(diǎn)以及參考節(jié)點(diǎn)信息進(jìn)行了更新。具體處理流程如下(為了說(shuō)明方便，僅以onmymsganchor為例進(jìn)行說(shuō)

36、明)：1.通過(guò)getdocument獲得文檔類(lèi)指針，然后再通過(guò)該指針獲得所存儲(chǔ)的所有節(jié)點(diǎn)的指針。2.依次對(duì)所有節(jié)點(diǎn)進(jìn)行如下判斷：a.根據(jù)ononmymsganchor()傳入的wparam參數(shù)，判斷這個(gè)消息是否是自己發(fā)出的，如果是的話(huà)，則直接退出本輪循環(huán),，否則繼續(xù)判斷。b.通過(guò)isinanchorarray()判斷發(fā)出該消息的錨節(jié)點(diǎn)id是否已經(jīng)在儲(chǔ)存本節(jié)點(diǎn)的參考節(jié)點(diǎn)id數(shù)組中，如果是的話(huà)，退出本輪循環(huán)，否則繼續(xù)判斷。c.判斷發(fā)出該消息的錨節(jié)點(diǎn)其通信范圍是否大于本節(jié)點(diǎn)距該錨節(jié)點(diǎn)的真實(shí)距離。如果小于的話(huà)，則意味著該錨節(jié)點(diǎn)的廣播消息不能到達(dá)本節(jié)點(diǎn)，直接退出本輪循環(huán)。否則，該錨節(jié)點(diǎn)的id號(hào)添加至本節(jié)

37、點(diǎn)的參考節(jié)點(diǎn)數(shù)組中去。d.完成對(duì)一個(gè)節(jié)點(diǎn)的參考節(jié)點(diǎn)信息更新，跳至a繼續(xù)判斷下一個(gè)節(jié)點(diǎn)，直至完成對(duì)所有節(jié)點(diǎn)的參考節(jié)點(diǎn)信息的更新工作。對(duì)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的更新工作的具體流程見(jiàn)代碼，本文不再贅述。核心步驟第二步，主要通過(guò)以下函數(shù)完成對(duì)節(jié)點(diǎn)的apit測(cè)試void ccontrolview:onapittest()該函數(shù)是控制窗口上的apit內(nèi)點(diǎn)測(cè)試按鈕的單擊響應(yīng)函數(shù)。該函數(shù)并無(wú)自己的實(shí)現(xiàn)代碼，只是負(fù)責(zé)彈出一個(gè)測(cè)試算法選擇對(duì)話(huà)框，然后根據(jù)用戶(hù)選擇的apit測(cè)試算法，調(diào)用相應(yīng)的測(cè)試函數(shù)進(jìn)行測(cè)試。本軟件集成了兩種apit測(cè)試算法，一種是原始apit、算法，另一種是經(jīng)過(guò)改進(jìn)的apit算法。核心步驟第三步，主要通過(guò)以下函數(shù)完成對(duì)節(jié)點(diǎn)的位置估算。void ccontrolview:onposestimate()該函數(shù)是對(duì)控制窗口類(lèi)上的”位置估算”按鈕的單擊響應(yīng)函數(shù)。它負(fù)責(zé)連續(xù)彈出兩個(gè)對(duì)話(huà)框，讓用戶(hù)進(jìn)行選擇。首先彈出的是選擇進(jìn)行坐標(biāo)估計(jì)的支持?jǐn)?shù)據(jù)對(duì)話(huà)框。用戶(hù)可以選擇通過(guò)apit原算法測(cè)試出的apitarea數(shù)據(jù)或是選擇通過(guò)改進(jìn)后的apit測(cè)試算法測(cè)出的apitarea數(shù)據(jù)。選擇好了支持?jǐn)?shù)據(jù)后，緊接著就會(huì)彈出一個(gè)選擇掃描算法的對(duì)話(huà)框。該對(duì)話(huà)框負(fù)責(zé)提示用戶(hù)選擇apit算法的網(wǎng)格掃描算法，