基于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平台上的运行情况，没有考虑节点的移动会对网络图谱结构造成的影响。因此，下一个目标考虑当节点有规律运动时对网络的影响。