面向移動(dòng)群智感知的多任務(wù)分發(fā)算法

2017-04-17 05:13:22徐哲，李卓,2，陳昕

計(jì)算機(jī)應(yīng)用 2017年1期

徐哲，李卓,2，陳昕

(1.北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京 100101； 2.網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點(diǎn)實(shí)驗(yàn)室(北京信息科技大學(xué))，北京 100101)

(*通信作者電子郵箱lizhuo@bistu.edu.cn)

面向移動(dòng)群智感知的多任務(wù)分發(fā)算法

徐哲1，李卓1,2*，陳昕1

(*通信作者電子郵箱lizhuo@bistu.edu.cn)

針對(duì)在移動(dòng)群智感知中基于機(jī)會(huì)通信完成數(shù)據(jù)傳輸會(huì)消耗大量時(shí)間成本的問(wèn)題，提出了一種基于中樞節(jié)點(diǎn)的多任務(wù)分發(fā)(HTA)算法。該算法利用節(jié)點(diǎn)在移動(dòng)網(wǎng)絡(luò)中社交關(guān)系屬性不同的特點(diǎn)，通過(guò)中樞節(jié)點(diǎn)選擇算法將部分節(jié)點(diǎn)作為中樞節(jié)點(diǎn)，并將其用于協(xié)助任務(wù)請(qǐng)求節(jié)點(diǎn)分發(fā)任務(wù)。在任務(wù)請(qǐng)求節(jié)點(diǎn)與中樞節(jié)點(diǎn)相遇時(shí)，同時(shí)給中樞節(jié)點(diǎn)本身和它的從屬節(jié)點(diǎn)分配任務(wù)，并由中樞節(jié)點(diǎn)負(fù)責(zé)向從屬節(jié)點(diǎn)分發(fā)任務(wù)與回收任務(wù)結(jié)果?；赥he ONE模擬器進(jìn)行實(shí)驗(yàn)，與在線任務(wù)分配(NTA)算法相比，HTA算法時(shí)間成本平均降低了24.9%，同時(shí)任務(wù)完成率平均提高150%。實(shí)驗(yàn)結(jié)果表明，HTA算法能夠提高任務(wù)的完成速度，降低時(shí)間成本消耗。

移動(dòng)群智感知；機(jī)會(huì)通信；多任務(wù)分發(fā)；社交；中樞節(jié)點(diǎn)

0 引言

近年來(lái)，智能手機(jī)、平板電腦、可穿戴設(shè)備、車載感知設(shè)備等智能終端設(shè)備迅速發(fā)展普及。這些設(shè)備集成了越來(lái)越多的傳感器，擁有越來(lái)越強(qiáng)大的計(jì)算、感知、存儲(chǔ)和通信能力。隨之出現(xiàn)了一種新的物聯(lián)網(wǎng)感知方式——移動(dòng)群智感知[1]。移動(dòng)群智感知是將眾包的思想與移動(dòng)感知相結(jié)合的產(chǎn)物，將普通用戶的移動(dòng)設(shè)備作為基本感知單元，通過(guò)移動(dòng)互聯(lián)網(wǎng)進(jìn)行有意識(shí)或無(wú)意識(shí)的協(xié)作，形成群智感知網(wǎng)絡(luò)，實(shí)現(xiàn)感知任務(wù)分發(fā)與感知數(shù)據(jù)收集利用，最終完成大規(guī)模的、復(fù)雜的感知任務(wù)。

目前，移動(dòng)群智感知已在環(huán)境監(jiān)測(cè)[2-3]、智能交通[4]、公共安全[5]、城市環(huán)境感知[6]等領(lǐng)域有很多應(yīng)用。但許多群智感知應(yīng)用需要將大量的感知數(shù)據(jù)傳輸?shù)綌?shù)據(jù)中心，采用移動(dòng)蜂窩網(wǎng)絡(luò)將消耗大量的電量和流量成本。為節(jié)約數(shù)據(jù)傳輸成本，移動(dòng)群智感知網(wǎng)絡(luò)中的各節(jié)點(diǎn)通過(guò)短距離通信技術(shù)使用“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的數(shù)據(jù)傳輸機(jī)制(如圖1)交換數(shù)據(jù)。這種數(shù)據(jù)傳輸機(jī)制是基于機(jī)會(huì)通信的傳輸機(jī)制[7]，通信機(jī)會(huì)的出現(xiàn)依賴于移動(dòng)節(jié)點(diǎn)間的相遇。由于移動(dòng)節(jié)點(diǎn)的位置會(huì)隨著時(shí)間動(dòng)態(tài)變化，同時(shí)移動(dòng)節(jié)點(diǎn)間的相遇時(shí)間間隔也有大范圍的波動(dòng)，因此在數(shù)據(jù)傳輸階段會(huì)消耗大量時(shí)間開(kāi)銷[8]，這將導(dǎo)致任務(wù)的整體時(shí)間成本巨大。要在最小化電量和流量成本的同時(shí)，實(shí)現(xiàn)較低的時(shí)間成本，則需要設(shè)計(jì)新的任務(wù)分發(fā)算法。

根據(jù)上述分析，由于移動(dòng)節(jié)點(diǎn)間通信鏈路的間隙性等原因，如何快速有效地實(shí)現(xiàn)任務(wù)分發(fā)及數(shù)據(jù)收集是移動(dòng)群智感知亟待解決的關(guān)鍵問(wèn)題之一。由于移動(dòng)節(jié)點(diǎn)的位置一直動(dòng)態(tài)變化，難以準(zhǔn)確對(duì)節(jié)點(diǎn)間的相遇機(jī)會(huì)進(jìn)行建模和預(yù)測(cè)來(lái)優(yōu)化感知任務(wù)的分發(fā)和分配。因此，如何確定高效任務(wù)分發(fā)、分配策略，將感知任務(wù)低成本、高效地傳遞給移動(dòng)節(jié)點(diǎn)，既克服移動(dòng)節(jié)點(diǎn)的帶寬資源限制，同時(shí)保障數(shù)據(jù)收集效率是移動(dòng)群智感知實(shí)用化的關(guān)鍵。

移動(dòng)節(jié)點(diǎn)在現(xiàn)實(shí)環(huán)境中依據(jù)自身規(guī)律不停地移動(dòng)，雖然存在隨機(jī)性，但又具有顯著的規(guī)律性[9]。同時(shí)移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)拓?fù)溲莼匦允芤苿?dòng)節(jié)點(diǎn)社交屬性影響，因此移動(dòng)節(jié)點(diǎn)間的相遇特性與其社交關(guān)系相關(guān)，兩移動(dòng)節(jié)點(diǎn)間的社交關(guān)系的強(qiáng)弱決定了彼此相遇機(jī)會(huì)的高低。社交網(wǎng)絡(luò)分析(Social Network Analysis， SNA)[10]中有兩個(gè)關(guān)鍵概念：社區(qū)(Communities)和中心性(Centrality)，從整個(gè)網(wǎng)絡(luò)的角度抽象出節(jié)點(diǎn)間的社交關(guān)系，刻畫(huà)了不同移動(dòng)節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的影響力。如果兩個(gè)彼此相遇概率較低的節(jié)點(diǎn)在高影響力節(jié)點(diǎn)的影響范圍內(nèi)，則它們利用高影響力的節(jié)點(diǎn)作為中繼可提高節(jié)點(diǎn)間傳遞數(shù)據(jù)的效率，進(jìn)而用于優(yōu)化感知任務(wù)的分發(fā)與分配。因此，本文擬利用各用戶節(jié)點(diǎn)的社會(huì)屬性，通過(guò)利用合適的中繼節(jié)點(diǎn)減少移動(dòng)群智感知任務(wù)的時(shí)間成本。

圖1 機(jī)會(huì)網(wǎng)絡(luò)中的“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”傳輸機(jī)制

本文主要研究移動(dòng)節(jié)點(diǎn)的社交屬性對(duì)數(shù)據(jù)轉(zhuǎn)發(fā)性能及任務(wù)分配策略的影響。本文提出了一種面向移動(dòng)群智感知的多任務(wù)分發(fā)算法——基于中樞節(jié)點(diǎn)的多任務(wù)分發(fā)(Hub-based multi-Task Assignment, HTA)算法，設(shè)計(jì)并實(shí)現(xiàn)了基于移動(dòng)節(jié)點(diǎn)社交屬性的中樞節(jié)點(diǎn)發(fā)現(xiàn)算法。本文基于St Andrews大學(xué)的Andrews_sassy數(shù)據(jù)集[11]和人工合成數(shù)據(jù)集，利用The ONE機(jī)會(huì)網(wǎng)絡(luò)模擬器進(jìn)行了實(shí)驗(yàn)。結(jié)果表明，比使用直接等待策略的在線任務(wù)分配(oNline Task Assignment, NTA)算法[12]縮短24.9%的任務(wù)平均完成時(shí)間，同時(shí)任務(wù)完成率也有平均150%的提高。

1 相關(guān)工作

移動(dòng)群智感知任務(wù)可分為三個(gè)階段：任務(wù)分發(fā)階段、任務(wù)執(zhí)行階段和任務(wù)結(jié)果返回階段。在任務(wù)分發(fā)階段和任務(wù)結(jié)果返回階段利用“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”機(jī)制進(jìn)行任務(wù)數(shù)據(jù)傳遞，需要解決數(shù)據(jù)傳遞時(shí)延高的問(wèn)題，機(jī)會(huì)網(wǎng)絡(luò)中的路由策略相關(guān)研究對(duì)該問(wèn)題進(jìn)行了廣泛的研究。這方面代表性工作主要包括：洪泛[13]是最極端的一種數(shù)據(jù)路由策略，它的思想是節(jié)點(diǎn)將數(shù)據(jù)傳遞給每一個(gè)與自己接觸的節(jié)點(diǎn)，通過(guò)網(wǎng)絡(luò)中存在多份數(shù)據(jù)來(lái)提高數(shù)據(jù)的投遞成功率和速率。由于網(wǎng)絡(luò)中存在多份數(shù)據(jù)，使得網(wǎng)絡(luò)負(fù)載增加，對(duì)每個(gè)智能設(shè)備的存儲(chǔ)能力造成巨大壓力，存儲(chǔ)容量很快會(huì)被占滿并無(wú)法再接收新的數(shù)據(jù)，導(dǎo)致網(wǎng)絡(luò)性能降低。直接等待[14]是另一種極端的數(shù)據(jù)轉(zhuǎn)發(fā)策略，它當(dāng)且僅當(dāng)源節(jié)點(diǎn)遇到目的節(jié)點(diǎn)時(shí)才投遞數(shù)據(jù)，數(shù)據(jù)的投遞成功率最低、速率最慢。噴射-等待[15]是機(jī)會(huì)網(wǎng)絡(luò)中的一種典型數(shù)據(jù)轉(zhuǎn)發(fā)策略，通過(guò)限制網(wǎng)絡(luò)中消息的副本數(shù)，有效降低了網(wǎng)絡(luò)負(fù)載。但是在移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)中，節(jié)點(diǎn)由于社會(huì)關(guān)系的影響，轉(zhuǎn)發(fā)能力存在較大的差異，造成噴射等待效率較低。文獻(xiàn)[16]中提出的一種BUBBLE轉(zhuǎn)發(fā)策略利用了人的社會(huì)性，根據(jù)節(jié)點(diǎn)的移動(dòng)軌跡計(jì)算出每個(gè)節(jié)點(diǎn)的活躍度，然后依據(jù)節(jié)點(diǎn)活躍度在系統(tǒng)和社區(qū)的排名，進(jìn)行消息路由策略的選擇：源節(jié)點(diǎn)將消息傳輸給全局活躍度大于自己的節(jié)點(diǎn)，直到將消息傳輸?shù)脚c目標(biāo)節(jié)點(diǎn)位于同一社區(qū)的中繼節(jié)點(diǎn)，然后中繼節(jié)點(diǎn)再將消息傳輸給社區(qū)活躍度大于自己的節(jié)點(diǎn)，直到消息達(dá)到目的節(jié)點(diǎn)。該算法考慮社會(huì)關(guān)系對(duì)數(shù)據(jù)傳輸機(jī)會(huì)的影響，利用了活躍度高的節(jié)點(diǎn)與其他節(jié)點(diǎn)接觸機(jī)會(huì)較多的特點(diǎn)，但要求機(jī)會(huì)網(wǎng)絡(luò)中的各節(jié)點(diǎn)清楚所有節(jié)點(diǎn)的社區(qū)劃分情況以及所有節(jié)點(diǎn)的活躍度，這使得該策略的應(yīng)用環(huán)境受到限制，實(shí)用性面臨挑戰(zhàn)。

在任務(wù)執(zhí)行階段，節(jié)點(diǎn)處理在任務(wù)分發(fā)階段接收到的任務(wù)，這里涉及到任務(wù)處理順序的問(wèn)題，目前最相關(guān)的研究在并行機(jī)調(diào)度領(lǐng)域。這方面代表性工作文獻(xiàn)[17-18]針對(duì)傳統(tǒng)并行機(jī)調(diào)度問(wèn)題的研究進(jìn)展作出了詳細(xì)的總結(jié)。此外，文獻(xiàn)[12]提出一種針對(duì)移動(dòng)社交網(wǎng)絡(luò)(與移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)具有相似的用戶移動(dòng)模型)環(huán)境下多任務(wù)分配問(wèn)題的算法，以動(dòng)態(tài)在線模式運(yùn)行的情況下得到的實(shí)驗(yàn)結(jié)果顯示時(shí)間性能優(yōu)于現(xiàn)有其他算法。

以上總結(jié)中，雖然有很多相關(guān)的研究成果可用于移動(dòng)群智感知的任務(wù)分發(fā)問(wèn)題中來(lái)，但是，各階段的理論又很難結(jié)合在一起，比如，數(shù)據(jù)路由問(wèn)題的解決方案要求在作出決策前確定要傳輸?shù)臄?shù)據(jù)，而任務(wù)分配算法則需要在任務(wù)分發(fā)者和普通節(jié)點(diǎn)相遇時(shí)再確定任務(wù)分配策略(即待傳輸?shù)臄?shù)據(jù))。因此，為進(jìn)一步減少感知任務(wù)的整體時(shí)間消耗，需要利用移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)中的社交屬性，提出新的算法，將任務(wù)分發(fā)與任務(wù)調(diào)度結(jié)合。

文獻(xiàn)[12]對(duì)于任務(wù)分發(fā)和結(jié)果返回的路由問(wèn)題采用的是直接等待策略，并對(duì)這種情況下的多任務(wù)分配問(wèn)題提出了解決方案。與文獻(xiàn)[12]不同的是，本文將任務(wù)分發(fā)與任務(wù)調(diào)度結(jié)合，使用單跳轉(zhuǎn)發(fā)策略，通過(guò)增加中樞節(jié)點(diǎn)輔助任務(wù)請(qǐng)求者分發(fā)感知任務(wù)，并提出了一種新的多任務(wù)分配與分發(fā)算法。

2 網(wǎng)絡(luò)模型與問(wèn)題定義

在一個(gè)由n個(gè)用戶組成的移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)中，每個(gè)用戶節(jié)點(diǎn)均攜帶著一個(gè)具有一定計(jì)算、存儲(chǔ)、通信能力的智能設(shè)備，并按照各自的活動(dòng)規(guī)律在地圖中移動(dòng)。假設(shè)有一個(gè)被稱為任務(wù)分發(fā)者的特殊用戶，用v0表示，他有m個(gè)感知任務(wù)需要分發(fā)給網(wǎng)絡(luò)中的其他用戶。如果v0與其他用戶vi相遇，v0將分配若干手中的感知任務(wù)給vi。然后，vi將花費(fèi)一定量的時(shí)間去完成分配給自己的任務(wù)。接著，vi在完成感知任務(wù)后，將一直等到自己與v0再次相遇時(shí)，將所得到的感知結(jié)果返回給v0。

本文假設(shè)：

1)近距離通信設(shè)備的傳輸性能滿足：分配任務(wù)和返回結(jié)果等數(shù)據(jù)能夠在節(jié)點(diǎn)間的一次機(jī)會(huì)連接斷開(kāi)之前傳輸完成。

2)移動(dòng)用戶i和j相遇間隔時(shí)間服從特征值為λi, j的指數(shù)分布。

3)每對(duì)用戶之間的關(guān)系參數(shù)λi, j代表了在單位時(shí)間內(nèi)，用戶i與用戶j之間的平均相遇次數(shù)。通過(guò)歷史相遇記錄或歷史連接記錄可以計(jì)算出參數(shù)λi, j。假設(shè)兩用戶在一段時(shí)間內(nèi)的接觸歷史記錄由集合C表示，每條記錄用ci表示，則：

(1)

定義1 任務(wù)完成時(shí)間(Makespan)。一個(gè)感知任務(wù)的完成時(shí)間等于t1+t2+t3，其中：t1為任務(wù)分發(fā)者開(kāi)始分發(fā)任務(wù)到節(jié)點(diǎn)i接收到該任務(wù)的時(shí)長(zhǎng)，t2為任務(wù)在節(jié)點(diǎn)i手中停留的時(shí)長(zhǎng)，t3為節(jié)點(diǎn)i將任務(wù)結(jié)果傳遞回任務(wù)分發(fā)者的時(shí)長(zhǎng)。對(duì)于任務(wù)j的Makespan，使用M(j)表示。

本文假設(shè)，任務(wù)分發(fā)者v0有m個(gè)獨(dú)立的感知任務(wù)，用J={j1,j2,…,jm}表示，這些任務(wù)可能屬于不同的任務(wù)類型。為了簡(jiǎn)化問(wèn)題，將任務(wù)的工作量(workload)統(tǒng)一為感知用時(shí)；使用t1,t2,…,tm表示且J中各任務(wù)的工作量大小,關(guān)系為t1≤t2≤…≤tm。假定v0將所有任務(wù)全部分配給其他用戶，且每個(gè)任務(wù)只會(huì)分配給一名用戶。

使用AM(Π)表示對(duì)于任務(wù)分配策略Π中的所有任務(wù)的AverageMakespan。公式表示為：

(2)

問(wèn)題1 多任務(wù)分配問(wèn)題。給定一個(gè)節(jié)點(diǎn)集合V={v0,v1,v2,…,vn-1}以及節(jié)點(diǎn)關(guān)系矩陣R[n][n]、一個(gè)感知任務(wù)集合J={J0,J1,J2,…,Jn-1}及其對(duì)應(yīng)的任務(wù)工作量集合T={T1,T2,…,Tm}。其中R[n][n]表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的單位時(shí)間內(nèi)的平均相遇次數(shù)，則多任務(wù)分配問(wèn)題是如何確定一個(gè)任務(wù)分配策略Π={J1,J2,…,Jn}，使AM(Π)最小。

在任務(wù)分發(fā)階段之前，任務(wù)分發(fā)者需要確定任務(wù)的分配策略才能將任務(wù)分發(fā)給各節(jié)點(diǎn)，任務(wù)分發(fā)階段和任務(wù)結(jié)果返回階段的時(shí)間成本又是必須考慮的因素。但是由于節(jié)點(diǎn)的移動(dòng)具有隨機(jī)性，難以準(zhǔn)確預(yù)測(cè)節(jié)點(diǎn)彼此何時(shí)相遇，所以任務(wù)分配策略難以實(shí)現(xiàn)最優(yōu)。

定理1 多任務(wù)分配問(wèn)題是NP-完全問(wèn)題。

證明首先，本文引入非相關(guān)并行機(jī)調(diào)度問(wèn)題。該問(wèn)題可描述為：任給m個(gè)工件，n臺(tái)機(jī)器，對(duì)每個(gè)i=1,2,…,n和每個(gè)j=1,2,…,m，第j個(gè)工件在第i臺(tái)機(jī)器上的加工時(shí)間為pij=ti+ti′+τj，對(duì)所有m個(gè)工件在n臺(tái)機(jī)器上安排加工時(shí)間表，使得在這些機(jī)器上最后加工完的平均任務(wù)完成時(shí)間最短。

在清楚所有節(jié)點(diǎn)間相遇時(shí)間的情況下，設(shè)任務(wù)分發(fā)者與節(jié)點(diǎn)v1,v2,…,vn的相遇時(shí)間為t1,t2,…,tn，距離下次相遇的時(shí)間間隔為t1′,t2′,…,tn′，對(duì)于m個(gè)任務(wù)，第j個(gè)任務(wù)的執(zhí)行時(shí)間為τj，則多任務(wù)分配問(wèn)題與非相關(guān)并行機(jī)調(diào)度問(wèn)題等價(jià)。

非相關(guān)并行機(jī)調(diào)度問(wèn)題已被證明為NP-完全問(wèn)題[19]，因此在清楚所有節(jié)點(diǎn)彼此相遇時(shí)間的情況下，多任務(wù)分配問(wèn)題是NP-完全問(wèn)題。清楚所有節(jié)點(diǎn)彼此相遇時(shí)間的是多任務(wù)分配問(wèn)題的一個(gè)特例，因此多任務(wù)分配問(wèn)題是NP-完全問(wèn)題。

接下來(lái)將介紹利用移動(dòng)節(jié)點(diǎn)社交屬性提出的一種多任務(wù)分配算法。

3 基于節(jié)點(diǎn)社交屬性的多任務(wù)分配算法

根據(jù)文獻(xiàn)[12]所述，為實(shí)現(xiàn)最優(yōu)任務(wù)分配策略，任務(wù)分發(fā)者應(yīng)該在與某節(jié)點(diǎn)相遇時(shí)才確定對(duì)應(yīng)需要分配的任務(wù)集。移動(dòng)群智感知網(wǎng)絡(luò)中的任務(wù)分發(fā)節(jié)點(diǎn)在遇到其他節(jié)點(diǎn)之前并不確定要分配給每個(gè)節(jié)點(diǎn)的任務(wù)集，更無(wú)法確定接收任務(wù)數(shù)據(jù)的目標(biāo)節(jié)點(diǎn)。因此，目前針對(duì)機(jī)會(huì)網(wǎng)絡(luò)的數(shù)據(jù)傳輸轉(zhuǎn)發(fā)策略[13-16]并不直接適用于移動(dòng)群智感知環(huán)境，這些策略均需要在數(shù)據(jù)傳遞初始階段就確定要傳遞的數(shù)據(jù)。在群智感知的數(shù)據(jù)分發(fā)領(lǐng)域，目前廣泛使用的策略是直接交付型，相當(dāng)于直接等待策略。因此，通過(guò)整合任務(wù)分配策略與數(shù)據(jù)分發(fā)策略的決策環(huán)節(jié)，優(yōu)化任務(wù)調(diào)度和數(shù)據(jù)分發(fā)流程，實(shí)現(xiàn)優(yōu)化AM。

本文提出了一種借助中樞節(jié)點(diǎn)協(xié)助分發(fā)任務(wù)的任務(wù)分配(HTA)算法。該算法的主要思想是依據(jù)節(jié)點(diǎn)之間的社交屬性篩選出中樞節(jié)點(diǎn)和對(duì)應(yīng)的從屬節(jié)點(diǎn)，任務(wù)分發(fā)者與中樞節(jié)點(diǎn)相遇時(shí)同時(shí)確定從屬節(jié)點(diǎn)的任務(wù)分配，然后借助該中樞節(jié)點(diǎn)協(xié)助分發(fā)從屬節(jié)點(diǎn)的任務(wù)。在完整介紹該算法前，先對(duì)中樞節(jié)點(diǎn)選擇算法進(jìn)行完整闡述。

3.1 中樞節(jié)點(diǎn)選擇算法

給定一個(gè)節(jié)點(diǎn)集合V={v0,v1,v2,…,vn-1}以及節(jié)點(diǎn)關(guān)系矩陣λ[n][n]。其中λi, j表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的單位時(shí)間內(nèi)的平均相遇次數(shù)。令ti, j表示節(jié)點(diǎn)i與節(jié)點(diǎn)j通信的時(shí)間成本，即節(jié)點(diǎn)i與節(jié)點(diǎn)j相遇的平均時(shí)間間隔。

問(wèn)題2 中樞節(jié)點(diǎn)選擇問(wèn)題。從除v0以外的其他節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)子集A，使v0僅向節(jié)點(diǎn)集A中的節(jié)點(diǎn)發(fā)送消息，最多通過(guò)一次轉(zhuǎn)發(fā)就可使所有節(jié)點(diǎn)接收到消息，且t0,i+ti, j≤t0, j(i∈A,j?A)。

根據(jù)對(duì)本文要解決問(wèn)題的分析，可以得出中樞節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中應(yīng)該是影響力較大的節(jié)點(diǎn)。中樞節(jié)點(diǎn)選擇問(wèn)題可以通過(guò)轉(zhuǎn)換為求Top-K問(wèn)題[20]，然后使用相應(yīng)的求解辦法求出結(jié)果，文獻(xiàn)[21]提出的算法能夠找出重要節(jié)點(diǎn)。但，針對(duì)本文問(wèn)題的分析，發(fā)現(xiàn)得到重要節(jié)點(diǎn)集后，重要節(jié)點(diǎn)以外的其他節(jié)點(diǎn)的歸屬問(wèn)題依然沒(méi)有解決。

通過(guò)分析，得出中樞節(jié)點(diǎn)應(yīng)當(dāng)具有以下屬性：某從屬節(jié)點(diǎn)vi與中樞節(jié)點(diǎn)的相遇概率應(yīng)高于節(jié)點(diǎn)vi與任務(wù)分發(fā)節(jié)點(diǎn)v0之間的相遇概率。因此，本文提出了一種新的中樞節(jié)點(diǎn)選擇算法。直接根據(jù)節(jié)點(diǎn)間相遇概率的高低確定中樞節(jié)點(diǎn)。根據(jù)2.1節(jié)對(duì)移動(dòng)社交網(wǎng)絡(luò)中的各節(jié)點(diǎn)的關(guān)系屬性λ的定義，每?jī)蓚€(gè)節(jié)點(diǎn)之間的關(guān)系屬性λ代表了這兩個(gè)節(jié)點(diǎn)的相遇概率高低，λ的數(shù)值越大對(duì)應(yīng)兩節(jié)點(diǎn)的相遇概率越高；另一方面它也反映了這兩個(gè)節(jié)點(diǎn)關(guān)系遠(yuǎn)近程度。

中樞節(jié)點(diǎn)選擇算法的基本思路是：要判斷vj是否為中樞節(jié)點(diǎn)，只需遍歷關(guān)系矩陣的每一行，判斷第j列的每一個(gè)值在其對(duì)應(yīng)的第i行中是否為最大值，如果為最大值則vj是vi的中樞節(jié)點(diǎn)。

具體實(shí)現(xiàn)方法是：若節(jié)點(diǎn)vj是另一節(jié)點(diǎn)vi的中樞節(jié)點(diǎn)，則在關(guān)系矩陣的第i行中，λi, j是最大值。要判斷vj是否為中樞節(jié)點(diǎn)，只需遍歷關(guān)系矩陣的每一行，求出其中的最大值，然后判斷該值是否在第j列。算法具體步驟見(jiàn)算法1。

在算法1第1)步中的result記錄了節(jié)點(diǎn)Vi的從屬節(jié)點(diǎn)，如果result為空集，則表示節(jié)點(diǎn)vi不作為中樞節(jié)點(diǎn)。

下面用一個(gè)簡(jiǎn)單的例子對(duì)該算法進(jìn)行解釋：首先，假設(shè)一個(gè)移動(dòng)社交網(wǎng)絡(luò)(Mobile Social Network, MSN)中有5個(gè)節(jié)點(diǎn)，其中的關(guān)系矩陣為：

先判斷節(jié)點(diǎn)1是否為某些節(jié)點(diǎn)的中樞節(jié)點(diǎn)：首先，在第2行中尋找最大值，第2行的最大值在第3列，不在第1列，所以節(jié)點(diǎn)1不是節(jié)點(diǎn)2的中樞節(jié)點(diǎn)；然后繼續(xù)在第3行中選擇最大值，第3行中的最大值在第2列，也不在第1列，所以節(jié)點(diǎn)1不是節(jié)點(diǎn)3的中樞節(jié)點(diǎn)；一直掃描到第5行，發(fā)現(xiàn)第一列中的數(shù)值在對(duì)應(yīng)的每一行里都不是最大值，所以，得到的計(jì)算結(jié)果是節(jié)點(diǎn)1不作為中樞節(jié)點(diǎn)。再來(lái)嘗試判斷節(jié)點(diǎn)2是否為某些節(jié)點(diǎn)的中樞節(jié)點(diǎn)，可以發(fā)現(xiàn)在第3行和第4行中，第2列的數(shù)值為所在行的最大值，說(shuō)明節(jié)點(diǎn)3和節(jié)點(diǎn)4均與節(jié)點(diǎn)2的相遇頻率高于與其他節(jié)點(diǎn)的相遇頻率，所以節(jié)點(diǎn)2作為節(jié)點(diǎn)3和節(jié)點(diǎn)4的中樞節(jié)點(diǎn)。依次判斷節(jié)點(diǎn)3、4、5可以計(jì)算得，節(jié)點(diǎn)3是節(jié)點(diǎn)1、2的中樞節(jié)點(diǎn)，節(jié)點(diǎn)4是節(jié)點(diǎn)5的中樞節(jié)點(diǎn)，節(jié)點(diǎn)5不是中樞節(jié)點(diǎn)

算法1 中樞節(jié)點(diǎn)選擇算法。

輸入：節(jié)點(diǎn)集合V={v0,v1,v2,…,vn-1}；關(guān)系矩陣λ[n][n]。輸出：每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的從屬節(jié)點(diǎn)集合，若某節(jié)點(diǎn)的從屬節(jié)點(diǎn)集為空，則其不作為中樞節(jié)點(diǎn)。

result=[?,?,…,?],result初始狀態(tài)有n個(gè)空集

fori← 1 ton-1:

forj ← 1ton-1:

max=λj,0

indexmax=0

fork ← 1ton-1:

如果λj,k大于max

max=λj,k

indexmax=k

10)

endfor

11)

如果indexmax等于i，則將vj加入result[i]

12)

endfor

13)

endfor

14)

輸出result

通過(guò)分析，該算法的時(shí)間復(fù)雜度為O(n2)，且僅計(jì)算了一個(gè)節(jié)點(diǎn)是否為中樞節(jié)點(diǎn)，若要對(duì)所有節(jié)點(diǎn)均計(jì)算一遍，則時(shí)間復(fù)雜度為O(n3)。在實(shí)際應(yīng)用中還可以采用另一種優(yōu)化后的實(shí)現(xiàn)，一次求出所有中樞節(jié)點(diǎn)及其從屬節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(n2)。

算法的主要思路與算法1基本相同，主要區(qū)別在第7)～10)步上，具體步驟見(jiàn)算法2。

算法2 優(yōu)化后的中樞節(jié)點(diǎn)選擇算法。

result=[?,?,…,?],result初始狀態(tài)有n個(gè)空集

forj← 1 ton-1:

max=λj,0

indexmax=0

fork ← 1ton-1:

如果λj,k大于max

max=λj,k

indexmax=k

endfor

10)

result[indexmax]=result[indexmax]+{vj}

11)

end for

12)

輸出result

3.2 任務(wù)分配與分發(fā)算法

通過(guò)3.1節(jié)的介紹，清楚了如何對(duì)中樞節(jié)點(diǎn)進(jìn)行選擇，本節(jié)將結(jié)合中樞節(jié)點(diǎn)選擇算法，計(jì)算感知任務(wù)集的分配策略并確定分發(fā)路徑。算法完整過(guò)程見(jiàn)算法3。

算法3 任務(wù)分配與分發(fā)算法。

輸入：待分配的任務(wù)集J={j1,j2,…,jm;t1≤t2≤…≤tm}；待分配任務(wù)的節(jié)點(diǎn)集V={v1,v2,…,vn}；關(guān)系矩陣λ[n][n]；任務(wù)分發(fā)者遇到的節(jié)點(diǎn)對(duì)應(yīng)序號(hào)i。輸出：任務(wù)集Ji及JF={Jj|j∈Fi}，F(xiàn)i是vi的從屬節(jié)點(diǎn)集。

當(dāng)任務(wù)分發(fā)者v0與節(jié)點(diǎn)vi相遇，執(zhí)行以下步驟：

在中樞節(jié)點(diǎn)選擇算法得到的所有從屬節(jié)點(diǎn)集中找出Fi

如果Fi非空:

將vi作為中樞節(jié)點(diǎn)，且Fi對(duì)應(yīng)中樞節(jié)點(diǎn)vi的從屬節(jié)點(diǎn)集

fork← 1 ton-1:

IPTk=2/λ0,k

endfor

IPTi=1/λ0,i,IPTj=1/λ0,i+1/λi, j,j∈Fi

m等于剩余未分配任務(wù)數(shù)量

forp← 1 tom:

10)

找出IPT值最小的節(jié)點(diǎn)對(duì)應(yīng)的序號(hào)indexmin

11)

Jindexmin=Jindexmin+{jp}

12)

IPTindexmin=IPTindexmin+tp

13)

如果indexmin等于i或indexmin對(duì)應(yīng)節(jié)點(diǎn)在Fi集中，則：

14)

J=J-{jp}

15)

endfor

16)

輸出Ji及JF={Jj|j∈Fi}，其余節(jié)點(diǎn)得到的結(jié)果拋棄

每次執(zhí)行任務(wù)分配算法后，只將相遇節(jié)點(diǎn)及其從屬節(jié)點(diǎn)(如果相遇節(jié)點(diǎn)被作為中樞節(jié)點(diǎn))分配到的任務(wù)分發(fā)出去，其余節(jié)點(diǎn)分配到的任務(wù)只是暫時(shí)的，不作為最終結(jié)果。

在中樞節(jié)點(diǎn)選擇算法中有可能會(huì)出現(xiàn)這樣的情況，兩個(gè)節(jié)點(diǎn)vi和vj互為中樞節(jié)點(diǎn)，則處理方案為，任務(wù)分發(fā)者v0先與節(jié)點(diǎn)vi相遇，就將vi作為vj的中樞節(jié)點(diǎn)。其次，消息準(zhǔn)備從中樞節(jié)點(diǎn)傳遞給從屬節(jié)點(diǎn)前，從屬節(jié)點(diǎn)判斷消息的上一次傳遞路徑是否為從屬節(jié)點(diǎn)本身，避免循環(huán)傳遞消息，即浪費(fèi)網(wǎng)絡(luò)資源，又有可能造成死循環(huán)。之所以可能出現(xiàn)上述問(wèn)題，是因?yàn)閺膹膶俟?jié)點(diǎn)的角度看，自身也是中樞節(jié)點(diǎn)，中樞節(jié)點(diǎn)也是從屬節(jié)點(diǎn)的從屬節(jié)點(diǎn)。

本文使用算法3將任務(wù)分配和分發(fā)收集的完整流程優(yōu)化為以下步驟：

1)在任務(wù)分發(fā)者v0，從開(kāi)始分發(fā)感知任務(wù)起第一次遇到節(jié)點(diǎn)vi時(shí)，執(zhí)行任務(wù)分配和分發(fā)算法3，計(jì)算出節(jié)點(diǎn)vi及其從屬節(jié)點(diǎn)(若節(jié)點(diǎn)vi被確定為中樞節(jié)點(diǎn))的任務(wù)分配策略。將vi及其從屬節(jié)點(diǎn)從節(jié)點(diǎn)集V中移除。

2)中樞節(jié)點(diǎn)vi接收到任務(wù)分配策略后，立即開(kāi)始按照工作量從小到大的順序依次執(zhí)行分配給自己的感知任務(wù)；同時(shí)在之后的第一次遇到屬于自己的從屬節(jié)點(diǎn)時(shí)，將自己保存的從屬節(jié)點(diǎn)任務(wù)分配策略分發(fā)給從屬節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)vi再一次遇到任務(wù)分發(fā)者時(shí)，將自己已經(jīng)完成的感知任務(wù)結(jié)果和來(lái)自從屬節(jié)點(diǎn)的感知任務(wù)結(jié)果傳遞給任務(wù)分發(fā)者。

3)從屬節(jié)點(diǎn)也開(kāi)始按照工作量從小到大的順序依次執(zhí)行分配給自己的感知任務(wù)。等到再一次自己遇到自己的中樞節(jié)點(diǎn)時(shí)，將自己已經(jīng)完成的感知任務(wù)結(jié)果傳遞給中樞節(jié)點(diǎn)。

4)一直等到任務(wù)分發(fā)者接收到所有感知任務(wù)的執(zhí)行結(jié)果后，過(guò)程終止。

下面對(duì)該任務(wù)分配與分發(fā)算法的實(shí)際應(yīng)用可行性進(jìn)行分析。算法1至3將網(wǎng)絡(luò)全局信息即關(guān)系矩陣λ[n][n]作為輸入，且僅被任務(wù)分發(fā)者使用，而剩余其他節(jié)點(diǎn)在完成感知任務(wù)的整個(gè)流程中均不需要關(guān)系矩陣λ[n][n]。而在實(shí)際系統(tǒng)實(shí)現(xiàn)中可參與群智感知任務(wù)的移動(dòng)節(jié)點(diǎn)會(huì)向系統(tǒng)提交注冊(cè)信息，可要求移動(dòng)節(jié)點(diǎn)上報(bào)自己與整個(gè)網(wǎng)絡(luò)其他節(jié)點(diǎn)的接觸歷史用于計(jì)算出整個(gè)網(wǎng)絡(luò)各節(jié)點(diǎn)之間的關(guān)系。任務(wù)分發(fā)者通過(guò)系統(tǒng)獲取參與群智感知任務(wù)的節(jié)點(diǎn)集的同時(shí)，獲取關(guān)系矩陣λ[n][n]即可。因此，由于只有任務(wù)分發(fā)者一個(gè)節(jié)點(diǎn)需要了解移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)的全局信息，降低了系統(tǒng)實(shí)現(xiàn)難度，具有實(shí)際應(yīng)用可行性。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)環(huán)境

本文使用TheONE模擬器對(duì)HTA算法的性能進(jìn)行驗(yàn)證，另外將NTA作為對(duì)照算法。本次實(shí)驗(yàn)所采用的現(xiàn)實(shí)環(huán)境數(shù)據(jù)集是來(lái)自StAndrews大學(xué)的Andrews_sassy數(shù)據(jù)集[11]。該數(shù)據(jù)集是由來(lái)自StAndrews大學(xué)的25名志愿者各自所攜帶的裝有傳感器的智能設(shè)備記錄的彼此相遇記錄和這些志愿者在Facebook上的社交網(wǎng)絡(luò)數(shù)據(jù)組成。另外本次實(shí)驗(yàn)還使用了人工生成的用戶接觸記錄的虛擬數(shù)據(jù)集。用于生成數(shù)據(jù)所采用的用戶移動(dòng)模型為工作日移動(dòng)模型(WorkingDayMovementmodel,WDM)[22]，模擬了40位用戶持續(xù)1 944h的活動(dòng)。各數(shù)據(jù)集的詳細(xì)參數(shù)如表1。本文將每個(gè)數(shù)據(jù)集中前三分之一時(shí)間的相遇記錄用于計(jì)算用戶節(jié)點(diǎn)彼此的社交網(wǎng)絡(luò)關(guān)系權(quán)重，后三分之二時(shí)間的相遇記錄用于模擬實(shí)驗(yàn)。

表1 實(shí)驗(yàn)所用數(shù)據(jù)集的統(tǒng)計(jì)信息

此外，針對(duì)存在的兩個(gè)中樞節(jié)點(diǎn)選擇算法1、2，本文實(shí)驗(yàn)使用改進(jìn)后的算法2。

為了提高實(shí)驗(yàn)說(shuō)服力，達(dá)到充分實(shí)驗(yàn)的目的，將每個(gè)數(shù)據(jù)集中的各個(gè)節(jié)點(diǎn)分別作為任務(wù)分發(fā)者分配一次感知任務(wù)，通過(guò)節(jié)點(diǎn)在移動(dòng)網(wǎng)絡(luò)中所具有的社交屬性不同來(lái)揭示算法在各種環(huán)境下的性能表現(xiàn)。此外，實(shí)驗(yàn)中用到的感知任務(wù)集通過(guò)程序隨機(jī)生成，由多組具有不同任務(wù)數(shù)量和平均workload的數(shù)據(jù)組成，參數(shù)設(shè)置如表2。其中任務(wù)數(shù)量為100，200和300，平均workload為500,600,…,1 000,2 000,…,5 000s。此外，本次實(shí)驗(yàn)不考慮任務(wù)的時(shí)效性問(wèn)題，即任務(wù)不會(huì)過(guò)期，只要任務(wù)的結(jié)果能夠傳回任務(wù)分發(fā)者即視為任務(wù)完成。通過(guò)簡(jiǎn)單計(jì)算，可以得出本次實(shí)驗(yàn)在使用Andrews_sassy數(shù)據(jù)集時(shí)，一共進(jìn)行了3×10×25=750次完整的模擬移動(dòng)群智感知過(guò)程；在使用人工數(shù)據(jù)時(shí)，一共進(jìn)行了3×10×27=810次完整的模擬移動(dòng)群智感知過(guò)程。實(shí)驗(yàn)的結(jié)果采用相同感知任務(wù)集下每個(gè)節(jié)點(diǎn)做一次任務(wù)分發(fā)者時(shí)的平均任務(wù)完成率和平均AM為評(píng)價(jià)指標(biāo)。

4.2 實(shí)驗(yàn)結(jié)果

先對(duì)真實(shí)數(shù)據(jù)集下的實(shí)驗(yàn)進(jìn)行分析。圖2顯示了在Andrew_sassy數(shù)據(jù)集和不同任務(wù)集下，HTA和NTA在AM方面的相對(duì)性能對(duì)比結(jié)果。整體而言，HTA大幅縮短了完成任務(wù)所需要的平均時(shí)間，平均縮短了24.9%。同時(shí)，如圖3所示，與NTA相比，HTA在絕大多數(shù)節(jié)點(diǎn)上還實(shí)現(xiàn)了任務(wù)完成率的大幅提高；對(duì)于所有節(jié)點(diǎn)，平均提高了150%。按任務(wù)集的平均工作量對(duì)實(shí)驗(yàn)分組，結(jié)果顯示任務(wù)集數(shù)量越大，HTA算法對(duì)平均完成時(shí)間所縮短的百分比越大、任務(wù)抵達(dá)率所提高的百分比也越大。

表2 實(shí)驗(yàn)所用任務(wù)集的參數(shù)配置

圖2 HTA相比NTA的AM提升百分比(Andrew_sassy數(shù)據(jù)集)

圖3 HTA相比NTA的消息抵達(dá)率提升百分比(Andrew_sassy數(shù)據(jù)集)

下面對(duì)人工生成的模擬數(shù)據(jù)集進(jìn)行性能分析。在所有任務(wù)集下，使用HTA得到的AM比使用NTA得到的AM平均縮短34.9%，詳細(xì)的AM性能比較如圖4；同時(shí)消息抵達(dá)率平均有111.1%的提高，詳細(xì)的消息抵達(dá)率性能比較如圖5。

圖4 HTA相比NTA的AM提升百分比(人工合成數(shù)據(jù)集)

通過(guò)圖2和圖4，還可發(fā)現(xiàn)，按任務(wù)集的任務(wù)數(shù)量分組后，對(duì)不同平均工作量的任務(wù)集進(jìn)行對(duì)比，結(jié)果顯示HTA算法對(duì)任務(wù)的AM所實(shí)現(xiàn)的改進(jìn)百分比隨任務(wù)集平均工作量的增加而有所降低，但縮短的絕對(duì)時(shí)間長(zhǎng)度是增加的。通過(guò)分析得出，這一改進(jìn)百分比變小的現(xiàn)象是由于任務(wù)工作量增加，任務(wù)分發(fā)階段消耗的時(shí)間t1與任務(wù)結(jié)果收集階段消耗的時(shí)間t3所占比重減小、任務(wù)執(zhí)行階段消耗的時(shí)間t2所占比重增加的原因造成的。因此，可以得出結(jié)論，本文所提算法對(duì)工作量越小的感知任務(wù)集越適用。

圖5 HTA相比NTA的消息抵達(dá)率提升百分比(人工合成數(shù)據(jù)集)

根據(jù)性能分析，發(fā)現(xiàn)HTA算法對(duì)AM性能的改進(jìn)程度有差異，根據(jù)數(shù)據(jù)集的具體特點(diǎn)進(jìn)行分析得出：因?yàn)镠TA算法依賴于移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)中各節(jié)點(diǎn)之間的穩(wěn)定強(qiáng)關(guān)系，而作為任務(wù)分發(fā)者的節(jié)點(diǎn)遇到的其他節(jié)點(diǎn)在移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)中的活躍程度各不相同，在任務(wù)分發(fā)者節(jié)點(diǎn)與其他普通節(jié)點(diǎn)的相遇次數(shù)較多時(shí)，并不能發(fā)揮中樞節(jié)點(diǎn)協(xié)助分發(fā)與收集任務(wù)的功效；另一個(gè)原因是，某些節(jié)點(diǎn)作為任務(wù)分發(fā)者時(shí)，與其他節(jié)點(diǎn)的相遇次數(shù)過(guò)少或過(guò)于集中，不能滿足分配感知任務(wù)和接收感知任務(wù)結(jié)果的需要，換句話說(shuō)，就是受限于采用的數(shù)據(jù)集。那么這表明，移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)的規(guī)模越大，越能發(fā)揮HTA算法在縮短任務(wù)分發(fā)與收集階段時(shí)間消耗的優(yōu)勢(shì)。

5 結(jié)語(yǔ)

如何確定高效的任務(wù)分發(fā)與分配策略是移動(dòng)群智感知數(shù)據(jù)收集的核心問(wèn)題之一。本文將社交網(wǎng)絡(luò)分析中的中心性和社區(qū)概念與任務(wù)分配策略結(jié)合，提出一種最小化任務(wù)平均完成時(shí)間的基于中樞的多任務(wù)分配(HTA)算法。該算法的核心思想是經(jīng)過(guò)中樞節(jié)點(diǎn)選擇算法篩選出的部分節(jié)點(diǎn)被用于輔助分發(fā)和收集任務(wù)數(shù)據(jù)，并參與決策任務(wù)分配策略，以進(jìn)一步降低移動(dòng)群智感知任務(wù)在數(shù)據(jù)分發(fā)與收集上的時(shí)間消耗。實(shí)驗(yàn)結(jié)果顯示，本文提出的HTA算法比NTA算法平均縮短了任務(wù)完成時(shí)間24.9%，同時(shí)任務(wù)抵達(dá)率平均提高了150%。經(jīng)過(guò)對(duì)實(shí)驗(yàn)結(jié)果的進(jìn)一步分析，得出該算法在工作量小于1 000s的任務(wù)集下更能發(fā)揮優(yōu)勢(shì)。

此外，本文所提算法假設(shè)感知任務(wù)分配給不同移動(dòng)節(jié)點(diǎn)能夠得到相同結(jié)果。考慮到不同節(jié)點(diǎn)的活躍度、任務(wù)完成能力等會(huì)影響感知任務(wù)的完成質(zhì)量，以及感知任務(wù)可能對(duì)地理位置有要求，在實(shí)現(xiàn)最小化平均完成時(shí)間的同時(shí)，如何保證最低數(shù)據(jù)完成質(zhì)量要求將是下一步的研究重點(diǎn)。

)

[1] 趙東,馬華東.群智感知網(wǎng)絡(luò)的發(fā)展及挑戰(zhàn)[J].信息通信技術(shù),2014(5):66-70.(ZHAOD,MAHD.Developmentandchallengesofcrowdsensingnetworks[J].InformationandCommunicationsTechnologies, 2014(5): 66-70.)

[2]DUTTAP,AOKIP,KUMARN,etal.Commonsense:participatoryurbansensingusinganetworkofhandheldairqualitymonitors[C]//SenSys’ 09:Proceedingsofthe7thACMConferenceonEmbeddedNetworkedSensorSystems.NewYork:ACM, 2009: 349-350.

[3]KIMS,ROBSONC,ZIMMERMANT,etal.Creekwatch:pairingusefulnessandusabilityforsuccessfulcitizenscience[C]//CHI’ 11:Proceedingsofthe2011SIGCHIConferenceonHumanFactorsinComputingSystems.NewYork:ACM, 2011: 2125-2134.

[4]GANTIR,PHAMN,AHMADIH,etal.GreenGPS:aparticipatorysensingfuel-efficientmapsapplication[C]//MobiSys’ 10:Proceedingsofthe8thInternationalConferenceonMobileSystems,Applications,andServices.NewYork:ACM, 2010: 151-164.

[5]SIMOENSP,XIAOY,PILLAIP,etal.Scalablecrowdsourcingofvideofrommobiledevices[C]//MobiSys’ 13:Proceedingsofthe11thAnnualInternationalConferenceonMobileSystems,Applications,andServices.NewYork:ACM, 2013: 139-152.

[6]RANARK,CHOUCT,KANHERESS,etal.Ear-phone:anend-to-endparticipatoryurbannoisemappingsystem[C]//Proceedingsofthe9thACM/IEEEInternationalConferenceonInformationProcessinginSensorNetworks.NewYork:ACM, 2010: 105-116.

[7] 陳翔,徐佳,吳敏,等.基于社會(huì)行為分析的群智感知數(shù)據(jù)收集研究[J].計(jì)算機(jī)應(yīng)用研究,2015,32(12):3534-3541.(CHENX,XUJ,WUM,etal.Researchofdatacollectiontechnologyincrowdsensingbasedonsocialbehavioranalysis[J].ApplicationResearchofComputers, 2015, 32(12): 3534-3541.)

[8]PELUSIL,PASSARELLAA,CONTIM.Opportunisticnetwor-king:dataforwardingindisconnectedmobileAdHocnetworks[J].IEEECommunicationsMagazine, 2006, 44(11): 134-141.

[9]BULUTE,SZYMANSKIBK.Exploitingfriendshiprelationsforefficientroutinginmobilesocialnetworks[J].IEEETransactionsonParallelandDistributedSystems, 2012, 23(12): 2254-2265.

[10]SRINIVASANV,MOTANIM,OOIWT.Analysisandimplicationsofstudentcontactpatternsderivedfromcampusschedules[C]//Proceedingsofthe12thAnnualInternationalConferenceonMobileComputingandNetworking.NewYork:ACM, 2006: 86-97.

[11]BIGWOODG,HENDERSONT,REHUNATHAND,etal.CRAWDADdatasetst_andrews_sassy[DS/OL].[2011-06-03]http://crawdad.org/st_andrews/sassy/20110603.

[12]XIAOM,WUJ,HUANGL,etal.Multi-taskassignmentforcrowdsensinginmobilesocialnetworks[C]//INFOCOM2015:Proceedingsofthe2015IEEEConferenceonComputerCommunications.Piscataway,NJ:IEEE, 2015: 2227-2235.

[13]ZHANGX,NEGLIAG,KUROSEJ,etal.Performancemodelingofepidemicrouting[J].ComputerNetworks, 2007, 51(10): 2867-2891.

[14]FRENKIELRH,BADRINATHBR,BORRASJ,etal.Theinfostationschallenge:Balancingcostandubiquityindeliveringwirelessdata[J].IEEEPersonalCommunications, 2000, 7(2): 66-71.

[15]SPYROPOULOST,PSOUNISK,RAGHAVENDRACS.Sprayandwait:anefficientroutingschemeforintermittentlyconnectedmobilenetworks[C]//Proceedingsofthe2005ACMSIGCOMMWorkshoponDelay-TolerantNetworking.NewYork:ACM, 2005: 252-259.

[16] HUI P, CROWCROFT J, YONEKI E.BUBBLE rap: social-based forwarding in delay tolerant networks [C]// Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York: ACM, 2008: 241-250.

[17] ALLAHVERDI A, NG C, CHENG T, et al.A survey of scheduling problems with setup times or costs [J].European Journal of Operational Research, 2008, 187(3): 985-1032.

[18] CHENG T, SIN C.A state-of-the-art review of parallel-machine scheduling research [J].European Journal of Operational Research, 1990, 47(3): 271-292.

[19] LENSTRA J K, SHMOYS D B, TARDOS é.Approximation algorithms for scheduling unrelated parallel machines [J].Mathematical Programming, 1990, 46(1/2/3): 259-271.

[20] KEMPE D, KLEINBERG J, TARDOS é.Maximizing the spread of influence through a social network [C]// Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York: ACM, 2003: 137-146.

[21] WANG Y, CONG G, SONG G, et al.Community-based greedy algorithm for mining top-kinfluential nodes in mobile social networks [C]// Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York: ACM, 2010: 1039-1048.

This work is partially supported by the National Natural Science Foundation of China (61370065, 61502040), the Program for Excellent Talents in Beijing Municipality (2014000020124G099), the Open Program of the Beijing Key Laboratory of Internet Culture and Digital Dissemination (ICDD201406), the Program of Key Laboratory of Modern Measurement & Control Technology (Ministry of Education)/Beijing Key Laboratory of Electromechanical System Measurement and Control (KF20151123205).

XU Zhe, born in 1993, M.S.candidate.His research interests include crowdsensing.

LI Zhuo, born in 1983, Ph.D., lecturer.His research interests include mobile wireless networks, distributed computing.

CHEN Xin, born in 1965, Ph.D., professor.His research interests include network performance evaluation, network security.

Multi-task assignment algorithm for mobile crowdsensing

XU Zhe1, LI Zhuo1,2*, CHEN Xin1

(1.SchoolofComputerScience,BeijingInformationScienceandTechnologyUniversity,Beijing100101,China;2.BeijingKeyLaboratoryofInternetCultureandDigitalDissemination(BeijingInformationScienceandTechnologyUniversity),Beijing100101,China)

Data transmission based on opportunistic communication in mobile crowdsensing may take a long period of time.To address this issue, a new Hub-based multi-Task Assignment (HTA) algorithm was proposed.In this algorithm, some nodes were selected to perform as the hubs which could help the requester node to deliver the tasks, according to the different characteristics of the social relationship of the nodes in mobile networks.When the task requester encountered a hub node, the hub node itself and its slave nodes were assigned tasks.After that, the hub node would distribute the tasks to the salve nodes, and received the results from them.Simulations were conducted on The ONE simulator.Compared with the oNline Task Assignment (NTA) algorithm, HTA algorithm reduced the time cost by 24.9% on average and improved the task completion ratio by 150% on average.The experimental results demonstrate that HTA algorithm can accelerate the accomplishment speed of the task and reduce the time cost.

mobile crowdsensing; opportunistic communication; multi-task assignment; social relationship; hub node

2016-08-01;

2016-08-12。基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61370065, 61502040)；北京市優(yōu)秀人才培養(yǎng)資助青年骨干個(gè)人項(xiàng)目(2014000020124G099)；網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目(ICDD201406)；現(xiàn)代測(cè)控技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室/機(jī)電系統(tǒng)測(cè)控北京市重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目(KF20151123205)。

徐哲(1993—)，男，山東陽(yáng)谷人，碩士研究生，主要研究方向：移動(dòng)群智感知；李卓(1983—)，男，河南南陽(yáng)人，講師，博士，CCF會(huì)員，主要研究方向：移動(dòng)無(wú)線網(wǎng)絡(luò)、分布式計(jì)算；陳昕(1965—)，男，江西南昌人，教授，博士，CCF會(huì)員，主要研究方向：網(wǎng)絡(luò)性能評(píng)價(jià)、網(wǎng)絡(luò)安全。

1001-9081(2017)01-0018-06

10.11772/j.issn.1001-9081.2017.01.0018

TP393.01