中圖分類號：TP391 文獻標志碼：A 文章編號：1671-5489（2025）04-1157-07

Non-uniform Node Deployment Algorithm for Multi Hop Wireless Networks Based on Ant Colony Algorithm

JIANG Cheng （Schoolof Computer and Information Science，Hubei Enginering University，Xiaogan 4320oo，Hubei Province，China）

Abstract： Aiming at the problem that uneven distribution of nodes led to incomplete network coverage，the uneven position and density of nodes increased the complexity of deployment，and the search for the optimal node was prone to geting stuck in local optimal solutions in a multi hop wireless network，the author proposed a non-uniform node deployment algorithm for multi hop wireless network based on ant colony algorithm. Firstly，the author obtained the minimum weighted distance decision variable to reduce the transmisson distance between Sink nodes and various sensors. Secondly，the author calculated the energy consumption of nodes，minimized node network loss， constructed a node deployment optimization model，and introduced compromise planning method to expand the multi-objective model into a single objective processing. Finally，the author introduced ant colony algorithm to solve the model，which could effectively traverse the potential solution space and quickly find the optimal deployment plan. The experimental results show that the network coverage of proposed algorithm is 97% ，with a maximum energy consumption of only 1.56×10^-7J ，which can effectively reduce network energy consumption. The survival cycle can reach up to 1 5Oo rounds，and the optimal node deployment plan can be obtained.

Keywords： ant colony algorithm; multi hop wireless network; non-uniform node; node deployment

在實際應(yīng)用環(huán)境中，無線節(jié)點的分布通常是不均勻的，例如，在農(nóng)村、城市邊緣或人口稀少的區(qū)域，由于地理條件、資源限制或人口分布等原因，節(jié)點的密度會不同[1-2]．這種非均勻節(jié)點部署會對多跳無線網(wǎng)絡(luò)的性能和效能產(chǎn)生重要影響．非均勻節(jié)點部署導(dǎo)致網(wǎng)絡(luò)覆蓋范圍的不平衡以及增大了搜索空間和復(fù)雜性，為優(yōu)化多跳無線網(wǎng)絡(luò)的設(shè)計和性能帶來了挑戰(zhàn)．研究非均勻節(jié)點部署的目標是尋找合適的節(jié)點部署方案，以克服節(jié)點密度不平衡和空洞區(qū)域等問題，提高網(wǎng)絡(luò)的連通性及覆蓋范圍.

目前，針對網(wǎng)絡(luò)節(jié)點部署方法已進行了大量研究．滕文想等[3]通過無線電通信原理，組建WSNs節(jié)點部署空間模型，對空間進行等距劃分，引入概率函數(shù)計算各節(jié)點作為簇首節(jié)點的概率，實現(xiàn)節(jié)點部署．該方法采用等距劃分的方式將空間均勻劃分為網(wǎng)格，不考慮實際節(jié)點部署需求和環(huán)境特征．這種劃分方式會導(dǎo)致在一些區(qū)域節(jié)點密度過高而覆蓋范圍重疊，而在其他區(qū)域節(jié)點密度過低而覆蓋范圍不足，并存在空洞覆蓋的問題．楊力等[4根據(jù)迭代，結(jié)合網(wǎng)絡(luò)分簇算法，篩選出邊緣服務(wù)有效覆蓋率最高的節(jié)點部署策略．雖然采用迭代和網(wǎng)絡(luò)分簇算法有助于提高網(wǎng)絡(luò)覆蓋率和性能，但由于復(fù)雜的搜索空間和非均勻節(jié)點部署會導(dǎo)致算法陷入局部最優(yōu)解，節(jié)點部署的效果受初始解的影響，選擇不合適的初始解會導(dǎo)致最終結(jié)果不能達到全局最優(yōu)．Yao等[5通過蛾焰算法實現(xiàn)了網(wǎng)絡(luò)節(jié)點部署，蛾焰算法雖然是一種優(yōu)化算法，但其搜索機制或參數(shù)設(shè)置無法很好地適應(yīng)無線網(wǎng)絡(luò)中的節(jié)點部署問題，導(dǎo)致算法易陷入局部最優(yōu)解．Gupta等[在設(shè)定的約束條件下進行網(wǎng)絡(luò)節(jié)點部署，盡管約束條件可以減小搜索空間的范圍和復(fù)雜性，但在無線網(wǎng)絡(luò)中，節(jié)點部署問題的搜索空間仍很大，易陷入局部最優(yōu)解。為有效解決上述算法存在的不足，本文提出一種基于蟻群算法的多跳無線網(wǎng)絡(luò)非均勻節(jié)點部署算法.

多跳無線網(wǎng)絡(luò)非均勻節(jié)點部署算法

1.1節(jié)點部署模型建立

考慮到多跳無線網(wǎng)絡(luò)的組成結(jié)構(gòu)，由于節(jié)點分布不均勻會導(dǎo)致網(wǎng)絡(luò)覆蓋范圍不平衡，因此可將數(shù)據(jù)傳輸?shù)阶顑?yōu)的Sink節(jié)點（匯聚節(jié)點）上，更有效利用節(jié)點的通信能力，提高網(wǎng)絡(luò)的連通性，減少節(jié)點之間的跳數(shù)及傳輸延遲和能量消耗．其中，Sink節(jié)點是在網(wǎng)絡(luò)中的一個特殊節(jié)點，其主要功能是對從其他節(jié)點采集到的數(shù)據(jù)進行聚合和轉(zhuǎn)發(fā)，將數(shù)據(jù)傳輸?shù)街付ǖ哪康牡?，如監(jiān)控中心或數(shù)據(jù)存儲設(shè)備，具有較強的處理能力和通信能力，且位置選擇會根據(jù)網(wǎng)絡(luò)拓撲結(jié)構(gòu)和通信要求確定.

為降低 Sink節(jié)點到各傳感器間的傳輸距離，組建最小化加權(quán)距離決策變量，在考慮節(jié)點間距離的同時，還需充分考慮網(wǎng)絡(luò)的覆蓋范圍．最小化節(jié)點間的直接距離 X_j 和節(jié)點位置間的相對距離 Y_ij 可分別表示為

考慮節(jié)點之間的距離，組建非均勻節(jié)點布局目標函數(shù) O₁ 對應(yīng)的數(shù)學(xué)模型為

minO₁=M?h_i?d_ij?X_j?Y_ij

其中 h_i 表示固定時間范圍內(nèi)網(wǎng)絡(luò)非均勻節(jié)點 i 發(fā)送的請求總數(shù)， d_ij 表示非均勻節(jié)點 i 與節(jié)點 j 兩者之間的歐氏距離， N 表示非均勻節(jié)點的總數(shù)， M 表示候選Sink節(jié)點數(shù)量.

在多跳無線網(wǎng)絡(luò)中，布設(shè)多個傳感器用于數(shù)據(jù)的采集，完成數(shù)據(jù)采集后，先將其傳輸至Sink節(jié)點，再根據(jù)真實需求選取對應(yīng)的網(wǎng)絡(luò)傳輸至監(jiān)控中心．由于Sink節(jié)點適用于規(guī)模較大且可靠性較高的網(wǎng)絡(luò)，多跳無線網(wǎng)絡(luò)中節(jié)點密度與節(jié)點之間的距離較大，所以借助相關(guān)的分層路由協(xié)議完成數(shù)據(jù)的傳輸工作．由于節(jié)點間的通信負載不均勻或節(jié)點位置分布不均勻，因此可能導(dǎo)致部分節(jié)點消耗能量過快，從而影響整個網(wǎng)絡(luò)的穩(wěn)定性和可靠性．通過計算各輪節(jié)點的能量消耗情況，可及時發(fā)現(xiàn)、監(jiān)測并調(diào)整節(jié)點能量的分布，實現(xiàn)節(jié)點能量的均衡，提高網(wǎng)絡(luò)的整體性能和穩(wěn)定性．假設(shè)各傳感器節(jié)點在設(shè)定的時間內(nèi)發(fā)送 l_i 位數(shù)據(jù)，則各輪多跳無線網(wǎng)絡(luò)非均勻節(jié)點消耗的能量 C_si 可表示為

其中 C_elec 表示接收或發(fā)送單位數(shù)據(jù)的無線電路損耗能量， d₀ 和 d 分別表示距離門限與各傳感器到簇頭節(jié)點之間的距離， c_ft 和 c_mp 表示不同功率對應(yīng)的放大系數(shù).

設(shè)在多跳無線網(wǎng)絡(luò)中簇頭節(jié)點數(shù)量為 K ，則每一輪簇頭消耗的能量總和 C_chj 可表示為

其中 C_da 表示簇頭融合后在單位時間內(nèi)消耗的能量， ψ 表示簇頭融合后全部數(shù)據(jù)傳輸?shù)蕉嗵鵁o線網(wǎng)絡(luò)消耗的能量總和， l_j 表示發(fā)送的數(shù)據(jù)位數(shù)信息， C_sj 表示多跳無線網(wǎng)絡(luò)內(nèi)簇內(nèi)節(jié)點消耗的數(shù)據(jù)總量．結(jié)合上述分析，將多跳無線網(wǎng)絡(luò)非均勻節(jié)點網(wǎng)絡(luò)損耗最小化，組建多跳無線網(wǎng)絡(luò)非均勻節(jié)點部署模型為

minO₂=C_chj+C_si

利用折中規(guī)劃方法將多目標函數(shù)轉(zhuǎn)換為單目標函數(shù)，假設(shè) O₁^* 為布局優(yōu)化的最優(yōu)目標， O₂^* 為網(wǎng)絡(luò)能耗最優(yōu)目標， ω 表示 O₁^* 和 O₂^* 的相位權(quán)重，將以上多目標優(yōu)化問題轉(zhuǎn)換為單目標優(yōu)化問題，則非均勻節(jié)點部署優(yōu)化目標函數(shù)的總數(shù)學(xué)模型 O₃ 為

1.2基于蟻群算法的非均勻節(jié)點部署模型求解

在處理非均勻節(jié)點部署問題時，由于搜索空間龐大且復(fù)雜，因此傳統(tǒng)的優(yōu)化方法會陷人局部最優(yōu)解．而蟻群算法能通過社會性規(guī)則和信息素的更新機制，有助于跳出局部最優(yōu)解，實現(xiàn)全局最優(yōu)解的搜索．在非均勻節(jié)點部署情況下，蟻群算法可根據(jù)不同的節(jié)點位置和密度，靈活調(diào)整蟻群的搜索路徑，從而更好地適應(yīng)網(wǎng)絡(luò)的特點．同時，其具有較強的并行處理能力，可加速問題的求解過程．因此，完成非均勻節(jié)點部署模型建立后，考慮最小化加權(quán)距離與網(wǎng)絡(luò)損耗最小化，通過蟻群算法求解確定最佳節(jié)點部署方案[7-8].

當螞蟻在搜索食物及回巢時，會在各路徑上釋放信息素．若一群螞蟻出發(fā)尋找食物，一旦有螞蟻成功找到食物，則它會沿原來的路徑返回巢穴.在返回途中，這只螞蟻會釋放出外激素，這些外激素會逐漸向四周擴散并導(dǎo)致其濃度逐漸降低．假設(shè)有兩只螞蟻都尋找到同一個食物，則會按如圖1所示的路徑返回.

圖1中，設(shè)定食物在 A 點，螞蟻從 O 點出發(fā)， ，如果第一只螞蟻直接回到 O 點時，則第二只螞蟻返回至 C 點．在蟻群算法[9-10]中，設(shè)定各條路徑上的信息素初始值為 τ_ij（0）=τ₀ ，在多個位置隨機放置的螞蟻數(shù)量為 Ψ_m ，則下一個位置被選擇概率 Δ_pij^k（Δ_t） 可表示為

其中 τ_ij 和 τ_is 分別表示邊 （i，j） 和 （i，s） 上的信息素， η_ij（t） 和 η_is（t） 表示啟發(fā)因子， α 和 β 表示調(diào)節(jié)因子，allowed表示螞蟻 k 下一步被允許訪問的位置集合.

在實用過程中，采用禁忌表追蹤并記錄每只螞蟻經(jīng)過的位置．當蟻群中的全部螞蟻完成第一次遍歷處理后，需統(tǒng)計并計算各螞蟻經(jīng)過的路徑長度總和，保存并記錄長度最短的路徑．在上述操作基礎(chǔ)上，將各邊上的信息素進行及時更新，主要包括信息素自然揮發(fā)和信息素補充等步驟．對信息素補充對應(yīng)的計算公式為

其中 ρ 表示信息素揮發(fā)系數(shù)， Δτ_ij^k 表示第 k 只螞蟻在所經(jīng)過邊釋放的信息素濃度.

當螞蟻完成一次巡回后，重置其禁忌表并重返其起始位置，為下一次巡回做準備．結(jié)合上述分析，利用蟻群算法[11-12]求解非均勻節(jié)點部署模型的基本操作流程如圖2所示.

基于上述分析，采用蟻群算法[13-14]進行多跳無線網(wǎng)絡(luò)非均勻節(jié)點部署模型的求解，操作步驟如下.

1）將全部變量進行初始化處理

2）將多跳無線網(wǎng)絡(luò)非均勻節(jié)點的拓撲圖進行初始化處理，將各節(jié)點發(fā)送的位置存儲到數(shù)據(jù)庫內(nèi)，計算隨機兩個節(jié)點的通信距離 W?a，b? ，在規(guī)定時間內(nèi)對其進行更新．假設(shè)在限定時間內(nèi)存在沒有更新的節(jié)點，則將該點設(shè)定為不可到達：

W?a，b?=Z（L?a，b?）²，

其中 L?a，b? 表示節(jié)點 a 與節(jié)點 b 之間的物理距離， Z 表示比例系數(shù)

3）在循環(huán)開始后，需根據(jù)實際需求設(shè)定最大的循環(huán)次數(shù).

4）全部螞蟻依次遍歷多跳無線網(wǎng)絡(luò)非均勻節(jié)點：利用式（8）實現(xiàn)轉(zhuǎn)移概率計算后，以此為依據(jù)判斷螞蟻下一步將達到的節(jié)點，并將相關(guān)節(jié)點直接加入到禁忌表中；假設(shè)當前多跳無線網(wǎng)絡(luò)非均勻節(jié)點為目標節(jié)點，則下一個螞蟻開始遍歷.

5）經(jīng)過計算和比較每只螞蟻的路徑長度后，將最短路徑直接存儲于全局變量中，路徑長度計算公式為

其中 x 表示削弱的信息素量.

6）對各螞蟻經(jīng)過的路徑進行信息素更新，在搜索過程中逐漸學(xué)習(xí)到更好的非均勻節(jié)點部署方案.較好路徑上螞蟻釋放的信息素濃度會增加，而較差路徑上的信息素濃度會減少．通過不斷迭代更新，信息素會逐漸趨于平衡，最終獲取全局最優(yōu)解．對每只螞蟻經(jīng)過的路徑進行信息素更新 τ_ij（t+n） ，輸出最佳的多跳無線網(wǎng)絡(luò)非均勻節(jié)點部署方案：

τ_ij（t+n）=O₃×（ρτ_ij^′+Δτ_ij^k）.

2 實驗分析

為驗證本文基于蟻群算法的多跳無線網(wǎng)絡(luò)非均勻節(jié)點部署算法的有效性，以CC2530 ZigBee無線傳感器作為多跳無線網(wǎng)絡(luò)的數(shù)據(jù)采集設(shè)備，通信半徑為 20m ．數(shù)據(jù)采集實驗環(huán)境如圖3所示.

在MATLAB平臺上進行實驗分析，仿真區(qū)域為 1500m×1500m ，選取10只虛擬螞蟻，設(shè)定迭代次數(shù)為50次，信息素揮發(fā)系數(shù)為0.1，每 5min 采集一次數(shù)據(jù).

在設(shè)定區(qū)域內(nèi)，對本文算法的覆蓋性能進行實驗分析，實驗結(jié)果如圖4所示．由圖4可見：在未采用本文算法進行多跳無線網(wǎng)絡(luò)非均勻節(jié)點部署前，在覆蓋區(qū)域內(nèi)出現(xiàn)了多處空白；而采用本文算法進行部署優(yōu)化后，覆蓋率得到顯著提升，說明本文算法有較好的覆蓋效果．這是因為本文算法通過最小化加權(quán)距離決策變量，降低傳感器到Sink節(jié)點的傳輸距離，縮短了數(shù)據(jù)傳輸路徑，減少了能量消耗和

信號衰減，增強了網(wǎng)絡(luò)的連通性和覆蓋范圍.

為進一步驗證本文算法的覆蓋性能，將網(wǎng)絡(luò)覆蓋率作為測試指標，分析3種不同算法的覆蓋性能，實驗結(jié)果如圖5所示．由圖5可見，本文算法的網(wǎng)絡(luò)覆蓋率為 97% ，明顯高于另外兩種算法，進一步驗證了本文算法在網(wǎng)絡(luò)覆蓋方面的性能．這是因為螞蟻釋放的信息素可以引導(dǎo)其他螞蟻選擇路徑，在節(jié)點部署問題中，能引導(dǎo)螞蟻集中選擇覆蓋率較高的區(qū)域進行部署，從而提高整體網(wǎng)絡(luò)的覆蓋率．經(jīng)過多次迭代，信息素會趨向平衡，網(wǎng)絡(luò)的覆蓋性能也會得到提升.

在多跳無線網(wǎng)絡(luò)非均勻節(jié)點部署方面，分析3種不同算法的能量開銷，實驗測試結(jié)果列于表1．由表1可見，采用本文算法進行多跳無線網(wǎng)絡(luò)非均勻節(jié)點部署的能量消耗明顯更低，最高僅為 1.56×10^-7J ，主要是因為本文算法引入了蟻群算法求解模型，具有全局搜索和信息素引導(dǎo)機制，能有效遍歷潛在解空間，快速找到較優(yōu)的部署方案．蟻群算法可以幫助優(yōu)化節(jié)點部署，降低了整個網(wǎng)絡(luò)的能量消耗.

圖6為不同算法在各分區(qū)的節(jié)點生命周期測試結(jié)果比較．由圖6可見，在不同分區(qū)下，分別采用不同算法進行多跳無線網(wǎng)絡(luò)非均勻節(jié)點部署處理后，各算法對應(yīng)的節(jié)點生命周期均發(fā)生了不同程度的變化．與另外兩種算法相比，本文算法的節(jié)點生存周期明顯更長，當區(qū)號為25時，生存周期高達1500輪，具有更高的使用價值．因為通過計算節(jié)點消耗的能量，最小化節(jié)點網(wǎng)絡(luò)損耗，并采用折中規(guī)劃方法綜合考慮能耗和其他指標，使節(jié)點能更有效地利用能量資源，并減少能量消耗．通過降低能耗，節(jié)點的能量消耗速度較慢，從而延長了節(jié)點的生存周期.

綜上所述，針對傳統(tǒng)多跳無線網(wǎng)絡(luò)非均勻節(jié)點

部署算法存在的不足，本文提出了一種基于蟻群算法的多跳無線網(wǎng)絡(luò)非均勻節(jié)點部署算法．實驗測試結(jié)果表明，本文算法可大幅度提升網(wǎng)絡(luò)覆蓋性能，降低能量開銷，延長節(jié)點生命周期，獲取更滿意的多跳無線網(wǎng)絡(luò)非均勻節(jié)點部署方案.

參考文獻

[1］黃悅?cè)A，劉恒沖，陳慶，等．基于USRNet與改進YOLOv5x的輸電線路絕緣子故障檢測方法［J]．高電壓技術(shù)，2022，48（9）： 3437-3446. （HUANG Y H，LIU H C，CHEN Q，et al. Transmission Line Insulator FaultDetection Method Based on USRNet and Improved YOLOv5x [J]. High Voltage Engineering， 2022，48（9）：3437-3446.）

[2]黃悅?cè)A，陳照源，陳慶，等．基于邊緣計算和改進YOLOv5s算法的輸電線路故障實時檢測方法［J]．電力建設(shè)，2023，44（1）：91-99.（HUANG Y H，CHEN Z Y，CHEN Q，et al. Real-Time Detection Method forTransmission Line Faults Applying Edge Computing and Improved YOLOv5s Algorithm [J]. Electric PowerConstruction，2023，44（1）：91-99.）

[3]滕文想，何繼鵬，劉鵬宇．窄長空間無線傳感器網(wǎng)絡(luò)節(jié)點部署策略研究［J]．煤炭工程，2023，55（7）：151-157.（TENG W X，HE JP，LIU P Y. Deployment Strategy of Wireless Sensor Network Nodes in Narrow and LongSpace［J].Coal Engineering，2023，55（7）：151-157.）

[4]楊力，何兆斌，孔志翔．天地一體化智能網(wǎng)絡(luò)智能節(jié)點部署策略[J]．小型微型計算機系統(tǒng)，2022，43（1）：159-164.（YANG L，HE Z B，KONG Z X. Deployment Strategy of Intelligent Node in Integrated IntellgentNetwork [J]. Journal of Chinese Computer Systems，2022，43（1）：159-164.）

[5]YAO Y，HU S，LI Y，et al. A Node Deployment Optimization Algorithm of WSNs Based on Improved MothFlame Search [J]. IEEE Sensors Journal，2022，22（10）：10018-10030.

[6]GUPTA S K，KUMAR S，TYAGI S. Energy Efcient and Effctive Node Deployment for Wireless SensorNetwork [J]. International Journal of Communication Systems，2022，35（9）： e5139-1-e5139-17.

[7］張孟健，汪敏，王霄，等．混合粒子群-蝴蝶算法的WSN節(jié)點部署研究［J]．計算機工程與科學(xué)，2022，44（6）：1013-1022. （ZHANG M J，WANG M，WANG X，et al. A Hybrid Particle Swarm-Buterfly Algorithm for WSNNode Deployment [J]. Computer Engineeringamp; Science，2022，44（6）：1013-1022.）

[8］趙越，李贊，李冰，等．面向多源時差定位的魯棒節(jié)點部署算法［J]．西安電子科技大學(xué)學(xué)報，2022，49（6）：15-22.（ZHAO Y，LI Z，LI B，et al. Robust Node Placement in TDOA-Based Multiple Sources Localization [J].Journal of Xidian University，2022，49（6）：15-22.）

[9]張佩，游曉明，劉升．融合動態(tài)層次聚類和鄰域區(qū)間重組的蟻群算法［J]．計算機應(yīng)用研究，2023，40（6）：1666-1673.（ZHANG P，YOU X M，LIU S. Robust Node Placement in TDOA-Based Multiple SourcesLocalization [J]. Computer Application Research，2023，40（6）：1666-1673.）

[10]周橋梁，劉妮妮．蟻群算法在重介質(zhì)智能化選煤過程中的應(yīng)用[J]．煤炭技術(shù)，2022，41（9）：246-248.（ZHOU Q L，LIU N N. Application of Ant Colony Algorithm in Inteligent Coal Preparation Process of DenseMedium [J].Coal Technology，2022，41（9）：246-248.）

[11］馬康康，王雷，李東東，等．基于信息素差異分布策略的路徑規(guī)劃蟻群改進算法［J]．南京航空航天大學(xué)學(xué)報，2023，55（1）： 100-107. （MA K K，WANG L，LI D D， et al. An Improved Ant Colony Algorithm for PathPlanning Based on Pheromone Diferential Distribution Strategy[J].Journal of Nanjing University of Aeronauticsamp;.Astronautics，2023，55（1）：100-107.）

[12]李金磊，翟海亭．改進蟻群算法的超密集網(wǎng)絡(luò)資源分配方法仿真［J]．計算機仿真，2023，40（4）：377-381.（LI JL，ZHAI H T. Simulation of Super Dense Network Resource Allcation Method Based on Improved AntColony Algorithm [J]. Computer Simulation，2023，40（4） ：377-381.）

[13］葛翔，譚成偉，薛亞勇，等．無線傳感器網(wǎng)絡(luò)覆蓋的部署及調(diào)度算法［J]．吉林大學(xué)學(xué)報（信息科學(xué)版），2024，42（3）： 400-405.（GE X，TAN C W， XUE Y Y，et al. Deployment and Scheduling Algorithms for NetworkCoverage of Wireless Sensor [J]. Journal of Jilin University（Information Science Edition），2024，42（3）：400-405.）

[14］宋佳艷，蘇圣超．基于改進蟻群優(yōu)化算法的自動駕駛多車協(xié)同運動規(guī)劃［J]．計算機工程，2022，48（11）：299-305.（SONG JY，SU S C. Multi-vehicle Collaborative Motion Planning for Autonomous Driving Based onImproved Ant Colony Optimization Algorithm [J]. Computer Enginering，2022，48（11）： 299-305.）（責(zé)任編輯：韓嘯）