基于Android平臺的Ad-hoc組網研究*

顏學文，王 海，董 超

（ 陸軍工程大學 通信工程學院，江蘇 南京 210007）

0 引 言

隨著智能手機的普及，越來越多的手機將進入人們的生活環境。Android系統是目前手機的主流操作系統[1]。該系統公開免費且具有強大穩定的系統，受到了大多數用戶的青睞。隨著大量手機用戶加入蜂窩網，會對基站產生很大的依賴性，需要通過基礎設施完成大范圍的通信任務。但是，在一些特設環境中，如應急搶險、軍隊演習作戰和智能家居等環境下，通信基礎設施可能會損毀或沒有覆蓋。手機如何在這些情況下實現組網通信，保證信息和數據能夠及時有效的分享，是目前的一個重大挑戰。移動Ad-hoc網絡[2]可以在沒有中心基礎設施的情況下，實現手機之間的組網通信，實現在沒有基礎設施的區域進行組網通信，將信息及時反饋給不同的用戶。但是，如何將Ad-hoc網絡引入Android手機平臺，使Android手機可以實現無線自組織網絡，是當前一項重要的研究課題。

在Android手機平臺植入Ad-hoc網絡技術，能夠很好地解決用戶組網問題，滿足用戶隨時隨地組網通信的需求，同時減少手機接入蜂窩網的個數，緩解蜂窩網的負擔。當前，有很多Ad-hoc網絡路由協議可以幫助設備構建穩定的網絡拓撲結構，實現設備之間的通信，但是很少有在手機上實現的。本文將主要介紹Ad-hoc中的兩個先驗式路由協議BATMAN和OLSR[3]，實現將BATMAN和OLSR兩個協議在Android手機平臺上運行，同時測量兩個協議組網中多跳節點之間的延時問題，從數值結果中進行分析，得到BATMAN的性能要遠強于OLSR的結論。

1 相關工作

1.1 Android平臺

Android系統是基于linux內核開發化的一種微型操作系統。該系統一般安裝在手機、平板電腦、手持設備等便攜式設備中，是Google公司開發并公布出來，具有開源免費的優勢。在不斷的更新下，它已經變得越來越完善。Android架構主要分為四個層，從高層到低層分別是應用程序層、應用程序框架層、系統運行庫層和linux核心層[4]，如圖1所示。

圖1 Android系統架構

其中，應用程序是Android會同一系列核心應用程序包一起發布的。該應用程序包包括email客戶端、SMS短消息程序、瀏覽器、聯系人管理程序等日常使用的程序，都是采用Java編寫的。應用程序框架開發人員也可以訪問核心應用程序所使用的API框架。該應用程序的架構設計簡化了組件的重用，任何一個應用程序都可以發布它的功能塊，且任何其他的應用程序都可以使用其所發布的功能塊。系統運行庫包括程序庫和Android運行庫。程序庫包含一些C/C++庫，能被Android系統中不同的組件使用。它們通過Android應用程序框架為開發者提供服務。Android運行庫是一個核心庫，提供了Java編程語言核心庫的大多數功能。Android的核心系統服務依賴于Linux 2.6內核，包括linux特有的安全性、內存管理、進程管理、網絡協議棧和驅動模型功能。Linux內核也同時作為硬件和軟件棧之間的抽象層。

1.2 Ad-hoc網絡

Ad-hoc網絡是一種由若干終端設備自動組建的局域網絡[5]，沒有中心設備，每個終端設備都是平等的，并通過路由協議在終端運行，實現數據的轉發和多跳路由，構建穩定的網絡拓撲結構。

Ad-hoc網絡主要有以下幾個特點[6]：（1）動態變化的拓撲結構，即網絡拓撲會隨著終端設備的移動、節點的加入和退出等隨時變化；（2）無中心網絡的自組織性，只要手機端打開WiFi并調整到Ad-hoc模式，就可以在同一個SSID下自動組建Ad-hoc網絡；（3）多跳網絡的實現，超過通信范圍的兩個手機可以通過其他手機中繼實現多跳通信。

這些特性決定了Ad-hoc自組織通信技術是終端設備不依靠基礎設施實現組網通信的關鍵，但是在Android手機上卻很難實現Ad-hoc組網，因為Android系統會阻止用戶使用Ad-hoc通信模式。所以，需要對Android系統內核進行修改來支持自組網通信[7]。

2 Ad-hoc網絡路由協議：OLSR和BATMAN

2.1 OLSR協議

Optimized Link State Routing Protocol（OLSR）是一個可以收集鏈路狀態且能動態計算網絡內最佳路由的動態鏈路協議[8]，是主要用于MANET網絡（Mobile Ad hoc Network）的路由協議，是根據MANET的要求，在傳統的LS（Link State）協議的基礎上優化的路由協議。

OLSR路由協議是由IETF MANET（Mobile Ad hoc NETwork）工作組為無線移動Ad Hoc網提出的一種標準化的表驅動式優化鏈路狀態路由協議。節點之間需要周期性地交換各種控制信息，通過分布式計算來更新和建立自己的網絡拓撲圖。被鄰節點選為多點中繼站MPR（Multi-point Relay）[9]的節點需要周期性地向網絡廣播控制信息。圖2為OLSR多跳中繼圖。控制信息中包含了把它選為MPR的節點的信息（稱為MPR Selector）。只有MPR節點被用作路由選擇節點，非MPR節點不參與路由計算[10]。OLSR還利用MPR節點有效地廣播控制信息，非MPR節點不需要轉發控制信息。

圖2 OLSR多跳中繼示例

節點在從自己的一跳鄰居節點中選擇MPR時的計算原則是：節點與MPR之間必須是雙向對稱鏈路，節點發送的分組通過MPR的中繼能夠到達所有對稱的兩跳鄰居節點。如果能夠滿足這一點，那么MPR就能有效進行TC分組的轉發，同時應該使MPR的數量盡量少。

OLSR主要采用兩種控制消息分組——HELLO分組和TC（Topology Control）分組[11]。

HELLO消息用于建立一個節點的鄰居表，報文中可以包括鄰居節點的地址和本節點到鄰居節點的延遲或開銷。OLSR采用周期性地廣播HELLO分組來偵聽鄰居節點的狀態。HELLO分組只在一跳的范圍內廣播，不能被轉發。與HELLO消息相反，TC分組必須被廣播到全網。

2.2 BATMAN協議

Better Approach To Mobile Ad-hoc Networking，是多跳移動Ad-hoc網絡的先驗式路由協議[12]。路由算法是將網絡中節點之間的最佳端到端路徑的信息分配到所有參與的節點中。每個節點僅感知并維護到其他所有節點的最佳下一跳信息，因此節點并不需要局部拓撲變化的全部信息，即單一節點只維護它指向目的節點的最佳下一跳鄰居信息，而沒有到目的節點的完整路由信息。另外，基于事件的但長期有效的洪泛機制，可以防止產生矛盾的拓撲信息。長期有效是指BATMAN協議不會為了最優到目的節點的路由而調度或使用超時的網絡拓撲信息，并限制拓撲消息的數量淹沒網格（從而避免控制流量的過度開銷）。該算法旨在處理基于不可靠鏈接的網絡。

簡單來說，BATMAN協議是每個發送方節點發送消息，稱該消息為BATMAN數據包幀，其中包括原發送節點的信息（Originator Messages或OGM信息）和可選擇的HNA信息，如圖3所示。

圖3 BATMAN數據幀

該數據包幀可以告知最佳下一跳節點源節點的地址，通知相鄰節點有關它的存在。這些鄰居根據明確的規則再次轉發OGM。該規則就是將原地址信息發送給指向目的節點方向的最佳下一跳鄰居，以通知其鄰居關于該消息的原始發起者的存在等。OGM很小，典型的原始數據包大小是52 Byte。除了IP和UDP開銷外，OGM至少包含發送方的地址、一個TTL和序列號。其中，序列號可以幫助判斷一個OGM包被轉發了多少次，如圖4所示。

圖4 OMG格式

HNA信息則包含了被廣播的網絡地址和子網掩碼，即最佳下一跳鄰居的地址，如圖5所示。

圖5 HNA格式

OGM包容易受到無線鏈路質量的影響[13]，因此一個好的鏈路可以更好更快地傳播數據。所以，需要最佳下一跳路徑。OGM包通過在網絡中不斷地選擇性洪泛，告知接收數據包的節點關于其他節點的信息。當節點Y的OGM被其單跳鄰居轉發時，節點X可以通過接收它的OGM了解節點Y的存在。如果節點X具有多個鄰居，節點X可以通過其單跳鄰居中的某個節點獲得更快和更可靠的OGM數量，來判斷該鄰居是否可以選為選擇向遠方節點Y發送數據的最佳下一跳鄰居，以獲得節點X到節點Y的路徑。

3 Android手機運行OLSR和BATMAN

3.1 Android手機開啟Ad-hoc模式

由于不同Android手機內核存在差異，大部分Android設備對普通用戶并不支持Ad Hoc功能。但是，Linux內核本身是可以實現Ad Hoc功能的[14]。因此，用戶只需要先以root身份登錄手機，再用iwconfig、ifconfig網絡配置工具開啟Ad Hoc功能，就能在手機上打開Ad-hoc模式。iwconfig是一個用于Linux系統無線擴展的用戶層配置工具，可以對Android設備無線網卡的大部分參數進行配置。Ifconfig則主要是用來實現網絡IP地址的配置的。

有些Android設備，在其應用架構與Linux系統內核層次上均不支持Ad Hoc模式。對于這種Android設備（如Nexus 7等），需要先修改其系統內核，使Android手機支持Ad-hoc模式。修改內核后，可以按照之前的步驟進行網絡配置。

內核調整的詳細規則如下：

+++b/drivers/net/wireless/bcmdhd/wl_cfg80211.c

-BIT(NL80211_IFTYPE_STATION)

+BIT(NL80211_IFTYPE_STATION)|BIT(NL80211_IFTYPE_ADHOC)

通過命令行輸入#iwconfig wlan0 mode Ad-hoc essid xxx，就可以成功配置Ad-hoc網絡，再使用ifconfig配置ip地址。其中，wlan0是無線網卡設備名。在不同的設備上，網卡名可能不同。xxx為無線網絡的服務集標識，用來區分不同的網絡。互相連接的無線設備，需要具有相同的ssid。經過如上配置，Android可以以Ad-hoc模式運行。

3.2 Android手機上運行OLSR協議

通過NDK交叉編譯工具編譯olsrd源碼，生成可在安卓手機上運行的二進制文件，具體步驟如下：

（1）將olsrd源碼拷貝至ubuntu系統中，在Linux系統上安裝NDK工具，NDK工具可以直接將C/C++語言編寫的協議源代碼編譯成Android平臺上可直接運行的二進制文件和相關的配置文件。但要注意，NDK的版本必須和olsrd源碼文件的版本相比配。在olsrd源碼文件夾中有相關的編譯說明，使用NDK編譯好生成olsrd可執行二進制文件。

（2）使用adb自帶的功能將可執行文件、配置文件和相關的庫文件發送到手機上，并更改可執行文件的使用權限，使用戶可以執行。

（3）運行。在電腦端通過adb可以進入Android系統的Linux終端，通過終端，直接輸入命令運行OLSR的可執行文件，程序運行結果如圖6所示。

圖6 OLSR協議在手機上運行

3.3 Android手機上運行BATMAN協議

BATMAN協議與OLSR協議不同，不能直接通過NDK交叉編譯成Android可執行的二進制文件。BATMAN協議需要一個Linux環境系統來進行編譯和運行。所以，本文在Android手機上搭建一個ubuntu虛擬平臺，BATMAN能夠在Android系統的硬件基礎上編譯運行，并能夠使用手機的網卡進行組網通信，具體步驟如下：

（1）在手機上安裝ubuntu虛擬平臺，可以下載到能在手機上運行的ubuntu的鏡像文件，根據自己實驗所用手機的具體情況修改鏡像系統ubuntu的啟動文件，直接在手機終端上啟動ubuntu完成虛擬系統的搭建。

（2）編譯BATMAN協議，將BATMAN源碼導入Android目錄下，通過虛擬平臺進入該目錄，使用gcc工具直接編譯出可執行程序BATMAN和相應的配置文件。

（3）運行協議。編譯好后重啟手機，配置好Ad-hoc網絡，重新通過ubuntu虛擬平臺進入BATMAN協議所在的目錄，通過命令$./batmand–d3 wlan0直接運行BATMAN協議。

BATMAN在手機上成功運行，如圖7所示。

圖7 BATMAN運行在手機上運行

4 BATMAN和OLSR協議測量數值分析

Ad-hoc的兩個協議BATMAN和OLSR在實際設備中都有很強的組網通信能力。將這兩個網絡通信協議移植到Android手機上，可以使Ad-hoc網絡具有更強的實用性。通過在實際場景中的測試可以體現出兩個協議的組網通信能力。本文實驗測量所在地點為教學樓走廊，采用10部配置好兩個協議和Ad-hoc網絡的手機來進行測試工作。

測試指標是端到端的往返延時。將手機依次編號為1～10，以1號機為源節點，依次向前排開，每個手機間隔20～30 m不等，如圖8所示。測量節點1依次發送ping包到節點2、4、6、8、10的往返平均延時，如圖9所示取得了兩組數據，其中ybatman表示BATMAN運行時測量取得的實際往返延時，yolsr表示OLSR協議運行時取得的往返延時。得到原始數據后，用一個weibull函數對原始數據進行線性擬合，得到圖9中的兩條曲線。

圖8 實驗環境

圖9 端到端往返延時

曲線擬合公式推導如下。weibull函數：

其中，t表示節點數；F(t)表示往返延時；t0和m分別是兩個參數，可以通過概率統計的理論使用測量的數據來確定參數。

通過對數變換可得：

令：

則式（2）可等價于：

故根據最小二乘法，可得：

其中：

其中，ti=1,2,…,10為節點；F(ti)為每個節點對應的往返延時。通過計算可得到m和a兩個參數，就能確定F(t)曲線，得到圖9中的擬合曲線，有助于分析問題。

從圖9可以看出，端到端的延時是隨著距離的增加而變大的，這是因為距離越長，數據傳輸的時間越長。因為WiFi的覆蓋范圍有限，在遠端的節點與節點1通信需要通過中間節點中繼，這也是距離越遠延時越長的原因。此外，在一跳通信范圍內，OLSR的性能會比BATMAN的性能要強。但是，當到達兩跳及以上時，BATMAN的延時會低于OLSR。而隨著距離的增大，OLSR的延時會變得更大，性能將遠低于OLSR，這是因為BATMAN總是在尋找最佳下一跳節點，所以在整個網絡拓撲結構中，會比OLSR的性能優化得更好。

5 結 語

Android手機作為目前主流且受歡迎的一類手機，過分依賴于基礎設施，在一些特殊情況下不能很好地為用戶服務。所以，提出了在Android手機上實現Ad-hoc組網通信的方案，并在Android手機上實現了Ad-hoc網絡通信協議OLSR和BATMAN的運行，同時在組網成功后對兩個協議進行了性能分析。結果顯示，BATMAN的性能要優于OLSR。在Android手機上實現Ad-hoc組網不但擴寬了Adhoc通信技術的使用范圍，還可以在手機端非常方便地實現組網通信，構建穩定的網絡拓撲環境，在災難救援、戰場通信等環境中發揮極強的作用。當前工作中只考慮了靜態環境下Ad-hoc路由協議在Android平臺上的運行情況，沒有考慮節點的移動會對網絡圖譜結構造成的影響。因此，下一個目標考慮當節點有規律運動時對網絡的影響。