一種採用多機器人的傳感器網絡優化部署方法
2023-05-22 18:57:36
一種採用多機器人的傳感器網絡優化部署方法
【專利摘要】本發明提出了一種採用多機器人的傳感器網絡優化部署方法，涉及機器人網絡與傳感器網絡兩個熱點領域，根據特定的傳感器網絡部署和感知目標特點(如限制區域種類及分布，感興趣區域分布)、感知性能指標需求(如覆蓋與連通性、生存期、廣義精度等)，結合不同機器人以及網絡節點在通信距離、感知距離、重量、承載能力和能量等方面的約束條件，由母機器人承載子機器以及網絡節點進入待部署與需感知區域，經智能規劃，分別由母機器人直接協同(此時，與傳統體系結構相似)網絡節點感知，或(和)通過分級拓展協同，由母機器人部署子機器人、進而由子機器人協同網絡節點部署與感知。在傳感器節點的部署中，通過針對機器人設計的距離優化(DO，Distance?Optimization)、時間優化(TO，Time?Optimization)和能量優化(EO，Energy?Optimization)問題的啟發式優化算法，以期達到網絡部署與感知的整體優化目的。
【專利說明】一種採用多機器人的傳感器網絡優化部署方法
【技術領域】
[0001]本發明涉及機器人網絡與傳感器網絡兩個熱點領域。根據特定的傳感器網絡部署和感知目標特點(如限制區域種類及分布，感興趣區域分布)、感知性能指標需求(如覆蓋與連通性、生存期、廣義精度等)，結合不同機器人以及網絡節點在通信距離、感知距離、重量、承載能力和能量等方面的約束條件，由母機器人承載子機器以及網絡節點進入待部署與需感知區域，經智能規劃，分別由母機器人直接協同(此時，與傳統體系結構相似)網絡節點感知，或(和)通過分級拓展協同，由母機器人部署子機器人、進而由子機器人協同網絡節點部署與感知。
【背景技術】
[0002]傳感器網絡隨機部署是最簡單的一種部署方式，但可能會帶來感知性能與需求不匹配，以及資源浪費等問題。實際上，從傳統網絡的規劃部署，到早期傳感器網絡節點的任意部署、隨機部署，再到網絡節點的整體規劃部署與局部隨機部署相結合的優化部署，是對於優化部署與感知問題研究的螺旋式上升的過程。高質量的部署有助於將智能從高端、遠程向傳感器網絡自身、本地遷移，從而更好地實現和體現傳感器網絡的分布式智能。通過移動機器人協同，可以實現傳感器網絡及其節點的逐漸擴展式部署，這一優勢在未知環境探索等情境下尤為重要。
[0003]一般而言，機器人協同的傳感器網絡部署與感知是綜合性較強、複雜程度較高的一類問題；而針對複雜作業任務，往往需要多個(或多種)機器人構成多機器人協作系統才能完成。進一步地，實際環境對於機器人協同的節點部署與感知作業往往造成各種限制；而各種機器人自身往往又各具特點(包括優勢和不足等)。
[0004]例如，僅從機器人和障礙物的幾何尺度的角度分析，小機器人在較大障礙(如深溝等)或較高作業面(如高臺階)等情境下進行傳感器網絡協同部署與感知作業較為困難，而大機器人在較低、較窄空間環境(如辦公桌下、貨架間、管道中)等情境下進行傳感器網絡協同部署與感知作業較為困難。
[0005]各種機器人進行協同網絡感知作業時有其自身的適應場合。而實際待部署與需感知環境往往是較為複雜的，單一類型機器人可能無法有效應對協同部署與感知作業全過程中多種環境限制，需要多種機器人配合完成感知的全過程。
[0006]另外，由傳感器網絡自身特點所決定，行動網路節點在能量、對環境的適應能力、對複雜環境的辨識能力與決策能力等方面必然存在較大的局限性，而且其復用性通常也非常有限。因此，機器人協同的傳感器網絡部署與感知傳統體系結構存在多方面的局限性，需要有新的體系結構加以補充。
【發明內容】
[0007]本發明的目的提出一種採用多機器人的傳感器網絡優化部署方法。
[0008]具體的技術方案為:[0009](I)採用城市分組的變形旅行商問題(TTSPGC, Transfigured TravellingSalesman Problem under Grouped Cities)模型作為描述基本感知作業(BDST, BasicDeploying and Sensing Task)問題的簡化模型。
[0010]在TTSPGC中，將各個感興趣區域作為城市(ctij)，並按其所處的限制區域(RAIIl?RA IIMjRAII為第II類限制區域，子機器人可以作業，母機器人不可以作業，可以部署網絡節點，可以通信)進行分組(城市組GCl?GCM)，其中城市下標i和j分別代表城市所屬的城市組編號和組內編號。
[0011]為解決母機器人與子機器人移動軌跡在限制區域邊界的連續性問題，提出了虛擬城市(VC, Virtual City)的概念,其基本思想如下。
[0012]針對每個限制區域，母機器人部署子機器人，以及子機器人回歸母機器人的位置設置一對虛擬城市。第i個限制區域的兩個虛擬城市分別為(兩個虛擬城市的下標j分別取O和限制區域內感興趣區域總數加1，即把虛擬城市添加為限制區域的首「城市」和末「城市」)。需要說明的是，虛擬城市之間在位置上有可能互相重合。
[0013](2)根據具體優化目標不同，協同部署與感知用機器人的優化問題(可以分為距離優化(DO, Distance Optimization)、時間優化(TO, Time Optimization)和能量優化(E0,Energy Optimization)三類典型問題，即在完成網絡節點分級異構拓展部署與感知作業過程中，針對協同部署與感知用母機器人和子機器人所經歷的距離、所花費的時間或所消耗的能量的優化問題，並因此對於單母機器人和單子機器人系統建立距離優化、時間優化和能量優化目標函數。距離優化是基礎，時間優化和能量優化在特定約束條件下可以轉化為具有權重的距離優化問題。
[0014](3)優化算法設計具體包括規劃與作業兩個層面，重點包括虛擬城市定位和軌跡規劃兩類問題，在設計中兼顧實現協同部署與感知用母機器人和子機器人的規劃、控制的實時性與優化效果之間的均衡。
[0015]I)協同部署與感知規劃優化流程
[0016]本發明採用兩級嵌套(TLN, Two-Level Nesting)的算法結構分別完成母機器人軌跡規劃(即，城市組次序以及城市組首虛擬城市、末虛擬城市位置的確定)和子機器人軌跡規劃(即，從首虛擬城市經城市組內各城市到達末虛擬城市的次序和路徑)，規劃的結果確定距離、時間和能量優化目標函數等各式中各城市組以及每個城市組內各城市的下標序號。
[0017]2)網絡節點部署與作業流程
[0018]在確定虛擬城市位置後，母機器人與子機器人軌跡規劃問題可以轉化為以SP(既是起點也是終點)和各個城市的集合構成的城市分組的變形旅行商問題(TTSPGC)。具體進行子機器人軌跡規劃時，採用自適應蟻群算法(ACA, Ant Colony Algorithm)解決該問題。
【專利附圖】
【附圖說明】
[0019]圖1基本感知作業下城市分組的變形旅行商模型的一個直觀表現圖。
[0020]圖2TTSPGC模型下多機器人與傳感器網絡協同部署與感知規劃流程圖。
[0021]圖3網絡節點部署與作業流程步驟I示意圖
[0022]圖4網絡節點部署與作業流程步驟2示意圖[0023]圖5網絡節點部署與作業流程步驟3示意圖
[0024]圖6網絡節點部署與作業流程步驟5示意圖
[0025]具體實施方法
[0026]為使本發明結構更加清晰完整，下面結合附圖對本發明作進一步的說明。
[0027]參照圖1，它是基本感知作業下城市分組的變形旅行商模型的一個直觀表現圖。
[0028]圖中I是各個感興趣區域(即為需要布置無線傳感器的地方)，在TTSPGC(城市分組的變形旅行商模型)中，將各個感興趣區域作為城市ctij，，對應圖中各個帶陰影的圓形。
[0029]圖中2是城市組，按各個感興趣區域所處的限制區域(RAII1?RAHM，RAII為第II類限制區域，子機器人可以作業，母機器人不可以作業，可以部署網絡節點，可以通信)進行分組(城市組GCl?GCM)，其中城市下標i和j分別代表城市所屬的城市組編號和組內編號。
[0030]圖中3是虛擬城市VC，為解決兩類機器人移動軌跡在限制區域邊界的連續性問題，提出了虛擬城市VC的概念，對應圖中各個帶陰影的菱形。針對每個限制區域，母機器人部署子機器人，以及子機器人回歸母機器人的位置設置一對虛擬城市。第i個限制區域的兩個虛擬城市分別為CtiO和cti (Ni+1)(兩個虛擬城市的下標j分別取O和限制區域內感興趣區域總數加1，即把虛擬城市添加為限制區域的首「城市」和末「城市」)。需要說明的是，虛擬城市之間在位置上有可能互相重合。
[0031]圖中4是母機器人的起點(SP)，為了保持處理上的統一性，將母機器人的起點(SP)同時定義為GCO (即第O號城市組)，CtOO和CtO (N0+1)(即第O號城市組的首虛擬城市和末虛擬城市)。
[0032]圖2為TTSPGC模型下多機器人與傳感器網絡協同部署與感知規劃流程圖。在此流程圖中，首先初步規劃母機器人的移動軌跡，進而規划子機器人的移動軌跡；通過子機器人在城市組內路徑的優化，在必要時調整虛擬城市的位置，進而調整子機器人、母機器人的規劃移動軌跡，從而達到針對特定目標函數優化的目的。需要強調的是，在實際規划過程中，母機器人與子機器人軌跡規劃關係通常較為複雜；圖中，步驟①?步驟⑧各環節之間通常並非簡單的串行關係。
[0033]圖3至圖6為網絡節點部署與作業流程示意圖。在此示意圖中，網絡節點部署與作業流程的步驟為:
[0034]I)母機器人承載子機器人及網絡節點按照規劃路逕到達一個城市組(如在圖3中，從GCtl出發，沿實線到達GC1中的虛擬城市Ctltl位置)並部署子機器人；
[0035]2)子機器人在某個城市組中按照規劃路徑移動並依次訪問各個城市(如在圖4
中，子機器人從GC1的首虛擬城市Ctltl移動到第I個真實城市Ct11......)進行網絡節點協
同部署(或信息感知)作業；
[0036]3)如圖5所示，子機器人按照規劃路徑遍歷某個城市組(B卩，在某個限制區域內完成所有感興趣區域的網絡節點協同部署/協同信息感知作業)後，按照規劃路徑(如，在圖5中，沿著雙點劃線的方向，從GCl的最後一個真實城市叫〃,移動到末虛擬城市叫w+υ)回歸母機器人；
[0037]4)判斷是否完成全部城市組的訪問(即，全部限制區域的網絡節點協同部署/協同信息感知作業)任務，若未完成，則返回I);
[0038]5)母機器人承載子機器人及剩餘的網絡節點按照規劃路徑回到SP(如在圖6中，從最後一個城市組GCm的末虛擬城市沿實線回到Ctcici)。
【權利要求】
1.一種採用多機器人的傳感器網絡優化部署方法，其特徵在於，該方法包括: 採用城市分組的變形旅行商問題(TTSPGC, Transfigured Travelling SalesmanProblem under Grouped Cities)模型作為描述基本感知作業(BDST,Basic Deploying andSensing Task)問題的簡化模型。 根據具體優化目標不同，協同部署與感知用機器人的優化問題可以分為距離優化(D0，Distance Optimization)、時間優化(TO, Time Optimization)和能量優化(EO, EnergyOptimization)三類典型問題,即在完成網絡節點分級異構拓展部署與感知作業過程中，針對協同部署與感知用母機器人和子機器人所經歷的距離、所花費的時間或所消耗的能量的優化問題。距離優化是基礎，時間優化和能量優化在特定約束條件下可以轉化為具有權重的距離優化問題。 優化算法設計具體包括規劃與作業兩個層面，重點包括虛擬城市定位和軌跡規劃兩類問題，在設計中兼顧實現協同部署與感知用母機器人和子機器人的規劃、控制的實時性與優化效果之間的均衡。
2.根據權利要求1所述的方法，其特徵在於，所述採用城市分組的變形旅行商問題(TTSPGC, Transfigured Travelling Salesman Problem under Grouped Cities)模型作為描述基本感知作業(BDST, Basic Deploying and Sensing Ta`sk)問題的簡化模型,此模型建立的過程為: 在TTSPGC中，將各個感興趣區域作為城市(ctij)，並按其所處的限制區域(RA II I~RA II M,RA II為第II類限制區域，子機器人可以作業，母機器人不可以作業，可以部署網絡節點，可以通信)進行分組(城市組GCl~GCM)，其中城市下標i和j分別代表城市所屬的城市組編號和組內編號。 為解決母機器人與子機器人移動軌跡在限制區域邊界的連續性問題，提出了虛擬城市(VC, Virtual City)的概念，其基本思想如下。 針對每個限制區域，母機器人部署子機器人，以及子機器人回歸母機器人的位置設置一對虛擬城市。第i個限制區域的兩個虛擬城市分別為Ctici和(兩個虛擬城市的下標j分別取O和限制區域內感興趣區域總數加1，即把虛擬城市添加為限制區域的首「城市」和末「城市」)。需要說明的是，虛擬城市之間在位置上有可能互相重合。
3.根據權利要求1所述的方法，其特徵在於，所述協同部署與感知用機器人的優化問題可以分為距離優化、時間優化和能量優化三類典型問題，對於此三類典型問題，所建立的優化數學模型為: (I)距離優化數學模型。 單母機器人-單子機器人系統基本距離優化目標函數可以用式(I)描述。 W f A』.、Jd = Y Y + D,(N-+,) + D(i+1)0 + D^m +nD ^ij?(Ν.+1)M(N +1) i=0 J=O1MVJ(D- 其中，M代表城市組的總數(i從O開始是為了能夠包括起點SP)； Ni代表第i號城市組內城市的個數(j從O開始是為了包括城市組的首虛擬城市)；代表子機器人在第i號城市組內，從第j號城市到第j+Ι號城市(包括末虛擬城市)之間所經歷的距離；DP+"代表母機器人從第i號城市組的首虛擬城市到末虛擬城市之間所經歷的距離； jcCi=代表母機器人從第i號城市組的末虛擬城市到第i+Ι號城市組的首虛擬城市之間所經歷的距離；
代表母機器人從第M號城市組(即，最後一個城市組)的末虛擬城市回到起點SP所經歷的距離。 (2)時間優化數學模型。 單母機器人-單子機器人系統基本時間優化目標函數可以用式(2)描述。
4.根據權利要求1所述的方法，其特徵在於，優化算法設計具體包括規劃與作業兩個層面，重點包括虛擬城市定位和軌跡規劃兩類問題，在設計中兼顧實現協同部署與感知用母機器人和子機器人的規劃、控制的實時性與優化效果之間的均衡。 協同部署與感知規劃優化的基本步驟為:首先初步規劃母機器人的移動軌跡，進而規划子機器人的移動軌跡；通過子機器人在城市組內路徑的優化，在必要時調整虛擬城市的位置，進而調整子機器人、母機器人的規劃移動軌跡，從而達到針對特定目標函數優化的目的。 網絡節點部署與作業流程的步驟為: 1)母機器人承載子機器人及網絡節點按照規劃路逕到達一個城市組並部署子機器人； 2)子機器人在某個城市組中按照規劃路徑移動並依次訪問各個城市進行網絡節點協同部署(或信息感知)作業； 3)子機器人按照規劃路徑遍歷某個城市組(即，在某個限制區域內完成所有感興趣區域的網絡節點協同部署/協同信息感知作業)後，按照規劃路徑回歸母機器人； 4)判斷是否完成全部城市組的訪問(即，全部限制區域的網絡節點協同部署/協同信息感知作業)任務，若未完成，則返回I)； 5)母機器人承載子機器人及剩餘的網絡節點按照規劃路徑回到SP。
【文檔編號】H04W16/18GK103533553SQ201210222776
【公開日】2014年1月22日 申請日期:2012年7月2日 優先權日:2012年7月2日
【發明者】路海龍, 邴志剛, 田立國, 楊麗 申請人:天津職業技術師範大學