吴之南，杨鑫，凌力

一种基于城市机会网络的网络服务模型及定位算法

吴之南，杨鑫，凌力

提出了一种在城市道路场景下应用的互联网访问服务模型。不同于传统接入方式，该模型不要求用户与互联网接入点建立直接连接，它允许用户通过城市中的机会网络间接地访问互联网。同时还提出了一种应用于该模型的定位算法。经过仿真分析，证明该算法可以在保证网络服务质量的基础上减少接入点数目并降低网络数据冗余。仿真结果还表明无线网络接入点的选取与网络中节点的数目对算法性能有显著影响。

机会网络；网络服务；定位算法；道路网格；

0 引言

机会网络是一种以“存储-携带-转发”模式为特征的自组网。不同于传统网络，机会网络不要求源节点与目标节点之间有完整链路，它通过节点在空间上的移动来寻找机会从原网络中带走数据并带入新网络[1]。

随着具备无线通信能力的终端的普及以及包括蓝牙4.0，ZigBee等无线自组网相关标准的成熟，拥有大量无线移动设备的城市正渐渐变成应用机会网络的典型场景，每一个携带移动终端的行人和交通工具都是城市机会网络中的节点。人们可以在不直接连接互联网（Internet）的情况下，利用周围的其它节点来间接地与互联网进行通信。要做到高效通信，除了高效的路由算法[2]，有效而准确地对节点定位可以大大提高数据与指定节点的相遇概率，提高转发效率，从而降低网络冗余，提升网络服务的整体性能。而城市中规律的道路交通网格也为定位节点提供了有利条件。杨卫东等人提出过一种此类场景的节点移动模型[3]。城市中的节点往往还具有社交性，在Schurgot M.R.的文章中[4]，我们看到关于社交性在容迟网络路由中的应用已成为一大研究热点。

本文将提出一种基于此类网络服务模型的定位算法并且通过模拟一种特殊的城市场景对算法进行仿真分析。

1 通过机会网络访问互联网

这部分将说明定位算法所基于的网络服务。首先，将介绍城市机会网络场景。其次，将介绍单一用户利用城市机会网络访问互联网的服务模型。

1.1 城市机会网络

基于机会网络的各类服务需要一定数量的节点才能比较高效。而要通过机会网络访问互联网还要求网络中包含可以连接互联网的接入点（AccessPoint）。拥有大量移动设备和基础网络设施的城市道路网格场景就基本具备了应用此类服务的所有基本条件。此外，城市中的各类法规和机制有效限制了城市中各类节点的行为模式，包括运动方向，速度甚至分布概率等。这让我们能够对节点进行分类，而每类节点拥有相同的行为模式。比如行人，车辆等。这大大简化了对节点定位和预测的难度，也简化了模拟场景的难度。

在此基础上，本文提出了一种特定的城市场景，即校园场景。它是一种简化了的城市场景，但保留了城市场景的主要特征。下文的仿真分析就是基于这种场景的。在这种场景中我们假设只有行人这一类节点，时速v为1.5米每秒。两行人节点每次相向接触可以产生的通信量D如公式（1）：

式中VD为数据传输速率，L为自组网的网络覆盖范围，t 为自组网建立时间。若取L为100米，t 为60毫秒，VD为250kbit/s，则每次接触可以传输30M左右的数据。

1.2 网络服务模型

当前作为主流无线上网技术之一的WiFi以IEEE 802.11系列协议为基础，通过终端与WiFi热点（AP）的直接连接来将用户接入互联网。在机会网络中，用户可以通过各种转发机制来发出服务请求，利用机会网络中的其它节点将请求数据转发给公共热点。返回数据时，则可以将数据转发给离用户最近的热点，再利用热点附近的机会网络转发给请求服务的用户。步骤如图1所示：

图1 服务模型示意图

在本文中，以节点为源，AP为目标的链路被称为上行链路；而以AP为源，节点为目标的链路被称为下行链路。由于机会网络的拓扑结构与用户的地理位置在不断变化，上述服务模型要求在数据下行过程中对请求服务的用户的地理位置做出预测，这正是本文所提出的算法要解决的问题。

2 算法设计

本文提出的算法是一种基于节点位置历史的算法。在某用户发出网络服务请求后，每次与机会网络中的其它节点相遇时，会向这些节点广播自身的位置信息和设备ID，而接收节点会由此生成一条记录并在记录中加上当前时刻的时间戳，然后记录在本地的定位记录队列上，这样接收信息的节点就携带了请求服务的用户的位置信息。在本文提出的服务模型中，由于每个节点都可以请求服务，因此，所有节点都是其它节点和自身的位置信息的携带者。此外，每当节点进入城市场景中所布置的热点的有效范围，就将自身的定位记录队列上传至互联网上的定位记录服务器，在上传信息得到确认后，节点将清空本地记录队列以节省本地存储空间。而定位记录服务器将根据各热点不定时上传的定位记录来更新存有所有节点位置信息的位置信息表。同时，定位记录服务器还会维护一张热点位置信息表，在向某目标用户转发下行数据时，服务器可以通过热点位置信息表找出离该目标用户的最新位置最近的热点，然后，向此热点转发下行数据，再由此热点向附近的所有机会网络节点广播数据，以期它们将数据携带转发给目标用户。这样可以避免向所有热点泛洪广播。节点算法和热点算法流程图如图2所示：

图2 节点算法流程图 热点算法流程图

3 分析方法

本文采用设置特定场景，利用Eclipse软件编写Java程序模拟的方法来分析该算法在场景中的性能。在本部分，首先，需要确定算法性能的度量指标。然后，将介绍本仿真采用的节点移动模型。最后，给出仿真场景的具体设置。

3.1 度量值

本文选取了以下3个指标来比较分析定位算法的性能。

1）平均传输时延

平均传输时延是在一段时间内，服务器上某节点最新位置所在的定位记录的时间戳和当前时间的差值的平均值，它描述了整个网络服务模型所掌握的位置信息的实时性和数据在下行过程中的时延性，也从侧面衡量了算法的准确性。该指标不包括首次传输时延。

2）首次传输时延

首次传输时延是用户发出网络服务请求后，位于网络中的定位记录服务器得到该请求所需的时间，这也是服务器首次获得该用户节点的位置信息的时间。它主要描述了本文提出的网络服务中的数据在上行过程中的时延性。

3）定位命中率

定位命中率是指在某时刻，实际离用户节点最近的热点和通过本算法预测的离该用户节点最近的热点相符的概率。它直接刻画了算法的预测准确性，是最重要的性能度量指标。

3.2 节点移动模型

本仿真在参考了RWP（Random Waypoint）和SPMBM（Shortest Path Map-Based Movement）节点移动模型后，提出了一套基于本次仿真场景的特定模型。该模型随机生成目标位置坐标，同一类节点以固定速度沿道路移动，直至到达下一个路口。当节点到达路口后以一预设概率随机决定下一步移动至哪个路口或者在本路口滞留，预设概率基于实际场景中的每个路口的实际人流情况。此外还假设所有节点在到达路口后不会立刻返回上一个路口。

3.3 仿真场景

本次仿真模拟校园这一特殊的城市场景。在该校园场景中只有行人这一类节点，各节点不会离开仿真场景所规定的范围，也不会消失。场景中的热点全部设置在路口。总共选取3组热点，每组4个。前两组按照将整个校园纵横分别分割为三均分和四均分的分割线交点来选取，取离交点最近的路口。而第三组则选取校园中人流量最高的4个路口作为热点。校园场景如图3所示：

图3 高人流量路口分布

三组点的选取如图4、图5所示：

图4 三均分近似路口分布

图5 四均分近似路口分布

本文还选取了节点数量（包括用户节点）分别为10、20、30、40的4组情况，这样与3组热点构成了12组仿真场景。每组进行多次仿真，取各次仿真结果的平均值作为该组仿真的仿真结果。仿真中只有一个用户节点，并假设该节点本身不具备和热点连接的能力即它必须依赖其他节点的转发来实现和互联网的数据交换，而其余节点都为转发节点，不会发出服务请求。

其它场景设置如表1所示：

表1 仿真场景设置

4 仿真结果分析

4.1 平均传输时延

如图6所示：

图6 平均传输延时

由图6可见，高人流量组有最小的平均传输时延。四均分组的平均传输时延较长，相比另两组有显著差别。各组平均传输时延随着节点数的增加而减小。三均分组的优异表现可能得益于该组热点的选取靠近场景中心高人流量区域。

4.2 首次传输时延

如图7所示：

图7 首次传输延时

由图7可见，四均分组的首次传输时延较长，但与另两组的差距随节点数增加而显著减小。首次传输时延在节点数从10增加到20时会显著减小，但之后与节点数的相关性明显减弱，这说明了首次传输时延具有很大的随机性，它与服务请求用户的路线和各节点的分布有关。

4.3 定位命中率

如图8所示：

图8 定位命中率

由图8可见，高人流量组有最高的定位命中率。各组定位命中率都随节点数的增加而提高。各组的命中率都高于25%，即高于随机选择热点策略下的定位命中率。

5 总结

本文提出了一种新型的网络服务模型，并且研究了基于该模型的定位算法，经过对仿真结果的仔细分析得出以下结论：（1）相较于在场景中均匀的布置网络热点，选取人流量高的地方布置热点可以提高定位算法的性能；（2）本文提出的网络模型及定位算法的性能会随网络中节点数量的增加而提高；（3）在节点较少的网络中，本文提出的网络模型及定位算法也能够达到较好的性能。

机会网络应用的主要困难之一在于难以找到典型的应用场景及服务。本文提出的服务模型及场景为机会网络的应用提供了一种新思路。

[1]熊永平,孙利民,牛建伟,等.机会网络[JJ].软件学报,,2009.20(1):1244-137.

[2]孙践知,刘乃瑞,张迎新,等.机会网络典型路由算法性能分析[J].计算机工程,2011.37(16)):86-89.

[3]杨卫东,朱红松,张德贤,等.车载容迟网络中一种基于真实轨迹的车辆移动模型[[J].计算机研究与发展,,2010.47(z2), 2770-274.

[4]Schhurgot M.R., CComaniciu Cristina, Jaffres-RRunser K.,“Beeyond traditionnal DTN routiing: social nettworks for oppportunistic commmunication”[JJ].IEEE Commmunications Maagazine,2012,500(7):155-162.

A Network Service Model and Localization Algorithm Based on Opportunistic Network of City

Wu Zhinan, Yang Xin, Ling li
(College of Information Science and Engineering, Fudan University, Shanghai 200433, China)

This paper presents a network service model based on urban roads scene. Different from traditional direct access methods, the model allows users to access the Internet indirectly by the opportunistic network in city. This paper also presents a localization algorithm based on this model.Performance evaluation shows that this algorithm can reduce the number of access points and the data redundancy in the systemwith an acceptable service performance. The result also shows the location of wireless network access point and the amount of nodes in the scene have significant impact on localization algorithm.

Opportunistic Network; Network Service; Localization Algorithm; Road Grid

TP393

A

20014.12.07)

1007-757X(2015)03-0012-03

吴之南（1991-），男，上海，复旦大学通信科学与工程系，硕士研究生，研究方向：网络与数据通信；上海，200433

杨 鑫（1990-），男，浙江，复旦大学通信科学与工程系，硕士研究生，研究方向：物联网信息处理；上海，200433

凌 力（1967-），男，浙江，复旦大学通信科学与工程系，副教授，研究方向：网络与数据通信；上海，200433