一種范圍性空間眾包任務的在線分配優化研究

高麗萍，戴 焜，高 麗

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

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

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

1 引 言

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

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

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

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

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

2 相關工作

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

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

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

3 系統模型的定義和目標系統模型

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

1)模型基本定義

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

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

(3)

2)模型假設

假設1.每一個工人最多只可以分配一個任務.

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

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

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

假設5.工人不會拒絕系統分配給的任務，一旦分配任務會立即執行任務.

假設6.當工人到達時如果存在可分配的任務會立即分配可執行任務不會等待.

假設7.工人的數量遠少于任務數量并且任務的分布是集中密集分布.

假設8.工人的報價是趨于穩定的，不會出現不真實的報價不會出現較大浮動的.

3)模型目標

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

4 基于樹形結構優化范圍空間眾包任務在線分配

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

4.1 OSSA算法

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

4.1.1 任務范圍冗余問題

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

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

4.1.2 任務范圍冗余的場景分析

在這個小節里會介紹兩個案例來說明任務范圍冗余出現的兩種情況，分析范圍冗余對任務分配情況的影響.

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

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

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

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

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

場景2.有三個工人w1，w2和w3和4個任務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)，任務和工人的范圍信息見圖1.

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

圖2 實例分析場景

4.2 任務關系和節點關系

為了消除任務范圍之間的關系，接下來會介紹三種任務之間的關系.

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

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

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

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

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

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

4.3 OSSA算法設計

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

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

OSSA算法具體內容：

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

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

4.4 改進算法

改進算法主要是在任務關系判斷環節對OSSA算法進行修改，使其可以快速將可能存在關系的任務從任務隊列中劃分并識別出任務關系.

下面會列出改進算法中會出現的變量和變量的意義

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

改進算法具體內容：

算法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的機制，但是在任務關系識別方面，使用了范圍任務樹將范圍信息存儲到樹中，當工人或任務到達時會首先將其范圍信息放入到樹中，根據其所屬節點在范圍關系樹的相對位置，判別出任務關系，在每次分配完畢后會將已分配的節點在關系樹中進行更新，將已分配的節點從樹中剪除.

算法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)

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

表1 節點關系與任務關系映射表

算法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函數中，會根據任務或工人信息計算其范圍的起始點和結束點在x軸和y軸的坐標，然后初始化樹節點，節點編號為任務或工人編號，set1和set2為比放入小于起始點和結束點的節點id，然后通過這些信息得出任務節點在樹中的節點關系.

算法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函數中，會根據節點中的值放入相應位置，首先插入節點會和樹的頭節點比較如果比插入節點的值要小，下次會和該節點的左節點比較，否則下一次和該節點的右節點比較，直到比較的節點為空為止，則將插入節點信息覆蓋該空節點，另外在整個插入過程中遇到比自己值小的節點會將其id記錄下來并且將其右子樹中的節點放入，每一次遇到比自己大的節點，該節點會將其id記錄在自己leftid集合中，函數最后將記錄的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

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

算法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)

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

算法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

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

4.5 實例分析

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

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

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

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

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

圖3 各任務到達后樹的情況

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

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

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

5 實驗分析

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

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

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

圖4 任務完成數對比

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

圖5 任務平均價格對比

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

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

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

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

6 總結與展望

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

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

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