一種基于城市機(jī)會(huì)網(wǎng)絡(luò)的網(wǎng)絡(luò)服務(wù)模型及定位算法

吳之南，楊鑫，凌力

一種基于城市機(jī)會(huì)網(wǎng)絡(luò)的網(wǎng)絡(luò)服務(wù)模型及定位算法

吳之南，楊鑫，凌力

提出了一種在城市道路場(chǎng)景下應(yīng)用的互聯(lián)網(wǎng)訪(fǎng)問(wèn)服務(wù)模型。不同于傳統(tǒng)接入方式，該模型不要求用戶(hù)與互聯(lián)網(wǎng)接入點(diǎn)建立直接連接，它允許用戶(hù)通過(guò)城市中的機(jī)會(huì)網(wǎng)絡(luò)間接地訪(fǎng)問(wèn)互聯(lián)網(wǎng)。同時(shí)還提出了一種應(yīng)用于該模型的定位算法。經(jīng)過(guò)仿真分析，證明該算法可以在保證網(wǎng)絡(luò)服務(wù)質(zhì)量的基礎(chǔ)上減少接入點(diǎn)數(shù)目并降低網(wǎng)絡(luò)數(shù)據(jù)冗余。仿真結(jié)果還表明無(wú)線(xiàn)網(wǎng)絡(luò)接入點(diǎn)的選取與網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目對(duì)算法性能有顯著影響。

機(jī)會(huì)網(wǎng)絡(luò)；網(wǎng)絡(luò)服務(wù)；定位算法；道路網(wǎng)格；

0 引言

機(jī)會(huì)網(wǎng)絡(luò)是一種以“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”模式為特征的自組網(wǎng)。不同于傳統(tǒng)網(wǎng)絡(luò)，機(jī)會(huì)網(wǎng)絡(luò)不要求源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間有完整鏈路，它通過(guò)節(jié)點(diǎn)在空間上的移動(dòng)來(lái)尋找機(jī)會(huì)從原網(wǎng)絡(luò)中帶走數(shù)據(jù)并帶入新網(wǎng)絡(luò)[1]。

隨著具備無(wú)線(xiàn)通信能力的終端的普及以及包括藍(lán)牙4.0，ZigBee等無(wú)線(xiàn)自組網(wǎng)相關(guān)標(biāo)準(zhǔn)的成熟，擁有大量無(wú)線(xiàn)移動(dòng)設(shè)備的城市正漸漸變成應(yīng)用機(jī)會(huì)網(wǎng)絡(luò)的典型場(chǎng)景，每一個(gè)攜帶移動(dòng)終端的行人和交通工具都是城市機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)。人們可以在不直接連接互聯(lián)網(wǎng)（Internet）的情況下，利用周?chē)钠渌?jié)點(diǎn)來(lái)間接地與互聯(lián)網(wǎng)進(jìn)行通信。要做到高效通信，除了高效的路由算法[2]，有效而準(zhǔn)確地對(duì)節(jié)點(diǎn)定位可以大大提高數(shù)據(jù)與指定節(jié)點(diǎn)的相遇概率，提高轉(zhuǎn)發(fā)效率，從而降低網(wǎng)絡(luò)冗余，提升網(wǎng)絡(luò)服務(wù)的整體性能。而城市中規(guī)律的道路交通網(wǎng)格也為定位節(jié)點(diǎn)提供了有利條件。楊衛(wèi)東等人提出過(guò)一種此類(lèi)場(chǎng)景的節(jié)點(diǎn)移動(dòng)模型[3]。城市中的節(jié)點(diǎn)往往還具有社交性，在Schurgot M.R.的文章中[4]，我們看到關(guān)于社交性在容遲網(wǎng)絡(luò)路由中的應(yīng)用已成為一大研究熱點(diǎn)。

本文將提出一種基于此類(lèi)網(wǎng)絡(luò)服務(wù)模型的定位算法并且通過(guò)模擬一種特殊的城市場(chǎng)景對(duì)算法進(jìn)行仿真分析。

1 通過(guò)機(jī)會(huì)網(wǎng)絡(luò)訪(fǎng)問(wèn)互聯(lián)網(wǎng)

這部分將說(shuō)明定位算法所基于的網(wǎng)絡(luò)服務(wù)。首先，將介紹城市機(jī)會(huì)網(wǎng)絡(luò)場(chǎng)景。其次，將介紹單一用戶(hù)利用城市機(jī)會(huì)網(wǎng)絡(luò)訪(fǎng)問(wèn)互聯(lián)網(wǎng)的服務(wù)模型。

1.1 城市機(jī)會(huì)網(wǎng)絡(luò)

基于機(jī)會(huì)網(wǎng)絡(luò)的各類(lèi)服務(wù)需要一定數(shù)量的節(jié)點(diǎn)才能比較高效。而要通過(guò)機(jī)會(huì)網(wǎng)絡(luò)訪(fǎng)問(wèn)互聯(lián)網(wǎng)還要求網(wǎng)絡(luò)中包含可以連接互聯(lián)網(wǎng)的接入點(diǎn)（AccessPoint）。擁有大量移動(dòng)設(shè)備和基礎(chǔ)網(wǎng)絡(luò)設(shè)施的城市道路網(wǎng)格場(chǎng)景就基本具備了應(yīng)用此類(lèi)服務(wù)的所有基本條件。此外，城市中的各類(lèi)法規(guī)和機(jī)制有效限制了城市中各類(lèi)節(jié)點(diǎn)的行為模式，包括運(yùn)動(dòng)方向，速度甚至分布概率等。這讓我們能夠?qū)?jié)點(diǎn)進(jìn)行分類(lèi)，而每類(lèi)節(jié)點(diǎn)擁有相同的行為模式。比如行人，車(chē)輛等。這大大簡(jiǎn)化了對(duì)節(jié)點(diǎn)定位和預(yù)測(cè)的難度，也簡(jiǎn)化了模擬場(chǎng)景的難度。

在此基礎(chǔ)上，本文提出了一種特定的城市場(chǎng)景，即校園場(chǎng)景。它是一種簡(jiǎn)化了的城市場(chǎng)景，但保留了城市場(chǎng)景的主要特征。下文的仿真分析就是基于這種場(chǎng)景的。在這種場(chǎng)景中我們假設(shè)只有行人這一類(lèi)節(jié)點(diǎn)，時(shí)速v為1.5米每秒。兩行人節(jié)點(diǎn)每次相向接觸可以產(chǎn)生的通信量D如公式（1）：

式中VD為數(shù)據(jù)傳輸速率，L為自組網(wǎng)的網(wǎng)絡(luò)覆蓋范圍，t 為自組網(wǎng)建立時(shí)間。若取L為100米，t 為60毫秒，VD為250kbit/s，則每次接觸可以傳輸30M左右的數(shù)據(jù)。

1.2 網(wǎng)絡(luò)服務(wù)模型

當(dāng)前作為主流無(wú)線(xiàn)上網(wǎng)技術(shù)之一的WiFi以IEEE 802.11系列協(xié)議為基礎(chǔ)，通過(guò)終端與WiFi熱點(diǎn)（AP）的直接連接來(lái)將用戶(hù)接入互聯(lián)網(wǎng)。在機(jī)會(huì)網(wǎng)絡(luò)中，用戶(hù)可以通過(guò)各種轉(zhuǎn)發(fā)機(jī)制來(lái)發(fā)出服務(wù)請(qǐng)求，利用機(jī)會(huì)網(wǎng)絡(luò)中的其它節(jié)點(diǎn)將請(qǐng)求數(shù)據(jù)轉(zhuǎn)發(fā)給公共熱點(diǎn)。返回?cái)?shù)據(jù)時(shí)，則可以將數(shù)據(jù)轉(zhuǎn)發(fā)給離用戶(hù)最近的熱點(diǎn)，再利用熱點(diǎn)附近的機(jī)會(huì)網(wǎng)絡(luò)轉(zhuǎn)發(fā)給請(qǐng)求服務(wù)的用戶(hù)。步驟如圖1所示：

圖1 服務(wù)模型示意圖

在本文中，以節(jié)點(diǎn)為源，AP為目標(biāo)的鏈路被稱(chēng)為上行鏈路；而以AP為源，節(jié)點(diǎn)為目標(biāo)的鏈路被稱(chēng)為下行鏈路。由于機(jī)會(huì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)與用戶(hù)的地理位置在不斷變化，上述服務(wù)模型要求在數(shù)據(jù)下行過(guò)程中對(duì)請(qǐng)求服務(wù)的用戶(hù)的地理位置做出預(yù)測(cè)，這正是本文所提出的算法要解決的問(wèn)題。

2 算法設(shè)計(jì)

本文提出的算法是一種基于節(jié)點(diǎn)位置歷史的算法。在某用戶(hù)發(fā)出網(wǎng)絡(luò)服務(wù)請(qǐng)求后，每次與機(jī)會(huì)網(wǎng)絡(luò)中的其它節(jié)點(diǎn)相遇時(shí)，會(huì)向這些節(jié)點(diǎn)廣播自身的位置信息和設(shè)備ID，而接收節(jié)點(diǎn)會(huì)由此生成一條記錄并在記錄中加上當(dāng)前時(shí)刻的時(shí)間戳，然后記錄在本地的定位記錄隊(duì)列上，這樣接收信息的節(jié)點(diǎn)就攜帶了請(qǐng)求服務(wù)的用戶(hù)的位置信息。在本文提出的服務(wù)模型中，由于每個(gè)節(jié)點(diǎn)都可以請(qǐng)求服務(wù)，因此，所有節(jié)點(diǎn)都是其它節(jié)點(diǎn)和自身的位置信息的攜帶者。此外，每當(dāng)節(jié)點(diǎn)進(jìn)入城市場(chǎng)景中所布置的熱點(diǎn)的有效范圍，就將自身的定位記錄隊(duì)列上傳至互聯(lián)網(wǎng)上的定位記錄服務(wù)器，在上傳信息得到確認(rèn)后，節(jié)點(diǎn)將清空本地記錄隊(duì)列以節(jié)省本地存儲(chǔ)空間。而定位記錄服務(wù)器將根據(jù)各熱點(diǎn)不定時(shí)上傳的定位記錄來(lái)更新存有所有節(jié)點(diǎn)位置信息的位置信息表。同時(shí)，定位記錄服務(wù)器還會(huì)維護(hù)一張熱點(diǎn)位置信息表，在向某目標(biāo)用戶(hù)轉(zhuǎn)發(fā)下行數(shù)據(jù)時(shí)，服務(wù)器可以通過(guò)熱點(diǎn)位置信息表找出離該目標(biāo)用戶(hù)的最新位置最近的熱點(diǎn)，然后，向此熱點(diǎn)轉(zhuǎn)發(fā)下行數(shù)據(jù)，再由此熱點(diǎn)向附近的所有機(jī)會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)廣播數(shù)據(jù)，以期它們將數(shù)據(jù)攜帶轉(zhuǎn)發(fā)給目標(biāo)用戶(hù)。這樣可以避免向所有熱點(diǎn)泛洪廣播。節(jié)點(diǎn)算法和熱點(diǎn)算法流程圖如圖2所示：

圖2 節(jié)點(diǎn)算法流程圖 熱點(diǎn)算法流程圖

3 分析方法

本文采用設(shè)置特定場(chǎng)景，利用Eclipse軟件編寫(xiě)Java程序模擬的方法來(lái)分析該算法在場(chǎng)景中的性能。在本部分，首先，需要確定算法性能的度量指標(biāo)。然后，將介紹本仿真采用的節(jié)點(diǎn)移動(dòng)模型。最后，給出仿真場(chǎng)景的具體設(shè)置。

3.1 度量值

本文選取了以下3個(gè)指標(biāo)來(lái)比較分析定位算法的性能。

1）平均傳輸時(shí)延

平均傳輸時(shí)延是在一段時(shí)間內(nèi)，服務(wù)器上某節(jié)點(diǎn)最新位置所在的定位記錄的時(shí)間戳和當(dāng)前時(shí)間的差值的平均值，它描述了整個(gè)網(wǎng)絡(luò)服務(wù)模型所掌握的位置信息的實(shí)時(shí)性和數(shù)據(jù)在下行過(guò)程中的時(shí)延性，也從側(cè)面衡量了算法的準(zhǔn)確性。該指標(biāo)不包括首次傳輸時(shí)延。

2）首次傳輸時(shí)延

首次傳輸時(shí)延是用戶(hù)發(fā)出網(wǎng)絡(luò)服務(wù)請(qǐng)求后，位于網(wǎng)絡(luò)中的定位記錄服務(wù)器得到該請(qǐng)求所需的時(shí)間，這也是服務(wù)器首次獲得該用戶(hù)節(jié)點(diǎn)的位置信息的時(shí)間。它主要描述了本文提出的網(wǎng)絡(luò)服務(wù)中的數(shù)據(jù)在上行過(guò)程中的時(shí)延性。

3）定位命中率

定位命中率是指在某時(shí)刻，實(shí)際離用戶(hù)節(jié)點(diǎn)最近的熱點(diǎn)和通過(guò)本算法預(yù)測(cè)的離該用戶(hù)節(jié)點(diǎn)最近的熱點(diǎn)相符的概率。它直接刻畫(huà)了算法的預(yù)測(cè)準(zhǔn)確性，是最重要的性能度量指標(biāo)。

3.2 節(jié)點(diǎn)移動(dòng)模型

本仿真在參考了RWP（Random Waypoint）和SPMBM（Shortest Path Map-Based Movement）節(jié)點(diǎn)移動(dòng)模型后，提出了一套基于本次仿真場(chǎng)景的特定模型。該模型隨機(jī)生成目標(biāo)位置坐標(biāo)，同一類(lèi)節(jié)點(diǎn)以固定速度沿道路移動(dòng)，直至到達(dá)下一個(gè)路口。當(dāng)節(jié)點(diǎn)到達(dá)路口后以一預(yù)設(shè)概率隨機(jī)決定下一步移動(dòng)至哪個(gè)路口或者在本路口滯留，預(yù)設(shè)概率基于實(shí)際場(chǎng)景中的每個(gè)路口的實(shí)際人流情況。此外還假設(shè)所有節(jié)點(diǎn)在到達(dá)路口后不會(huì)立刻返回上一個(gè)路口。

3.3 仿真場(chǎng)景

本次仿真模擬校園這一特殊的城市場(chǎng)景。在該校園場(chǎng)景中只有行人這一類(lèi)節(jié)點(diǎn)，各節(jié)點(diǎn)不會(huì)離開(kāi)仿真場(chǎng)景所規(guī)定的范圍，也不會(huì)消失。場(chǎng)景中的熱點(diǎn)全部設(shè)置在路口。總共選取3組熱點(diǎn)，每組4個(gè)。前兩組按照將整個(gè)校園縱橫分別分割為三均分和四均分的分割線(xiàn)交點(diǎn)來(lái)選取，取離交點(diǎn)最近的路口。而第三組則選取校園中人流量最高的4個(gè)路口作為熱點(diǎn)。校園場(chǎng)景如圖3所示：

圖3 高人流量路口分布

三組點(diǎn)的選取如圖4、圖5所示：

圖4 三均分近似路口分布

圖5 四均分近似路口分布

本文還選取了節(jié)點(diǎn)數(shù)量（包括用戶(hù)節(jié)點(diǎn)）分別為10、20、30、40的4組情況，這樣與3組熱點(diǎn)構(gòu)成了12組仿真場(chǎng)景。每組進(jìn)行多次仿真，取各次仿真結(jié)果的平均值作為該組仿真的仿真結(jié)果。仿真中只有一個(gè)用戶(hù)節(jié)點(diǎn)，并假設(shè)該節(jié)點(diǎn)本身不具備和熱點(diǎn)連接的能力即它必須依賴(lài)其他節(jié)點(diǎn)的轉(zhuǎn)發(fā)來(lái)實(shí)現(xiàn)和互聯(lián)網(wǎng)的數(shù)據(jù)交換，而其余節(jié)點(diǎn)都為轉(zhuǎn)發(fā)節(jié)點(diǎn)，不會(huì)發(fā)出服務(wù)請(qǐng)求。

其它場(chǎng)景設(shè)置如表1所示：

表1 仿真場(chǎng)景設(shè)置

4 仿真結(jié)果分析

4.1 平均傳輸時(shí)延

如圖6所示：

圖6 平均傳輸延時(shí)

由圖6可見(jiàn)，高人流量組有最小的平均傳輸時(shí)延。四均分組的平均傳輸時(shí)延較長(zhǎng)，相比另兩組有顯著差別。各組平均傳輸時(shí)延隨著節(jié)點(diǎn)數(shù)的增加而減小。三均分組的優(yōu)異表現(xiàn)可能得益于該組熱點(diǎn)的選取靠近場(chǎng)景中心高人流量區(qū)域。

4.2 首次傳輸時(shí)延

如圖7所示：

圖7 首次傳輸延時(shí)

由圖7可見(jiàn)，四均分組的首次傳輸時(shí)延較長(zhǎng)，但與另兩組的差距隨節(jié)點(diǎn)數(shù)增加而顯著減小。首次傳輸時(shí)延在節(jié)點(diǎn)數(shù)從10增加到20時(shí)會(huì)顯著減小，但之后與節(jié)點(diǎn)數(shù)的相關(guān)性明顯減弱，這說(shuō)明了首次傳輸時(shí)延具有很大的隨機(jī)性，它與服務(wù)請(qǐng)求用戶(hù)的路線(xiàn)和各節(jié)點(diǎn)的分布有關(guān)。

4.3 定位命中率

如圖8所示：

圖8 定位命中率

由圖8可見(jiàn)，高人流量組有最高的定位命中率。各組定位命中率都隨節(jié)點(diǎn)數(shù)的增加而提高。各組的命中率都高于25%，即高于隨機(jī)選擇熱點(diǎn)策略下的定位命中率。

5 總結(jié)

本文提出了一種新型的網(wǎng)絡(luò)服務(wù)模型，并且研究了基于該模型的定位算法，經(jīng)過(guò)對(duì)仿真結(jié)果的仔細(xì)分析得出以下結(jié)論：（1）相較于在場(chǎng)景中均勻的布置網(wǎng)絡(luò)熱點(diǎn)，選取人流量高的地方布置熱點(diǎn)可以提高定位算法的性能；（2）本文提出的網(wǎng)絡(luò)模型及定位算法的性能會(huì)隨網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的增加而提高；（3）在節(jié)點(diǎn)較少的網(wǎng)絡(luò)中，本文提出的網(wǎng)絡(luò)模型及定位算法也能夠達(dá)到較好的性能。

機(jī)會(huì)網(wǎng)絡(luò)應(yīng)用的主要困難之一在于難以找到典型的應(yīng)用場(chǎng)景及服務(wù)。本文提出的服務(wù)模型及場(chǎng)景為機(jī)會(huì)網(wǎng)絡(luò)的應(yīng)用提供了一種新思路。

[1]熊永平,孫利民,牛建偉,等.機(jī)會(huì)網(wǎng)絡(luò)[JJ].軟件學(xué)報(bào),,2009.20(1):1244-137.

[2]孫踐知,劉乃瑞,張迎新,等.機(jī)會(huì)網(wǎng)絡(luò)典型路由算法性能分析[J].計(jì)算機(jī)工程,2011.37(16)):86-89.

[3]楊衛(wèi)東,朱紅松,張德賢,等.車(chē)載容遲網(wǎng)絡(luò)中一種基于真實(shí)軌跡的車(chē)輛移動(dòng)模型[[J].計(jì)算機(jī)研究與發(fā)展,,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-），男，上海，復(fù)旦大學(xué)通信科學(xué)與工程系，碩士研究生，研究方向：網(wǎng)絡(luò)與數(shù)據(jù)通信；上海，200433

楊 鑫（1990-），男，浙江，復(fù)旦大學(xué)通信科學(xué)與工程系，碩士研究生，研究方向：物聯(lián)網(wǎng)信息處理；上海，200433

凌 力（1967-），男，浙江，復(fù)旦大學(xué)通信科學(xué)與工程系，副教授，研究方向：網(wǎng)絡(luò)與數(shù)據(jù)通信；上海，200433