一種范圍性空間眾包任務(wù)的在線分配優(yōu)化研究

高麗萍，戴 焜，高 麗

1(上海理工大學 光電信息與計算機工程學院，上海 200093)

2(復(fù)旦大學 上海數(shù)據(jù)科學重點實驗室，上海 200093)

3(上海理工大學 圖書館，上海 200093)E-mail：lipinggao@usst.edu.cn；2012701442@qq.com

1 引 言

近年來隨著人工智能領(lǐng)域的蓬勃發(fā)展，人們對于數(shù)據(jù)的需求日益增長，眾包技術(shù)在數(shù)據(jù)采集中的重要地位得到了廣泛的認可.空間眾包技術(shù)是眾包技術(shù)的一個重要分支[1，2]，空間眾包嚴格規(guī)定了參與者的完成任務(wù)的工作地點，將采集到的數(shù)據(jù)賦予了地域性更加符合實際情況[3]，例如滴滴打車客戶在指定某個地點叫車，在滴滴平臺上的司機看到任務(wù)后必須要到客戶所在地才可以完成任務(wù).隨著移動眾包感知技術(shù)(Mobile Crowdsourcing Sensing，MCS)的蓬勃發(fā)展，信息獲取手段的提升促進了在過去幾年里，越來越多的國內(nèi)外的學者開始對于空間眾包的分配問題進行研究，并且取得了巨大的成果[4-6].

空間眾包問題中主要有三個方面的研究內(nèi)容：任務(wù)分配、任務(wù)規(guī)劃和隱私保護.其中任務(wù)分配是保證眾包任務(wù)完成的核心技術(shù).任務(wù)分配指如何分配任務(wù)給工人來實現(xiàn)最大的任務(wù)分配數(shù)量和最小化任務(wù)成本，例如TGOA[2]算法將分配過程分成兩個階段，利用當前分配和當前的全局最優(yōu)解作對比來考慮是否會采用，期望通過每次分配局部最優(yōu)來接近全局最優(yōu).在分配模式上分為離線模式和在線模式兩種，離線模式是在已知任務(wù)信息和參與者信息進行分配，但是在響應(yīng)時間有要求的情況下并不適用(例如外賣行業(yè)等)，并且在現(xiàn)實的場景中分配平臺實現(xiàn)不可能了解到所有任務(wù)和工人的情況，所以離線模式只適合不需要高響應(yīng)的任務(wù)，在線模式是指任務(wù)信息和參與者信息事前并不知道，只有當任務(wù)或參與者到達時才會知道其信息，例如Peng Chen[7]提出的MQA算法，通過分析地區(qū)任務(wù)出現(xiàn)情況來預(yù)測任務(wù)在某個時間段出現(xiàn)的概率，從而提高工人可以連續(xù)完成多個任務(wù)的概率以實現(xiàn)提高任務(wù)分配數(shù)量的提高.

隨著人工智能的飛速發(fā)展，人們對于數(shù)據(jù)量的需求日益增長，傳統(tǒng)的派專人采集數(shù)據(jù)的形式已經(jīng)不能再滿足人們的需求，空間眾包利用MCS可以有效加快數(shù)據(jù)的采集速度和任務(wù)成本的控制，MCS技術(shù)是利用智能手機的傳感儀器在手機空閑時采集四周的傳感信息(如噪音強度，WIFI信號的強弱程度，交通擁堵情況等信息)，在成本上，傳統(tǒng)方法是雇傭?qū)I(yè)人士來采集信息，但是對于某些信息并不是一定要專業(yè)儀器才可以采集到，沒有必要聘用專業(yè)人士利用MCS平臺征集參與者利用參與者的智能手機同樣可以采集到相同的數(shù)據(jù)，在OMG算法基于MCS平臺通過反向競拍的方式將任務(wù)分配出去，參與者通過公開報價的方式去獲取任務(wù)，并且將分配過程分成了多個階段，每個階段錄取的參與者的任務(wù)平均報價都會比之前階段低，可以將任務(wù)成本有效降低，比使用傳統(tǒng)方法雇傭?qū)I(yè)人士去采集信息任務(wù)成本上要低很多，在時間上因為空間眾包平臺是利用網(wǎng)絡(luò)來征集這段時間在任務(wù)地點附近并且有空完成任務(wù)的人，與傳統(tǒng)方法去請人到工作地點采集要更加的快捷.

本課題組之前所提出的優(yōu)化范圍性空間眾包分配算法(Optimizing Scope Spatial Crowdsourcing Tasks Allocation algorithm，OSSA)在空間任務(wù)中工作地點加入了范圍屬性，在任務(wù)分配之前將任務(wù)優(yōu)化來消除任務(wù)冗余的問題，從而提高可分配任務(wù)數(shù)量.因為在感知信息采集時有時并不是采集一個地點的信息而實要采集一個范圍的信息，但是在采集范圍信息時，會出現(xiàn)任務(wù)范圍的重疊導致任務(wù)冗余的現(xiàn)象，在人少任務(wù)多的情況下，過多的任務(wù)冗余會導致分配數(shù)量的下降.OSSA在識別任務(wù)關(guān)系和分配任務(wù)時，會將任務(wù)隊列中所有任務(wù)進行比較，因此算法效率較低，本文所提出的OSSA改良算法的解決方法是將任務(wù)或工人的區(qū)域信息放入具有樹形結(jié)構(gòu)的任務(wù)樹中，并且在存儲時按照任務(wù)區(qū)域特性存儲信息，從而在檢索與到達任務(wù)或工人相關(guān)的任務(wù)信息或者工人信息時可以利用任務(wù)樹實現(xiàn)快速檢索.

本文首先介紹下OSSA算法，之后在OSSA算法的基礎(chǔ)上利用二叉樹將任務(wù)信息在空間上進行分類管理，當有新任務(wù)到達時，會利用之前存儲范圍信息的二叉樹快速檢索到與任務(wù)范圍有冗余的任務(wù)，從而減小問題的規(guī)模并且加快識別任務(wù)關(guān)系的速度，進一步提高算法分配效率.本文組織結(jié)構(gòu)如下：第二部分對研究背景與相關(guān)工作進行介紹；第三部介紹系統(tǒng)模型和問題定義；第四部分介紹利用二叉樹將空間任務(wù)分類的優(yōu)化算法并實例分析.第五部分，對設(shè)計的優(yōu)化算法通過隨機模擬工人和任務(wù)信息的數(shù)據(jù)，進行模擬仿真實驗并給出實驗分析結(jié)果，然后進行對比實驗來證明優(yōu)化算法的效果和正確性，第六部分為全文內(nèi)容的總結(jié)以及對未來工作的展望.

2 相關(guān)工作

空間眾包的優(yōu)化問題，在近些年來被越來越多的研究者所關(guān)注，在優(yōu)化方法中主要有三個目標，主要從分配數(shù)量，任務(wù)成本，任務(wù)質(zhì)量三個方面去考慮，分配數(shù)量主要是考慮如何將最終分配的任務(wù)個數(shù)最大化，例如(GeoCrowd：Enabling Query Answering with SpatialCrowdsourcing)Leyla Kazemi[3]提出的LLEP方法，該方法主要是將工人出現(xiàn)的密度分等級分配任務(wù)時根據(jù)任務(wù)出現(xiàn)地區(qū)等級的高低去決定優(yōu)先分配任務(wù)，來保證任務(wù)最大化分配數(shù)量.任務(wù)成本主要是優(yōu)化最終分配的任務(wù)的平均成本即參與者的報酬，例如Frugal-OMZ[1]算法和OMG[8]算法都是在通過參考上一個階段參與者產(chǎn)生價值與得到成本的比值作為閾值，將其作為下一個階段選擇參與者的指標，從而最大化降低任務(wù)完成成本，任務(wù)質(zhì)量是指參與者完成所分配任務(wù)的質(zhì)量，例如MELODY算法[9]采取分階段的方式，將分配過程分成多個階段，當工人完成任務(wù)后，會有一個質(zhì)量的反饋，算法基于EM(Expectation-Maximization algorithm)算法根據(jù)前幾次的所完成任務(wù)的質(zhì)量來預(yù)估下次質(zhì)量，根據(jù)工人質(zhì)量的預(yù)測將任務(wù)分配給工人.

在上述的優(yōu)化方法中，大多是從分配階段對算法進行優(yōu)化，任務(wù)優(yōu)化是近年來一個新的優(yōu)化方向，該方向是將任務(wù)之間的屬性關(guān)聯(lián)起來分析，任務(wù)不再是相互獨立存在的，在文獻[4]中總結(jié)了任務(wù)優(yōu)化的三個主要優(yōu)化方面，第一種任務(wù)的整合，是指將某些任務(wù)整合在一起交給參與者去完成[10-12]，例如Y.Liu[10]所提出的MT-MCMF算法通過分析參與者的行動軌跡將在將其軌跡范圍內(nèi)的任務(wù)整合交給參與者完成，實現(xiàn)最大化分配數(shù)量的目標.第二種是任務(wù)劃分[13-16]它是將任務(wù)與任務(wù)之間屬性的關(guān)聯(lián)或者是任務(wù)與工人之間屬性的關(guān)聯(lián)將任務(wù)進行劃分便于將來分配，減小分配的問題規(guī)模加快分配效率，例如文獻[11]中認為工人在分配任務(wù)時并不是和所有任務(wù)都是有關(guān)系的，其利用樹分解技術(shù)將有關(guān)系的工人或任務(wù)迅速找到，將那些不可能會出現(xiàn)在最優(yōu)方法中的枝杈剪除，從而實現(xiàn)最大化任務(wù)數(shù)量的目標.文獻[14]是利用分治的方法將僅和當前分配有關(guān)聯(lián)的任務(wù)和參與者找到，進行局部的分配，從而提高分配效率，第三種任務(wù)分解[17，18]，在文獻中為了完成復(fù)雜的問題將任務(wù)進行分解成一個個子任務(wù)，并將子任務(wù)分給參與者完成，最后將所有結(jié)果整合，從而實現(xiàn)提高任務(wù)的完成數(shù)量，文獻[17]研究了任務(wù)分解后的不同完成任務(wù)的方式如順序?qū)崿F(xiàn)、并行實現(xiàn)和分治實現(xiàn)，文獻[18]將任務(wù)分解應(yīng)用到了圖像采集中通過將任務(wù)分解讓參與者從自己的角度去采集圖像，所得到的結(jié)果是從不同角度拍攝的圖像從而增強了任務(wù)的完成質(zhì)量和所完成任務(wù)的容錯率.

上述在任務(wù)劃分的優(yōu)化方法大多是針對任務(wù)是一個地點通過圖的方式進行劃分，而本文是將帶有范圍屬性的空間眾包任務(wù)利用樹的技術(shù)將其分類，在優(yōu)化任務(wù)時通過其關(guān)系節(jié)點在樹中的位置推斷其與其他任務(wù)的關(guān)系，從而迅速找到與之相關(guān)聯(lián)的任務(wù)，減小尋找關(guān)聯(lián)任務(wù)的問題規(guī)模，提高分配任務(wù)的效率.

3 系統(tǒng)模型的定義和目標系統(tǒng)模型

本系統(tǒng)基于OSSA算法的基礎(chǔ)上加入了范圍任務(wù)樹，將會有一系列任務(wù)T{t1，t2…}和工人W{w1，w2…}到達系統(tǒng)中，任務(wù)內(nèi)容是工人利用MCS技術(shù)通過智能手機中的傳感器去采集目標區(qū)域中的相關(guān)感知信息(例如空氣質(zhì)量信息、交通信息、噪音信息等)，系統(tǒng)將會根據(jù)任務(wù)和工人信息給出分配結(jié)果，當任務(wù)t到達時，根據(jù)任務(wù)的范圍信息將任務(wù)放入范圍任務(wù)樹中，并且利用其所在樹節(jié)點的位置快速找到與之有關(guān)聯(lián)的任務(wù)，然后根據(jù)關(guān)聯(lián)任務(wù)與任務(wù)t在樹中節(jié)點的相對位置來推斷任務(wù)關(guān)系，在有工人w到達時，檢索范圍任務(wù)樹找出符合工人接受范圍的任務(wù)，如果發(fā)現(xiàn)符合條件的任務(wù)會立即分配，沒有符合的任務(wù)將等待符合的任務(wù)出現(xiàn)，直到等待時間超過工人的離開時間，根據(jù)工人所完成的任務(wù)給出合理報酬，本系統(tǒng)由于是采用MCS技術(shù)收集感知數(shù)據(jù)，所以系統(tǒng)中出現(xiàn)的任務(wù)都是同質(zhì)任務(wù).

1)模型基本定義

模型定義基本參照OSSA算法，其中加入了關(guān)于范圍任務(wù)二叉樹的基本定義.

定義1.(任務(wù)時效性)每個任務(wù)ti都存在一個開始時間ai和一個結(jié)束時間di，ai是指任務(wù)的到達時間的時間點，di是指任務(wù)的離開時間的時間點，任務(wù)只有在ai和di的閉區(qū)間內(nèi)才可以被分配.

定義2.(任務(wù)范圍)每個任務(wù)ti都有一個任務(wù)范圍，為了方便計算任務(wù)的范圍，將所有任務(wù)的范圍定義為一個矩形，由(ri，hi，wi)表示，ri是任務(wù)范圍的左頂點，hi是任務(wù)范圍的長度，wi是任務(wù)范圍的寬度.

定義3.(工人時效性)每個工人wi都存在到達時間ai和結(jié)束時間di，ai是工人進入分配平臺的時間點，di是工人離開分配平臺的時間點，工人只有在ai和di閉區(qū)間內(nèi)才可以接受任務(wù).

定義4.(工人可接受任務(wù)范圍)每個工人有一個可接受任務(wù)的范圍，為了方便計算可接受的范圍，將所有可接受范圍定義為一個矩形，用(ri，hi，wi)表示，ri是可接受范圍的左頂點，hi是可接受范圍的長度，wi是可接受范圍的寬度.

定義5.(工人報酬)每一個工人都有一個報價ci，系統(tǒng)會根據(jù)當時的分配情況給出工人報酬pi，為了保證工人權(quán)益即系統(tǒng)給出的報酬pi必須滿足pi≥ci.

定義6.(任務(wù)編號)每一個任務(wù)都有自己任務(wù)編號，m為任務(wù)類型號，n為子任務(wù)編號，當任務(wù)t根據(jù)其任務(wù)范圍分為了t1，t2時，其任務(wù)類型號為任務(wù)t的任務(wù)類型號，t1的子任務(wù)編號為1，t2的子任務(wù)編號為2，t的子任務(wù)編號為0.

定義7.(子任務(wù)標志位和子任務(wù)數(shù)量位)每一個根任務(wù)都有一個子任務(wù)標志位N和子任務(wù)數(shù)量位M，當有子任務(wù)分解出來時子任務(wù)的子任務(wù)編號是當前任務(wù)子任務(wù)標志位，并且更新根任務(wù)的子任務(wù)標志位加1，子任務(wù)數(shù)量位則是記錄根任務(wù)中未完成子任務(wù)的個數(shù).

定義8.(任務(wù)范圍的起始點與結(jié)束點)任務(wù)的起始點指的是任務(wù)范圍左上點即ri，而結(jié)束點為任務(wù)范圍的右下點ei即(ri.x+wi，ri.y+hi ).

定義9.(范圍任務(wù)樹節(jié)點)范圍任務(wù)樹的節(jié)點由坐標值信息、任務(wù)編號、坐標點類型和右子樹節(jié)點集合組成，其中的坐標值信息為坐標的x軸信息或y軸信息，任務(wù)編號即該節(jié)點所描述任務(wù)的任務(wù)編號，坐標點類型分為兩類S，E用來記錄該座標點是任務(wù)范圍的起始點還是結(jié)束點，右子樹節(jié)點集合記錄了在右子樹中只有起始坐標信息沒有結(jié)束坐標信息任務(wù)的任務(wù)編號集合.

定義10.(任務(wù)分配數(shù)量)

(1)

(2)

定義11.(任務(wù)平均成本)：

(3)

2)模型假設(shè)

假設(shè)1.每一個工人最多只可以分配一個任務(wù).

假設(shè)2.工人和任務(wù)的信息和到達的順序事先是未知的，只有到達以后才可以獲取任務(wù)和工人信息.

假設(shè)3.由于本文所討論的范圍任務(wù)都是基于MCS技術(shù)，所以工人在被分配任務(wù)時無需考慮工人能力問題，工人只要滿足上節(jié)的三點要求就可以分配任務(wù).

假設(shè)4.任務(wù)一旦被分配以后，工人一定可以完成任務(wù)，不存在中途放棄的情況.

假設(shè)5.工人不會拒絕系統(tǒng)分配給的任務(wù)，一旦分配任務(wù)會立即執(zhí)行任務(wù).

假設(shè)6.當工人到達時如果存在可分配的任務(wù)會立即分配可執(zhí)行任務(wù)不會等待.

假設(shè)7.工人的數(shù)量遠少于任務(wù)數(shù)量并且任務(wù)的分布是集中密集分布.

假設(shè)8.工人的報價是趨于穩(wěn)定的，不會出現(xiàn)不真實的報價不會出現(xiàn)較大浮動的.

3)模型目標

利用范圍任務(wù)樹劃分范圍任務(wù)，在對范圍任務(wù)檢測時可以利用任務(wù)在范圍任務(wù)樹存放任務(wù)信息的過程獲得的信息，快速鑒別那些可能會與任務(wù)有關(guān)聯(lián)的任務(wù)，再通過任務(wù)樹中節(jié)點的與關(guān)聯(lián)任務(wù)的節(jié)點的相對位置，推斷出任務(wù)的任務(wù)關(guān)系.然后利用OSSA的分配方法來解決任務(wù)冗余所帶來的問題.

4 基于樹形結(jié)構(gòu)優(yōu)化范圍空間眾包任務(wù)在線分配

由于本算法是基于OSSA算法改進而來，接下來會首先介紹OSSA算法的基本原理和流程，然后再介紹本算法對于OSSA算法的優(yōu)化部分.

4.1 OSSA算法

OSSA算法主要是通過任務(wù)關(guān)系來解決節(jié)約范圍性空間眾包任務(wù)冗余問題，節(jié)約人力從而提高任務(wù)的可分配數(shù)量的方法.

4.1.1 任務(wù)范圍冗余問題

任務(wù)范圍冗余問題是指：多個工人在完成多個任務(wù)時會出現(xiàn)其所負責的部分與其他工人負責的部分之間出現(xiàn)重疊和部分重疊的問題.在空間任務(wù)分配時，由于任務(wù)的發(fā)布方往往不是同一個機構(gòu)或客戶，所以會導致任務(wù)與任務(wù)之間雖然是獨立存在的，但是任務(wù)之間可能會存在空間依賴關(guān)系.在傳統(tǒng)的分配算法中并沒有考慮這個問題而是認為任務(wù)之間相互獨立，因此分配任務(wù)時會出現(xiàn)任務(wù)空間之間的冗余.

接下來會給出兩個案例來重點說明任務(wù)范圍冗余的所帶來的的人力浪費.

4.1.2 任務(wù)范圍冗余的場景分析

在這個小節(jié)里會介紹兩個案例來說明任務(wù)范圍冗余出現(xiàn)的兩種情況，分析范圍冗余對任務(wù)分配情況的影響.

任務(wù)范圍假設(shè)為矩形，范圍信息由左上角坐標信息和矩形的長和寬組成.

任務(wù)t1，t2，t3是采集任務(wù)范圍內(nèi)的感知信息，工人會利用MCS技術(shù)利用自己的智能手機的傳感器采集任務(wù)中的感知信息.

場景1.有兩個工人w1和w2和兩個任務(wù)t1和t2到達，兩個工人的可接受范圍為((0，0)，200，200)，任務(wù)t1的任務(wù)范圍為((50，50)，100，100)，任務(wù)t2的任務(wù)范圍為((100，100)，50，50)，工人w1和w2時間信息為(2，10)，w1的報價為1而w2的報價為5，任務(wù)t1的時間信息為(1，5)，任務(wù)t2的到達時間為(2，6)，詳情如圖1所示.

圖1 場景1和場景2中工人和任務(wù)的范圍信息

如圖1(a)所示當t1和t2到達時，w1和w2都可以分配t1和t2任務(wù)，在傳統(tǒng)分配算法中會直接分配任務(wù)給w1和w2，但是可以看出t1和t2之間的任務(wù)范圍并不是完全獨立的，而是存在交集部分的t2的任務(wù)面積是包含在t1中的，在之前的假設(shè)中工人可以完成任何任務(wù)，所以當在完成t1任務(wù)時，工人肯定會覆蓋t2的任務(wù)范圍，本來一個人就可以將t1和t2任務(wù)一起完成現(xiàn)在要兩個人才可以完成，因為t1和t2的任務(wù)范圍存在冗余部分(t2)，導致了分配時人力的浪費情況的出現(xiàn).

場景2.有三個工人w1，w2和w3和4個任務(wù)t1，t2，t3和t4，w1的時間信息為(3，10)，w2的時間信息為(4，5)，w3的時間信息為(5，5)，t1的時間信息為(0，5)，t2的時間信息為(1，4)，t3的時間信息為(2，6)，t4的時間信息為(2，6)，任務(wù)和工人的范圍信息見圖1.

如圖1(b)所示當任務(wù)到達時，t1，t2，t3分別在w1，w2和w3的到達范圍內(nèi)，所以w1，w2，w3可以分配t1，t2，t3，但是t4的任務(wù)范圍卻不被任何一個工人所覆蓋，所以在傳統(tǒng)的分配算法中，t4會被擱置直到有新的工人到達檢測是否覆蓋t4的任務(wù)范圍，但是通過圖2可以直觀的看到，t4任務(wù)雖然不在任何一個工人的范圍內(nèi)但是t4的部分任務(wù)范圍被其他三個任務(wù)的任務(wù)范圍包含，即當完成其他3個任務(wù)時3個工人已經(jīng)把t4任務(wù)的任務(wù)范圍覆蓋了，但是由于沒有一個工人可以覆蓋t4的整個范圍導致t4任務(wù)無法被分配，在這種情況中，任務(wù)之間雖然在任務(wù)范圍中沒有出現(xiàn)直接包含的情況，但是任務(wù)與任務(wù)之間存在部分覆蓋的情況，導致了任務(wù)范圍冗余情況的出現(xiàn)，可以想象在任務(wù)數(shù)量巨大的情況下，少量的部分覆蓋也會造成大面積的范圍冗余情況的出現(xiàn)，從而出現(xiàn)分配時分配任務(wù)數(shù)量的下降.

圖2 實例分析場景

4.2 任務(wù)關(guān)系和節(jié)點關(guān)系

為了消除任務(wù)范圍之間的關(guān)系，接下來會介紹三種任務(wù)之間的關(guān)系.

1)獨立關(guān)系：存在兩個范圍任務(wù)t1和t2，其任務(wù)范圍為S1和S2，若S1∩S2=?則t1和t2屬于獨立關(guān)系.

2)相交關(guān)系：存在兩個范圍任務(wù)t1和t2，其任務(wù)范圍為S1和S2，若S1∩S2=S3≠?且S3≠S1和S3≠S1，則t1和t2屬于相交關(guān)系.

3)包含關(guān)系：存在兩個范圍任務(wù)t1和t2，其任務(wù)范圍為S1和S2，若S1∩S2=S2，則任務(wù)t1和t2屬于包含關(guān)系.

4)被包含關(guān)系：存在兩個范圍任務(wù)t1和t2，其任務(wù)范圍為S1和S2，若S1∩S2=S1，則任務(wù)t1和任務(wù)t2屬于被包含關(guān)系.

如圖1(a)所示，任務(wù)t1與t2在任務(wù)范圍上存在交集部分t2，根據(jù)上文的任務(wù)關(guān)系定義，t1與t2的任務(wù)范圍交集為t2，所以t1對于t2是包含關(guān)系，t2對于t1是被包含關(guān)系，如圖1(b)所示，任務(wù)t1和t4也存在交集部分，但是交集部分不等于t1或t4的任務(wù)范圍，所以t1和t4是相交關(guān)系，在圖1(b)中任務(wù)t1和t2的任務(wù)范圍不存在交集，所以t1和t2是獨立關(guān)系.

從上述任務(wù)關(guān)系說明中可以看出在相交關(guān)系和包含與被包含關(guān)系中存在任務(wù)范圍冗余的問題，所以O(shè)SSA算法的目標是通過將任務(wù)整合和分解的手段，將每一個任務(wù)和除它外的所有任務(wù)的任務(wù)關(guān)系轉(zhuǎn)化為獨立關(guān)系從而消除任務(wù)范圍冗余的問題.

4.3 OSSA算法設(shè)計

為了跟好的理解算法，首先會在表1中介紹算法中會出現(xiàn)的變量以及變量的含義：

變量名含 義tid表示任務(wù)編號tm,tn表示任務(wù)的類型號和子任務(wù)編號Wi,ti,pi分別表示工人i,任務(wù)i和工人i的報價.ri,hi,wi 分別表示范圍的起始點,范圍的高度和范圍的寬度.Ti.include表示任務(wù)i的包含集合存放與任務(wù)i有包含關(guān)系的任務(wù)id.ti.included表示任務(wù)i的被包含集合存放與任務(wù)i有被包含關(guān)系的任務(wù)id.ti.intersect表示任務(wù)i的相交集合存放與任務(wù)i有相交關(guān)系的任務(wù)id.Taskset表示任務(wù)集合將任務(wù)與其任務(wù)id映射表.Swi表示工人i可接受范圍Sti表示任務(wù)i的任務(wù)范圍wqueue表示已到達但沒有分配任務(wù)的工人隊列tqueue表示已到達但沒有執(zhí)行的任務(wù)隊列cur_time表示當前時間點

OSSA算法具體內(nèi)容：

算法1.OSSA

n=0

ui arrive

Su=compterarea(ui)

if T !=cur_time：

detect_time(cur_time)

sign=False

if(type(ui)==Worker)

for t in tqueue：

if St∩Su=Stand count(t.include)>=count(task.include)：

if count(t.include)==count(task.include)：

if count(t.intersect)> count(task.intersect)：continue

pi=area_salary(t.id，u)

task=t

sign=True

if not sign：

wqueue.add(u)

else：

u.id=n

n+=1

Taskset[id]=u

task_relation(u.id)

if u.included !=?

for w in wqueue：

if Sw∩Su=Suand minprice > cw：

selectedworker=w

pw=area_salary(u)

minprice=cw

sign=True

if not sign：

tqueue.add(u.id)

else：

delete_relation(u.id)

wqueue.remove(selectedworker)

Taskset.pop(u)

在OSSA算法中，如果是任務(wù)到達時會首先檢測該任務(wù)和任務(wù)隊列中的任務(wù)之間的關(guān)系，如果該任務(wù)與某一任務(wù)存在被包含關(guān)系(即該任務(wù)的任務(wù)范圍與其他任務(wù)完全重疊)，則不會將任務(wù)放入任務(wù)隊列中，若沒有存在任務(wù)與其有被包含關(guān)系則將其放入任務(wù)隊列中，在識別任務(wù)關(guān)系時，會將存在關(guān)系的任務(wù)根據(jù)關(guān)系類型分別儲存在不同關(guān)系隊列中，方便分配任務(wù)時方便整合任務(wù)內(nèi)容，當有任務(wù)離開任務(wù)范圍分解或被分配時會根據(jù)其關(guān)系隊列重新更新與之有范圍關(guān)聯(lián)的任務(wù)的關(guān)系隊列，當工人到達時會根據(jù)工人的工作范圍從任務(wù)隊列中搜索可完成的任務(wù)，然后將任務(wù)按照所包含的任務(wù)個數(shù)將其重新擺列，挑選出包含任務(wù)最多的任務(wù)交給工人完成，工人所獲得的報酬會根據(jù)任務(wù)范圍的大小和其所包含任務(wù)個數(shù)和其占包含任務(wù)的任務(wù)范圍的比例綜合計算，通過OSSA算法可以將范圍任務(wù)有效優(yōu)化，使得分配給工人的任務(wù)是在當時階段完全獨立的任務(wù)，有效減輕了任務(wù)冗余所帶來的問題.

在OSSA算法中，在對任務(wù)的任務(wù)關(guān)系初始判斷時，會將任務(wù)隊列中每一個任務(wù)都會進行判斷然后得出該任務(wù)與其他任務(wù)之間的關(guān)系，當任務(wù)數(shù)量越來越多時，關(guān)系判斷時間會線性增長，會極大降低算法的效率，接下來會介紹本算法如何利用空間任務(wù)樹將任務(wù)進行劃分，從而有效的找出可能存在非獨立關(guān)系的任務(wù).

4.4 改進算法

改進算法主要是在任務(wù)關(guān)系判斷環(huán)節(jié)對OSSA算法進行修改，使其可以快速將可能存在關(guān)系的任務(wù)從任務(wù)隊列中劃分并識別出任務(wù)關(guān)系.

下面會列出改進算法中會出現(xiàn)的變量和變量的意義

變量名含 義id分別表示任務(wù)編號tm,tn表示任務(wù)編號中的任務(wù)類型號和子任務(wù)編號XTree表示任務(wù)在X軸投影的任務(wù)樹YTree表示任務(wù)在Y軸投影的任務(wù)樹node表示樹的節(jié)點node.type表示樹中存放坐標的含義,S代表該節(jié)點表示任務(wù)范圍的初始點,E代表該節(jié)點表示任務(wù)范圍的結(jié)束點node.value表示節(jié)點存放的坐標值node.leftid存放了該節(jié)點右子樹中只有任務(wù)范圍的初始點卻沒有終結(jié)點所代表任務(wù)的任務(wù)編號node.kind表示節(jié)點種類,T代表存放的是任務(wù)信息,W代表存放的是工人信息node.id表示樹所代表任務(wù)或工人的編號Tnode.left表示節(jié)點的左節(jié)點Tnode.right表示節(jié)點的右節(jié)點XTree.firstYTree.first表示X軸投影樹的根節(jié)點表示Y軸投影樹的根節(jié)點

改進算法具體內(nèi)容：

算法2.Improved OSSA

n=0

ui arrive

detect_time(cur_time)

sign = False

if(type(ui)==Worker)

updateTree(ui)

if ui.include==null

wqueue.add(ui)

else

queue=ui.include

task=null

max=0

for t in queue

if t.included !=null

continue

if count(t.include)>max

max=count(t.include)

task=t

if task

pi=area_salary(task.tid，u)

deletenode(task)

deletenode(ui)

else

update(ui)

for node in ui.included

if node.kind==w&&minprice>=c

selectedworker=workerset.get(node.id)

minprice=c

sign=true

if sign

pi=area_salary(ui，selectworker)

wqueue.remove(selectworker)

deletenode(ui)

deleternode(selectworker)

在改進算法中，在分配方面沿用了OSSA的機制，但是在任務(wù)關(guān)系識別方面，使用了范圍任務(wù)樹將范圍信息存儲到樹中，當工人或任務(wù)到達時會首先將其范圍信息放入到樹中，根據(jù)其所屬節(jié)點在范圍關(guān)系樹的相對位置，判別出任務(wù)關(guān)系，在每次分配完畢后會將已分配的節(jié)點在關(guān)系樹中進行更新，將已分配的節(jié)點從樹中剪除.

算法3.updateTree

relationX=updateX(ui)

relationY=updateY(ui)

if type(ui)=W

for id，kind in relationX

if kind !=1

continue

if relationY.get(id)!=null and realtionY[id]==1

if id in taskset

ui.include.add(id)

else

for id，kind in relationX

if relationY.get(id)==null

continue

if kind==0 and id in taskset

ui.intersct.add(id)

taskset.get(id).intersect.add(id)

if kind==1

if relationY[id]==1

ui.included.add(id)

if id in taskset.key

taskset.get(id).include(ui.id)

else

workerset.get(id).include(ui.id)

else

if id in taskset

ui.intersect.add(id)

taskset.get(id).intersect.add(ui.id)

if kind==2

if relationY[id]==2

if id in taskset.key

ui.include.add(id)

taskset.get(id).included(id)

else

if id in taskset

ui.intersect.add(id)

在改良算法中，工人和任務(wù)之間也可以用任務(wù)范圍確定關(guān)系，但是工人與任務(wù)之間只有包含關(guān)系，因為只有當工人的工作范圍完全覆蓋了任務(wù)范圍才可以完成，所以工人與任務(wù)之間的相交關(guān)系和被包含關(guān)系沒有任何意義.首先算法會將任務(wù)/工人的信息分別放入代表X投影和Y投影的范圍任務(wù)樹中，然后根據(jù)從返回的任務(wù)節(jié)點在兩個樹中的關(guān)系，可以推斷出任務(wù)與現(xiàn)有任務(wù)之間的關(guān)系或工人與任務(wù)之間的關(guān)系，節(jié)點關(guān)系和任務(wù)關(guān)系的映射見表1.然后將識別好的關(guān)系放入關(guān)系隊列中.

表1 節(jié)點關(guān)系與任務(wù)關(guān)系映射表

算法4.UpdateX/uUpdateY

snode←(ui.id，S，ui.x，null，ui.type )

enode←(ui.id，S，ui.x+wi，null，ui.type)

set1=updateNode(ui)

set2=updateNode(ui)

detect_relative(set1，set2-set1)

在UpdateX或UpadteY函數(shù)中，會根據(jù)任務(wù)或工人信息計算其范圍的起始點和結(jié)束點在x軸和y軸的坐標，然后初始化樹節(jié)點，節(jié)點編號為任務(wù)或工人編號，set1和set2為比放入小于起始點和結(jié)束點的節(jié)點id，然后通過這些信息得出任務(wù)節(jié)點在樹中的節(jié)點關(guān)系.

算法5.UpdateNode

node put in Tree

root=Tree.first

tasked=[]

prenode=null

while root

prenode=root

if root.value<=node.value

tasked.add(root.id)

for id in root.leftid

tasked.add(id)

root=root.right

if root.value>node.value

root=root.left

if prenode.value

for id in prenode.leftid

if taskid.exist(id)

tasked.remove(id)

else

tasked.append(id)

prenode.right=node

else

prenode.left=node

if node.type==E

taskset.remove(node.id)

return tasked

在updateNode函數(shù)中，會根據(jù)節(jié)點中的值放入相應(yīng)位置，首先插入節(jié)點會和樹的頭節(jié)點比較如果比插入節(jié)點的值要小，下次會和該節(jié)點的左節(jié)點比較，否則下一次和該節(jié)點的右節(jié)點比較，直到比較的節(jié)點為空為止，則將插入節(jié)點信息覆蓋該空節(jié)點，另外在整個插入過程中遇到比自己值小的節(jié)點會將其id記錄下來并且將其右子樹中的節(jié)點放入，每一次遇到比自己大的節(jié)點，該節(jié)點會將其id記錄在自己leftid集合中，函數(shù)最后將記錄的id集合返回.

算法6.detect_relative(set1，set2-)

nodeRelationship={}

occur1，occur2={}，{}

for id in set1

if occur1.get(id)==null

occur1[id]=0

occur1[id]+=1

for id in set2

if occur2.get(id )==null

occur2[id]=0

occur2[id]+=1

for key，count in occur1

if count==2

continue

if occur2.get(key)!=null

occur2[id]=0

nodeRelationship=0

else

nodeRelationship=1

for key，count in occur2

if count==0

continue

if count==1

nodeRelationship[id]=0

else

nodeRelationship[id]=2

return nodeRelationship

在該函數(shù)的作用是將任務(wù)范圍的起始點和結(jié)束點在樹中返回的id集合進行分析，得出其與其他任務(wù)在x軸或y軸上的關(guān)系，set1代表的是起始點返回的id集合，set2代表的是結(jié)束點返回的id集合與set1的差集(即將出現(xiàn)在set1中的元素刪除)，首先會分別記錄在兩個集合中id出現(xiàn)的次數(shù)，如果在set1中出現(xiàn)只有一次而在set2中出現(xiàn)過則為相交關(guān)系用0代表，反之若在set2中沒有出現(xiàn)則為被包含關(guān)系用1代表，然后檢查在set2中節(jié)點出現(xiàn)次數(shù)如果只出現(xiàn)一次則為相交關(guān)系如果出現(xiàn)過兩次則為被包含關(guān)系用2代表，最后返回記錄節(jié)點關(guān)系的字典.

算法7.deletenode

if type(ui)==w

for id in ui.include

taskset.get(id).included.remove(id)

else

for id in ui.include

taskset.get(id).included.remove(ui.id)

deletenode(ui)

for id in ui.included

if id in taskset

taskset.get(id).include.remove(id)

for id in ui.intersect

deleteAllraltionship(taskset.get(id))

nodes=descompose(ui，taskset.get(id))

deleteFromTree(taskset.get(id))

for n in nodes

update(n)

snode=taskset.get(ui.id).snodeX

enode=taskset.get(ui.id).enodeX

deletenodefromTree(snode)

deleternodefromTree(enode)

snode=taskset.get(ui.id).snodeY

enode=taskset.get(ui.id).enodeY

deletenodefromTree(snode)

deleternodefromTree(enode)

該函數(shù)的目的是將已分配的任務(wù)和工人刪除其在算法中的所有信息，首先會判斷是工人還是任務(wù)，如果刪除的工人，則將其所包含任務(wù)的被包含隊列里把其id刪除，如果刪除的任務(wù)，首先將其id從其他任務(wù)的包含隊列中刪除，然后遍歷其相交隊列，將與其相交的任務(wù)去除相交部分，然后根據(jù)具體的相交情況，將剩余任務(wù)區(qū)域分解成若干個新的任務(wù)放入任務(wù)樹中，將被分解的任務(wù)從樹中刪除，最后將被其所包含的任務(wù)從樹中刪除，最后將該任務(wù)在任務(wù)樹中刪除.

算法8.deletenodefromTree

delnode=nodes.get(id)

leftnodes，newleftnodess=delnode.leftid，null

leftnode=delnode.left

While delnode.right and delnode.right.right

rnode=delnode.right

newleftnodes=rnode.leftid

rnode.leftid=leftnodes

newleftnode=rnode.left

rnode.left=leftnode

leftnode=newleftnode

leftnodes=newleftnodes

delnode=delnode.right

if delnode.right.left

swap(delnode.right.left，delnode)

deletenodefromTree(delnode)

else

delnode.right.leftid=leftnodes

delnode.left=leftnode

該函數(shù)用來將任務(wù)節(jié)點從任務(wù)樹中刪除，首先會檢查該節(jié)點的右節(jié)點是否存在如果不存在就尋找其左節(jié)點存在則由其左節(jié)點來代替其位置如果不存在則返回，如果右節(jié)點存在則檢查其節(jié)點的右節(jié)點是否存在，如果存在則將右節(jié)點信息覆蓋要刪除的節(jié)點將將要刪除節(jié)點的leftid賦給右節(jié)點，然后利用同樣的方法將原來右節(jié)點從樹中刪除一直遞歸直到不符合條件為止，若不存在就判斷該節(jié)點的左節(jié)點是否存在如果存在則將左節(jié)點來覆蓋刪除節(jié)點信息，然后將原來的左節(jié)點放入函數(shù)中遞歸，如果左節(jié)點不存在則將右節(jié)點替換要刪除的節(jié)點.

4.5 實例分析

首先用通常的分配算法，認為任務(wù)之間是相互獨立存在的，對任務(wù)進行分配，然后會使用改良算法對任務(wù)進行分配，由于改良算法是對OSSA算法中任務(wù)關(guān)系識別環(huán)節(jié)的改進，而在分配任務(wù)和工人報酬方面依然是沿用OSSA算法的方法，所以在實例分析中會在場景里放入先后出現(xiàn)的任務(wù)，然后利用改進算法來識別任務(wù)之間的關(guān)系，來證明改良算法對于任務(wù)關(guān)系識別的可行性.

實例說明假設(shè)有3個基于MCS完成的任務(wù)來自不同的機構(gòu)是采集三個不同區(qū)域的信息來做相關(guān)工作，為了方便計算將任務(wù)范圍簡單定義成一個矩形區(qū)域，所有任務(wù)的發(fā)生區(qū)域簡單定義為一個XY軸坐標組成的區(qū)域，任務(wù)范圍信息由矩形的左上角坐標和矩形的長寬構(gòu)成，任務(wù)信息由任務(wù)范圍信息和任務(wù)的報價組成，工人之間的采集工具(智能手機)可采集信息完全相同.

在圖2中有t1，t2，t3三個任務(wù)，它們是依次出現(xiàn)的，任務(wù)信息如下：t1(5，3，4，5，4)、t2(8，4，15，12，5)、t3(10，4，12，，6，6)，任務(wù)出現(xiàn)順序是t2、t1、t3，t1和t3是采集區(qū)域的噪音信息而t2是采集WIFI信息強弱信息，在貪心算法和TGOA算法中認為三個任務(wù)之間是獨立的，會將三個任務(wù)分配給三個不同的人完成，但是可以從圖2看出t2和t3之間是存在范圍重疊的(即t2和t3之間存在任務(wù)冗余問題)，而t2和t3的任務(wù)內(nèi)容雖然不同但是在任務(wù)是基于MCS技術(shù)，是利用手機中的傳感器來收集區(qū)域的信息，所以在分配給t2任務(wù)的功能的工人其實在完成過程中也會經(jīng)過t3的任務(wù)區(qū)域，由于在前提假設(shè)中工人之間的手機可采集的信息是相同的，則完成t2任務(wù)的工人其實完全有能力完成t3任務(wù)，由于任務(wù)冗余明明只有2個人完成的任務(wù)現(xiàn)在需要3個人完成.

接下來會利用改良算法辨識任務(wù)之間的關(guān)系，證明改良算法對于任務(wù)識別結(jié)果是和使用OSSA算法一致的，另外通過例子來進一步理解改良算法的基本流程.

一開始t2到達時，將其任務(wù)區(qū)域信息放入空間樹中，放入后的具體結(jié)果見圖3(a)，由于是第一個到達任務(wù)所以沒有任何任務(wù)關(guān)系產(chǎn)生.

圖3 各任務(wù)到達后樹的情況

t1到達后將空間樹的信息放入其中，放入后詳細情況見圖3(b)，在存放t1的初始點x坐標時，首先和t2的初始節(jié)點比較，發(fā)現(xiàn)小于節(jié)點的值所以將其放入頭節(jié)點的左子樹，并且頭節(jié)點會記錄放入其左子樹的任務(wù)id(即t2的id)，由于沒有值小于t1初始節(jié)點的坐標值所以返回集合為空，而放入t1的結(jié)束點的坐標時，由于t2的初始節(jié)點的坐標小于其只，所以會返回一個t2的id，所以t1和t2在x軸投影上的關(guān)系是相交關(guān)系.同理在放入t1的初始點的y坐標時，由于沒有比其小的節(jié)點返回為空，而放入t1的結(jié)束點的坐標時會發(fā)現(xiàn)只有t2的初始節(jié)點的值比起小，所以會返回一個t2的id，所以t1和t2在y軸的投影關(guān)系是相交.通過綜合x，y軸的投影關(guān)系得出t1和t2是相交關(guān)系.

t3到達后將其信息放入樹中，放入后的詳細情況見圖3(c)，在存放t3初始點的x坐標時，由于t1的兩個節(jié)點的x坐標都小于它，而t2只有初始節(jié)點小于它，所以返回的是兩個t1的id和一個t2的id，同理在放入t3結(jié)束點的x坐標時會返回相同的結(jié)果在任務(wù)識別中由于t1的id出現(xiàn)了兩次在set1中，所以t3和t1在x軸投影上沒有關(guān)系，而set2是將結(jié)束點返回結(jié)合中刪除set1的元素，由于set1和set2相同所以set2為空，根據(jù)算法可以的出t3和t2是包含與被包含關(guān)系，當放入t3初始點的有坐標時，會發(fā)現(xiàn)t2的初始節(jié)點坐標和其相同而t1的初始節(jié)點坐標小于它所以會返回一個t1的id和一個t2的id，同理放入t3結(jié)束點y坐標時會返回相同結(jié)果，由于兩個點返回的結(jié)果一致所以set2為空，根據(jù)算法得出t3與t1和t2在y軸投影是包含與被包含關(guān)系，由于t1和t3在x軸投影沒有關(guān)系所以t1和t3是獨立關(guān)系，而t2和t3在x，y軸都是包含關(guān)系所以t2和t3是包含關(guān)系.

從這個例子中可以了解改良算法對于任務(wù)關(guān)系識別上得出的結(jié)果與使用OSSA算法得出的結(jié)果是相同，在改良算法中，將三個任務(wù)放入了兩個任務(wù)樹中，在處理工程中發(fā)現(xiàn)了t2和t3在兩個樹中的坐標信息同時出現(xiàn)包含關(guān)系，則t2與t3的關(guān)系時包含關(guān)系，則會將t2和t3合成一個任務(wù)，從而避免了任務(wù)冗余問題帶來的人力浪費的問題，另外改良算法在確認任務(wù)關(guān)系時，并沒有像OSSA算法中遍歷任務(wù)隊列中的任務(wù)確認任務(wù)之間的關(guān)系，而是利用任務(wù)樹坐標的情況迅速找到與其任務(wù)范圍相關(guān)的任務(wù)確認其任務(wù)關(guān)系.

5 實驗分析

本節(jié)首先會將OSSA算法與TGOA算法和貪心算法在可分配任務(wù)數(shù)量和任務(wù)成本上進行對比，證明改良算法所改良的OSSA算法的正確性和可行性.然后將改良算法與OSSA算法處理時間進行對比，比較兩種算法的執(zhí)行速度，證明改良算法對執(zhí)行效率的改良.實驗設(shè)備介紹：實驗將在win10系統(tǒng)下運行，實驗的程序是由python語言編寫，編譯平臺為pycharm，電腦cpu為 i7-6700，內(nèi)存為16g.

實驗數(shù)據(jù)：整個場景為300*300的平面假設(shè)有工人500人其報價在[1，10]之間隨機產(chǎn)生，工人出現(xiàn)地點在全圖范圍內(nèi)隨機產(chǎn)生，工人可接受范圍在[1，100]*[1，100]區(qū)間隨機產(chǎn)生，任務(wù)個數(shù)在800-1500之間每隔100取一次，任務(wù)地點隨機產(chǎn)生，任務(wù)范圍在[1-50]*[1-50]區(qū)間隨機產(chǎn)生.

實驗1.將固定工作人員數(shù)量并逐漸增加了任務(wù)數(shù)量，以驗證OSSA使用任務(wù)優(yōu)化后的任務(wù)數(shù)量是否大于沒有任務(wù)優(yōu)化的算法數(shù)量.由于該算法針對的是任務(wù)較少的工作人員，因此任務(wù)數(shù)量將從超過工作人員數(shù)量開始.因此，實驗設(shè)計人員的數(shù)量逐漸從800增加到觀察完成任務(wù).在本實驗中，OSSA完成的任務(wù)數(shù)和沒有任務(wù)優(yōu)化的分配算法僅限于在給定數(shù)量的任務(wù)下每個工作人員的一個任務(wù).從圖4中可以看出，OSSA算法與其他兩種算法隨著任務(wù)數(shù)量的增加可分配任務(wù)數(shù)量之間的差距會逐漸增大，由于任務(wù)冗余會造成人力的浪費，在工人只能分配一次的情況下，由于對任務(wù)本身范圍的優(yōu)化使得最大可分配數(shù)量得到提高.

圖4 任務(wù)完成數(shù)對比

實驗2.當固定工人數(shù)量逐漸增加時，驗證OSSA算法的任務(wù)平均價格不會超過未使用任務(wù)優(yōu)化算法的任務(wù)平均價格.從圖5可以看出，任務(wù)的平均價格隨著任務(wù)數(shù)量的增加而逐漸減少.由于數(shù)據(jù)的隨機性，其他兩種算法上下波動，但從未低于OSSA算法的平均價格.當任務(wù)范圍內(nèi)的沖突數(shù)量不斷增加時，包含任務(wù)和交叉任務(wù)的改良任務(wù)的平均價格低于當時的單個任務(wù)價格.因此，當沖突次數(shù)逐漸增加時，已完成任務(wù)的平均價格將逐漸下降.

圖5 任務(wù)平均價格對比

通過上面兩組實驗可以證明OSSA算法在解決具有范圍性任務(wù)分配問題上的可行性和正確性.

實驗3.將工人個數(shù)固定逐漸增加任務(wù)個數(shù)，對比OSSA與改良算法之間在運行效率，從圖6中可以看出當OSSA算法與改良算法隨著任務(wù)個數(shù)的增多，改良算法與OSSA之間的運行時間逐漸增大，這是由于當任務(wù)個數(shù)增多時，OSSA算法在工人到達或任務(wù)到達檢查關(guān)系時，是將任務(wù)隊列或工人隊列中的信息拿出來一個個與到達工人或任務(wù)的區(qū)域信息對比，而在改良算法中當有工人或者任務(wù)到達時會將任務(wù)區(qū)域信息在任務(wù)樹中進行檢索查看是否有相關(guān)的信息，而不是與現(xiàn)有數(shù)據(jù)一個個對比獲得，所以當任務(wù)數(shù)量增大時改良算法與OSSA算法運行時間的差距會逐漸增大.

圖6 OSSA與改良算法運行時間對比圖

改良算法主要是改動了OSSA算法中任務(wù)關(guān)系識別過程，在時間上在OSSA算法中會將任務(wù)放入任務(wù)隊列中將任務(wù)與任務(wù)隊列中的其他任務(wù)放入任務(wù)信息中，在判斷任務(wù)之間的關(guān)系時，會遍歷整個任務(wù)隊列得出任務(wù)之間的關(guān)系所以時間復(fù)雜度是O(m*n)，n為現(xiàn)有任務(wù)隊列中的任務(wù)個數(shù)，m為與任務(wù)存在任務(wù)范圍冗余任務(wù)的個數(shù)，而改良算法中會額外建立一個空間任務(wù)樹來存放任務(wù)范圍信息，利用樹形結(jié)構(gòu)可以迅速索引到與自己任務(wù)范圍相關(guān)的任務(wù)，其時間復(fù)雜度為O(mlogn)，改良算法通過增加空間任務(wù)樹在現(xiàn)有任務(wù)的任務(wù)范圍中建立索引，加快找到新到達任務(wù)與之在任務(wù)范圍有關(guān)系的任務(wù)判斷任務(wù)關(guān)系，因此具有更高的執(zhí)行效率.

6 總結(jié)與展望

在改良算法中針對OSSA算法在搜索任務(wù)關(guān)系過程進行優(yōu)化，使得識別任務(wù)關(guān)系不用和現(xiàn)有任務(wù)一一對比，而是將任務(wù)信息放入空間任務(wù)樹中，檢查代表任務(wù)區(qū)域的兩個節(jié)點與其他節(jié)點之間的關(guān)系來推斷出任務(wù)關(guān)系，從而加快了任務(wù)關(guān)系識別速度，通過對比實驗可以證明改良算法的識別速度在任務(wù)多的情況下由于原有算法，而且因為其他環(huán)節(jié)是與OSSA算法一致的，所以最后的分配結(jié)果是不會改變.

改良算法由于是利用樹形結(jié)果進行優(yōu)化搜索，在一些極端情況下會出現(xiàn)線性搜索的結(jié)果，對于這種情況可能會在未來通過某種機制對這種情況進行改進.

在算法中，假設(shè)了任務(wù)是同質(zhì)任務(wù)(即工人有能力完成所有類型的任務(wù))，但是在現(xiàn)實中由于人們智能手機的不同所能采集的感知信息是不同的，為了更加符合現(xiàn)實需求，接下來會主要去研究工人所能完成任務(wù)有差異的情況下如何去避免任務(wù)范圍冗余的問題.