摘  要： 無線傳感器網絡（WSN）中的傳感器節點相互協作構成天線陣列，通過使用波束形成技術建立一個與無人機的通信連接。為了分散節點之間的處理和通信負載，提出了基于QR分解的分布式波束形成算法。建立MATLAB仿真模型對算法的性能進行分析，然后與集中式算法進行比較。分散處理負載的代價是增加了通信成本，從而導致網絡總功耗的增加。然而，每個節點的平均功率仍低于集中式算法中的簇頭，這樣就延長了節點的壽命。因此，該算法增強了網絡的魯棒性。

　　關鍵詞： 無線傳感器網絡；分布式；集中式；負載

1 基于LS的集中式波束形成算法簡介

　　基于LS的集中式方法的任何實現方案存在固有問題：處理負載不是分散在節點之間，而是由單一節點（簇頭）承擔，因此簇頭的能量很快就耗盡，發生故障的概率很大。如果這個簇頭出現故障，那么必須從頭開始解決LS問題，即一個新的中央節點必須重復這些工作：收集信息、計算權重系數、廣播信息，這造成了資源和時間的浪費。由于節點的電池壽命有限，因此節點失敗是很常見的?？偠灾?，集中式算法缺乏魯棒性。

2 基于QR分解的分布式波束形成算法

　　基于QR分解的分布式算法解決了集中式算法遇到的難題，付出的代價是增加了通信成本。對于魯棒性要求高的傳感器網絡，這種算法是可取的。簇頭收集所有傳感器節點的位置數據構造導向矩陣DH，然后對DH使用基于Householder變換的方法進行QR分解，對一個給定的期望響應Fd找到計算權重向量w的解決方法。

　　該算法利用DH的具體性質進行QR分解。導向矩陣

　　其中n是傳感器節點的數量，m是逼近點的數量。D（?茲）H第i列的元素僅取決于相應的節點位置xi和相應的角度。

　　第一個節點向其余所有節點廣播H1，其他節點經過H1的作用后，它們相應的列發生改變。同理，所有的Householder變換H1，H2，…，Hn-1，Hn作用后，將得到如下的上三角矩陣

　　其中a的上（k）標表示矩陣元素aij經過了Hk的作用，i=2，3，…，m，j=2，3，…，n；k=2，3，…，n。由于Householder變換只對其影響到的元素起作用，所以整個過程不會產生額外的處理負載，集中式和基于QR分解分布式方法在處理負載上沒有區別。分布式方式一個明顯的優勢是陣列中的每一個節點不需要承載所有的計算負載，它們依次完成QR分解，共同分擔計算負載。然而，該過程中會產生一些額外的通信負載，因為需要廣播矩陣。這就是減輕簇頭過重處理負載所付出的代價。

　　第二階段是利用這些Householder變換更新期望響應

　　第三階段是利用回代解決系統方程R1=c1=[c1 c2 … cn]H，其中R1是矩陣DnH前n行的n×n上三角矩陣。第n個節點通過等式n=cn計算出波束形成的權重n，然后第n個節點向所有節點廣播其位置xn和權重n。第n-1個節點收到廣播信息后，同樣，第n-1個節點向所有節點廣播其位置xn-1和權重n-1，第n-2個節點收到廣播信息后，通過第n-2個等式計算出權重?棕n-2。最后，每個節點都得到了自身的權重，這些節點協調工作構成傳感器網絡，形成天線陣列。

3 算法性能分析

　　計算成本用實現所需要的指令數來衡量。在中央處理器中，求解分布式QR分解算法的指令數Ni=2n2（m-n/3）+mn+n2，其中第一項是由QR分解決定，第二項是利用Householder變換更新期望響應的向量產生的，最后一項是利用回代解決權重問題產生的。

　　在分布式方法的第一階段中，第一個節點不構造整個矩陣，只使用它的第一列構造第一個Householder矩陣H1。然后在后面的回代階段，使用H1計算R1的第一行。同樣地，第二個節點使用第二列計算H2和R1更新的第二行。因此，整個過程不會增加額外計算，總處理成本正好等于集中式方法的總處理成本。定義Pi為每條指令的平均功率，處理功率Pp：

　　Pp=Ni×Pi=[2n2（m-n/3）+mn+n2]×Pi（3）

　　在集中式算法中，通信成本只與實現算法所發送陣元的數據量有關，簇頭從n個節點收集所有位置信息，發送n個權重，所以傳送的數據量Nt=2n。

　　在分布式算法中，對于第一階段，任一節點i發送矩陣Hi，共有m-i+2個數，因此第一階段的所有節點發送的總數據量為：

　　對于回代階段，除了第一個節點外的每個節點都要向其他節點廣播它們的位置和權重，因此回代階段發送的總數據量CBS=2（n-1）。最后得到通信的總數據量C=CQR+CBS=（m+4-n/2）（n-1）。假設每個陣元用b比特（bit）來表示，那么所傳送的比特數Ntb=C×b。定義Ptb為傳送每bit的平均功率，通信功率Pc

　　Pc=Ntb×Ptb=（m+4-n/2）（n-1）×Ptb×b（5）

　　因此，算法實現過程中的總功率是式（3）和式（5）的和。

　　P=[2n2（m-n/3）+mm+n2]×Pi+（m+4-n/2）（n-1）×Ptb×b（6）

　　同理，集中式算法的總功耗為：

　　P=[2n2（m-n/3）+mm+n2]×Pi+2n×Ptb×b（7）

4 仿真結果

　　圖1和2分別繪出了總功耗和逼近點數量m、傳感器數量n的函數圖形。其中Ptb=tb×Pi，歸一化功率Pn=[2n2（m-n/3）+mm+n2]+（m+4-n/2）（n-1）。

　　從圖中可以明顯看出，分布式算法比集中式算法的功率高，這是額外通信負載造成的。然而，分布式算法的總成本不是由單一節點承擔，而是分散在傳感器網絡節點之間。例如，圖1中部署了20個傳感器節點，其分布式算法的功率大約是集中式算法的5倍。因此，集中式算法的簇頭所消耗的功率大約是分布式算法的傳感器節點的4倍。顯然，這將導致簇頭迅速失敗，意味著將需要選擇一個新的簇頭重新開始所有的計算。因此，用分布式方法的總功耗來換取網絡的魯棒性是非常合理的。

　　本文對基于QR分解的分布式波束形成算法做了詳細的介紹，該算法降低了節點平均功耗，付出的代價是增加了通信功率，進而增加了網絡中的總功耗。然而這個總功率分散在傳感器節點之間，因此分布式算法中單個傳感器節點的平均功率低于集中式算法中簇頭所需要的功率。因此，網絡出現故障的概率大大降低，增強了魯棒性。本文進行了一些假設，如節點可以精確地計算它們的位置，它們之間的通信不受噪聲影響。將來的工作可能要研究這些誤差對計算權重向量和陣列性能的影響。本文在均勻采樣的基礎上選擇一些逼近點，但也可以選擇其他的方法，如使用非均勻網格。最后，通信成本被定義為實現算法所需要傳送數據的一個函數。然而除了本文中一些產生功耗的因素，還有其他產生功耗的因素，如數據包開銷和由于碰撞、錯誤導致的重傳，這些功耗是總功耗的一部分，在將來的工作中需要考慮。

　　參考文獻

　　[1] 楊維，陳俊仕.移動通信中陣列天線技術[M].北京：清華大學出版社，2005.

　　[2] F.施依德.數值分析（第2版）[M].羅亮生，包雪松，譯.西安：西安電子科技大學出版社，2002.

　　[3] ZHAO Q， SWAMI A， TONGL. The interplay between signal processing and networking in sensor networks[J]. IEEE Signal Processing Magazine， 2006，23（4）：84-93.

　　[4] REICHENBACH F. A distributed linear least squares method for precise localization with low complexity in wireless sensor networks[C]. Proceedings of 2nd IEEE International Conference， DCOSS， San Francisco， CA，2006：514 -528.

　　[5] GOLUB G， VAN LOAN C F. Matrix computations[M]. Baltimore， MA： The Johns Hopkins University Press，1996.