一種在移動通信系統內存儲和維護用戶設備信息的方法
2023-09-14 01:09:50
專利名稱：一種在移動通信系統內存儲和維護用戶設備信息的方法
技術領域：
本發明涉及電信領域，尤其是涉及移動通信系統以及移動通信系統中對用戶設備相關信息進行存儲和查找的方法。
背景技術：
在移動通信系統中，相關的網絡控制設備需要對用戶設備的信息進行維護以便能夠及時地查找到相應的用戶設備並進行相應的處理。例如，負責一個區域的網絡控制器需要對處於該區域內的所有移動通信設備的信息進行登記、存儲，並在該等移動通信設備主動請求建立通信鏈路時，或者在其他通信設備請求與該等移動通信設備建立通信鏈路時查找到該等移動通信設備的相關信息。在這個過程中，如何合理地存儲該等移動通信設備的信息，以及如何在網絡控制設備中查找該等移動通信設備的信息是一個關鍵的問題。
以寬帶碼分多址(WCDMA，WideBand Code-Division Multiple Access)系統為例，其是第三代移動通信系統標準化組織提出的無線傳輸技術(RTT，Radio Transmission Technical)方案。在寬帶碼分多址系統中，無線網絡控制器負責對本區域內的所有用戶設備(UE，User Equipment)的信息進行存儲和維護，並在需要的時候從資料庫中查找該等信息。具體地說，在寬帶碼分多址系統中，使用UTRAN無線網絡臨時標識(U-RNTI，UTRAN-Radio Network Temporary Identity)和Cell無線網絡臨時標識(C-RNTI，Cell-Radio Network Temporary Identity)來標識不同的用戶設備和維護相應上述標識下用戶設備已被分配的資源，例如，被分配的語音信道，下載數據時的數據鏈路信道信息等。我們以現有標準為例，根據3GPP25.331標準，一個UTRAN無線網絡臨時標識的長度是32位(bit)，一個Cell無線網絡臨時標識的長度是16位(bit)，假設一個無線網絡控制器有200000個用戶，即其需要維護200000個用戶設備的相關信息，如果採用直接映射的方法，假設僅該存儲200000個用戶設備UTRAN無線網絡臨時標識信息，所需要的存儲空間約為16G字節(Bytes)左右。而實際的情況是，一個無線網絡控制器所需要維護的用戶設備數量遠遠大於上述假設的用戶數200000個，因此，按照上述的直接映射的方法存儲用戶設備信息對於網絡控制設備而言是一個沉重的負擔，大大地浪費了硬體成本。
不僅如此，我們繼續採用上述假設條件，採用上述的直接映射的方法存儲用戶設備信息的情況下，則當無線網絡控制器需要查找一個特定的用戶設備的信息時，所需要的平均時間也比較長，例如，在上述條件下，一般來說比較常用的查找方法是二分法，其查找的平均時間是log2n次，儘管其已經比順序查找法在效率上有了很大的提高，但實際上，這樣的時間消耗仍然很大。
歸納而言，本領域的技術人員希望解決兩個問題，即如何優化存儲用戶設備相關信息所需要的存儲空間，以及如何提高查找一個特定用戶設備相關信息的時間。由於存儲的問題和查找的問題是相關的，因此，上述兩個實際上是一個問題。
為此，在申請號為CN200410000520.9，發明名稱為「一種UTRAN協作尋呼中的分布式數據存儲處理方法」的中國專利申請中提出了一種對用戶設備進行分布式存儲從而提高RNC系統UTRAN協作尋呼的整體性能的方法，本發明嘗試提出一種不同的用於對用戶設備進行存儲和維護的方法。
發明內容
發明人希望提供一種在移動通信系統中存儲和維護用戶設備信息的方法，以此來優化存儲空間，相應地，也提供一種新型的查找用戶設備的方法，以提高查找效率。
為此，本發明提供了一種基於哈希表和二叉樹相結合的存儲方法以解決上述問題。
一種在移動通信系統中存儲和維護用戶設備信息的方法，應用於該移動通信系統中的網絡控制設備的用戶設備信息維護控制單元中，其特徵在於，該方法通過如下步驟完成將一個用戶設備信息存儲至數據伺服器內的過程步驟一，使用一哈希函數對用戶設備信息的關鍵字進行映射，確定其在哈希表中的第一存儲位置；步驟二，若所述第一存儲位置與哈希表內數據不發生衝突，則按照所述第一存儲位置存儲所述用戶設備信息，否則重複步驟一、二進行有限次數的探索以探索下一個存儲位置，若在有限次內完成存儲操作則存儲過程完畢，否則轉步驟三；步驟三，以上述存儲位置中的一個存儲位置作為根節點建立二叉樹，並按照二叉樹存儲規則將所述用戶設備信息存儲到二叉樹相應的位置。
上述步驟一中所述的用戶設備信息的關鍵字是用戶設備的標識信息。例如，對於寬帶碼分多址系統其是UTRAN無線網絡臨時標識，也可以是Cell無線網絡臨時標識。
上述步驟一中所述的哈希函數是一除餘函數，即H(K)＝K mod P，其中，K表示所述用戶設備信息的關鍵字，P為小於所述哈希表長度的最大指數。
上述P的取值範圍與所述網絡控制設備所維護的用戶設備的個數a的關係符合如何要求時15％*P＜a＜85％*P為推薦範圍。
但需要注意的是，上述哈希函數還可以採用其他方法構建，例如平方取中法，可以採用從高位開始選取關鍵字的平方的第2、3、4位作為該關鍵字的哈希地址。
上述步驟二中，採用開放定址法進行有限次探索，具體而言，採用如下函數Hi(k)＝(H(k)+di)mod m(i＝1，2，…，k(k≤m-1))，其中，K表示所述用戶設備信息的關鍵字，m代表所述哈希表的長度，di代表探索所需要的增量。
上述增量di可以是如下的一種(1)di＝1，2，3…；(2)di＝12，-12，22，-22…；(3)di為偽隨機序列。
上述探索的次數在每次啟動所述用戶設備信息維護控制單元時人工設定。
上述探索的次數是上述的用戶設備信息維護控制單元根據系統的具體情況來動態決定的。該用戶設備信息維護控制單元根據系統接入的用戶設備的數量以及系統的內存空間、系統存儲或查找一個用戶設備的時間來決定探索的次數。
在上述步驟三中，作為根節點的存儲位置是由管理員預先指定的，例如是第一存儲位置，或者是第二存儲位置，或者是最後一個存儲位置，或者是其他存儲位置。
上述網絡控制設備應用於一個移動通信系統中，用於對一個區域內的所有用戶設備進行維護，對該移動通信系統中的基站進行管理，提供無線資源管理、基站功率控制、用戶接入管理和移動性管理等功能。該移動通信系統還包括所述的數據伺服器，用於存儲用戶設備的相關信息，所述網絡控制設備包括一用戶設備信息維護控制單元，該單元用於對用戶設備信息進行具體維護，上述的一種存儲和維護用戶設備信息的方法即應用於該單元中。
在上述存儲過程中，所存儲的用戶設備信息是該用戶設備信息的全部內容，包括關鍵字以及其他信息，例如用戶設備的連接狀態信息等。
在上述存儲過程中，所存儲的用戶設備信息也可以僅僅是該用戶設備信息的關鍵字，此時，用於存儲該等關鍵字的存儲位置或二叉樹的節點所對應的存儲單元還包括一個地址指針，該指針指向用於存儲該用戶設備其他信息的存儲單元。在這樣的情況下，先根據本方法確定該用戶設備信息的關鍵字的存儲單元，然後將該用戶設備的其他信息存儲到一個存儲單元中，並將後一個存儲單元的地址指針與該用戶設備的關鍵字一併存儲到前一個存儲單元內。
在應用了上述一種存儲用戶設備信息的方法對用戶設備信息進行存儲後，在查找特定設備時就可以應用同樣的方法予以查找。可以理解的是，進行查找時，在確定一個存儲位置或二叉樹的根節點後，不是在該位置判斷是否衝突或進行存儲，而是將該位置的關鍵字信息與待查找的關鍵字進行比較，如果一致則表明查找成功，否則繼續查找。
當一個用戶設備不再需要上述網絡控制設備維護時，上述網絡控制設備首先按照本發明提供的方法查找到該用戶設備的存儲位置，然後刪除該用戶設備的相應信息。可以理解的是，當上述存儲位置對應的存儲單元僅僅存儲該用戶設備的關鍵字時，則先行將該存儲單元中包含的地址指針對應的存儲信息，即該用戶設備的其他信息刪除，然後再刪除該用戶設備信息的關鍵字。
當一個用戶設備信息需要更改時，上述網絡控制設備首先按照本發明提供的方法查找到該用戶設備的存儲位置，然後修改該用戶設備的相應信息。同樣可以了解的是，當上述存儲位置對應的存儲單元僅僅存儲該用戶設備的關鍵字時，則實際修改該存儲單元中包含的地址指針所指向的存儲單元內的該用戶設備的其他信息。
以一個網絡控制設備需要維護的用戶設備數量為200000個為例，在採用直接映射方法的情況下，存儲上述用戶設備的關鍵字索引所需要的存儲空間約為16G字節，查找一個特定用戶設備的時間複雜度為log2n；而在採用本發明所述的方法的情況下，存儲上述用戶設備的關鍵字索引所需要的存儲空間遠低於上述的16G字節。例如，在上述情況下，假設所有用戶全部被激活，並設定哈希表長度為最大用戶數，即200000，此時，一個用戶設備的關鍵字信息需要4個字節(Byte)，因此，最終的關鍵字索引佔用的存儲空間為800000位元組。相應地，查找一個特定用戶設備的時間複雜度低於log2n+1，因此，在查找效率上也有了很大的提高。不僅如此，採用本發明提供的查找方法，查找次數降低，也導致比較的次數減少，從而減少了對內存的佔用。
實際上上述的例子是比較極端的情況，在實際應用中，所有用戶設備均被激活，在這樣的實際情況下，本發明提供的存儲方法可以節省更多的空間。
本發明所提供的一種存儲用戶設備信息的方法，有效地節省了存儲空間，同時可以快速地查找用戶設備相關信息，提高了系統效率。應於該種方法的移動通信系統的性能有了顯著的提高。
圖1是本發明的一個實施例所應用的移動通信系統的系統示意圖。
圖2是本發明的一個實施例存儲一個用戶設備信息的流程圖。
圖3a、3b、3c、3d、3e、3f是本發明的一個實施例中用於存儲用戶設備信息的二叉樹哈希表的示意圖。
圖4是本發明的又一個實施例中用於存儲用戶設備信息的二叉樹哈希表的示意圖。
圖5是本發明的一個實施例中哈希表二叉樹的一個二叉樹節點的數據結構示意圖。
具體實施例方式
參考圖1，其描述了本方面的一個實施例所應用於的移動通信系統的系統示意圖。在本實施例中，所述的移動通信系統是一個寬帶碼分多址(WCDMA)系統。參考圖1，寬帶碼分多址系統至少包括網絡控制設備1，即無線網絡控制器(RNC)，以及一數據伺服器2。本領域的技術人員可以理解，在實際應用中，上述寬帶碼分多址系統還應包括其他設備，例如若干個節點(NodeB)、若干個用於中轉的交換機(MSC)等，但由於本發明重點關心上述的網絡控制設備1，因此對該等其他設備予以忽略，本領域的技術人員可以根據現有技術以及公知資料對其他設備予以理解並實施。在本實施例中，上述無線網絡控制器採用了烽火科技集團生產的FH-RNC-3101-I產品，而採用何種無線網絡控制器並不影響本發明的實質內容，例如，在其他類似的實施例中，也可以採用諾基亞公司生產的UltraSiteSupreme系列WCDMA基站產品。
參考圖1，上述網絡控制設備1又包括用戶設備信息維護控制單元11，以及其他單元，例如單元一12、單元二12等。同樣，在本實施例中，對單元一12等單元不再具體描述。上述用戶設備信息維護控制單元11用於具體地對其所在的無線網絡控制器所負責的區域內的用戶設備3的信息進行維護。
參考圖1，上述用戶設備信息維護控制單元11與上述數據伺服器2相互通訊，並可以向數據伺服器2寫入或讀取數據。
參考圖1，在上述無線網絡控制器所負責的區域內存在多臺用戶設備3，在此不贅述。
本領域的技術人員可以理解，儘管在圖1中僅僅描述了一個數據伺服器2，但當上述絡控制設備1負責維護的區域內的用戶設備3過多的時候，則會造成上述數據伺服器無法存儲全部的用戶設備3的信息，從而造成服務質量下降的問題。此時，可以增加上述數據伺服器2的數量，例如兩臺，甚至多臺。當然，也可以在不增加數據伺服器2數量的前提下通過其他途徑提高數據伺服器2的性能，例如增加其存儲空間等。由於本領域的技術人員對此部分內容可以理解，所以不再贅述。
參考圖2，其描述了本發明的一個實施例中對一個用戶設備信息進行存儲的流程圖。當上述用戶設備信息維護控制單元11接收到存儲一個用戶設備的請求後，首先，用戶設備信息維護控制單元11確定該用戶設備的關鍵字(圖中未示出)，在本實施例中，該等關鍵字是Cell無線網絡臨時標識。而本領域的技術人員理解，在寬帶碼分多址系統中，上述關鍵字還可以採用UTRAN無線網絡臨時標識，在寬帶碼分多址系統以及其他的移動通信系統中，也可以用其他關鍵字，只要該關鍵字可以對用戶設備進行唯一標識即可。
然後，使用一哈希函數對用戶設備信息的關鍵字進行映射，確定其在哈希表中的第一存儲位置，步驟401；接下來，判斷所述第一存儲位置是否空閒，即第一存儲位置與哈希表內數據是否發生衝突，步驟411，如果不衝突，則在該存儲位置存儲該用戶設備信息，步驟402，本次存儲過程結束，否則轉步驟403；接下來，使用探測函數探索下一個存儲位置，步驟403；接下來，判斷探測到的存儲位置是否空閒，即該存儲位置與哈希表內數據是否發生衝突，步驟412，如果不衝突，則在該存儲位置存儲該用戶設備信息，步驟402，本次存儲過程結束，否則轉步驟413；接下來，判斷是否已經達到規定的最大探測次數，413，若沒有達到，則轉步驟413，否則轉步驟404；接下來，以一存儲位置為根節點建立二叉樹，並將該用戶設備的信息存儲到該二叉樹的相應位置，步驟404，本次存儲過程結束。
在本實施例中，上述步驟401中所述的哈希函數是一除餘函數(除留餘數函數)，如下所示
H(K)＝K mod P其中，K表示所述用戶設備信息的關鍵字，P為小於所述哈希表長度的最大指數。在本實施例中，上述P選擇了199，此時的哈希表長度為200。本領域的技術人員可以理解，在其他實施例中，上述P還可以選擇其他數值，例如201、399等。根據發明人的經驗和試驗，上述P的選擇範圍與上述網絡控制設備1所維護的用戶設備3的個數的關係符合經驗公式15％*P＜a＜85％*P時本方法的效果比較好，其中a表示用戶設備3的個數，此時，上述哈希表的效率高，且衝突明顯減少。
上述P的取值和用戶設備的數量以及和上述網絡控制設備的性能有間接的關係。當P值過小，衝突嚴重，會降低存儲效率；P值也不是越大越好，因為如果系統容量較小，而使用較大的P值，運算將會浪費較多的時間。
而在與上述實施例類似的其他實施例中，上述步驟401中所述的哈希函數是一平方取中函數，即從高位開始選取關鍵字的平方的第2、3、4位。例如，以十進位表示的關鍵字1200按照上述平方取中函數處理後得到的哈希地址為440，即其平方的第2、3、4位。相應地，也可以從關鍵字的平方中選取其他位數，例如第3、4、5位等等，這並不影響本發明的實質內容。
同時本領域的技術人員也可以理解，上述將用戶設備關鍵字映射到哈希表的方法也可以採取其他方法，例如直接定址法、數字分析法、摺疊法、隨機數法等。該部分的內容，可以參考現有技術和公知資料來作出適當的變化，例如可以參考《算法和數據結構——C語言描述》(張乃孝主編，高教出版社，2002)、《數據結構——C語言版》(嚴蔚敏、吳偉民，清華大學出版社，1997)、《實用數據結構基礎》(陳明，清華大學出版社，2002)等書籍。本領域的技術人員通過現有技術和公知資料可以了解到更多的關於哈希函數構造的理論，例如可以知道上述P一般接近或等於哈希表的長度，一般選取質數，也可以是不包含小於20質因子的合數等等。
在本實施例中，在上述步驟403中採用開發定址法進行探索，具體而言，採用如下函數Hi(k)＝(H(k)+di)mod m(i＝1，2，…，k(k≤m-1))
其中，K表示所述用戶設備信息的關鍵字，m代表所述哈希表的長度，di代表探索所需要的增量。在本實施例中，di＝1，2，3，4，即進行探測的時候，首先在當前存儲位置的基礎上將K的值增加1並將增加後的存儲位置作為下一個存儲位置，如果仍然衝突，則再增加1，直到增加到4為止探測結束。關於增量的問題，可以參考現有技術和公知資料了解更多的內容，例如參考上述的書籍。
而本領域的技術人員可以理解，在其他實施例中，上述增量也可以選擇其他的方式，例如在另一個實施例中，增量按照如下公式取得di＝12，-12，22，-22應用該增量的探測方法也稱為平方探測法。由於本領域的技術人員可以參考現有技術和公知資料了解更多的內容，例如參考上述的書籍對該等增量的選擇予以理解並實施，所以不再贅述。
而在又一個實施例中，該等增量也可以是一個偽隨機序列。此時，則根據該偽隨機序列進行探索。
在本實施例中，上述探索的次數為4，即當探索了4次後所確定的存儲位置仍然是衝突的，則終止探測步驟，進入下一步驟404。
而在其他類似實施例中，儘管仍然採用本實施例中選用的增量，但探測的次數是6，即在本實施例的基礎上多探測2次。本領域的技術人員可以理解，探測的次數並不影響本發明的實質內容。實際上，探測的次數主要取決於整個移動通信系統的繁忙程度和負載能力，理論上講，如果系統並不繁忙，探測次數可以適當增加，負載能力比較大的時候，探測次數可以增加。根據經驗和試驗，發明人總結探測的次數在3～8次本方法的效果比較好，可以在時間和空間之間取一個比較合理的、被用戶設備所接受的平衡。
在本實施例中，上述探測次數是由管理員預先設定的，在管理員下一次設定該探測次數之前，一直按照該設定的探測次數進行探測。而在其他實施例中，該等探測次數也可以根據系統的具體情況來動態決定，但一旦決定後，在上述網絡控制設備下一次重新啟動之前，該等探測次數將一直保持不變。實際上，本領域的技術人員可以理解，在動態決定探測次數的情況下，主要取決於接入的用戶設備的數量以及系統的內存空間、系統存儲或查找一個用戶設備的時間等因素。
在本實施例中，在上述步驟404中將所探測到的最後一個存儲位置作為根節點建立二叉樹。不論該二叉樹內是否存在除了根節點以外的其它節點數據，都根據二叉樹的規則將上述用戶設備3的關鍵字存儲到二叉樹的一個相應節點上。關於如何按照二叉樹的規則進行存儲，本領域的技術人員可以參考現有技術和公知資料予以理解，例如參考上述的書籍。
而在其他實施例中，在上述步驟404中也可以將探測到的第二個存儲位置作為根節點建立二叉樹。在又一個實施例中，還可以將按照步驟401確定的第一存儲位置作為根節點建立二叉樹。以哪一個存儲位置作為根節點可以預先設定，具體的選擇並不影響本發明的實質內容。
參考圖2，經過圖中所示的步驟，就可以將任何一個用戶設備信息存儲到按照本發明所述方法構建的哈希表二叉樹內。具體而言，首先確定第一存儲位置，如果存在衝突，則根據有限次探索來確定下一個存儲位置，如果不能找到空閒的存儲位置，則將其中的一個存儲位置作為根節點將該用戶設備信息存入二叉樹的相應位置。只要上述的數據伺服器2具有足夠的存儲空間，那麼用戶設備必然可以被存儲至上述的哈希表二叉樹內的一個位置。
相應地，當需要查找一個用戶設備信息時，只要按照圖2所示的以及本發明提供的方法進行查找，就可以查找到該用戶設備的關鍵字，從而進一步查找到該用戶設備的其它信息，例如用戶設備IMSI(國際移動用戶識別符)、連接狀態、RAB(無線接入承載)業務資源分配、承載能力信息、功控信息等等。當上述用戶設備信息的關鍵字與該用戶設備的上述其他信息是分別存儲的，則根據存儲上述用戶的關鍵字的存儲單元包括的地址指針可以進一步查找到該用戶設備的上述其他信息。
類似地，當需要刪除一個用戶設備時，按照上述步驟查找到該用戶設備的關鍵字的存儲位置。當上述用戶設備的所有信息均存儲在該存儲位置，則直接刪除該存儲位置的數據內容即完成刪除操作；當上述用戶設備信息的關鍵字與該用戶設備的上述其他信息是分別存儲的，則根據存儲上述用戶設備信息的關鍵字的存儲單元包括的地址指針進一步查找到該用戶設備的上述其他信息的存儲位置並予以刪除，然後再從所述的哈希表二叉樹中將用戶設備的關鍵字信息刪除。
類似地，也可以完成對一個用戶設備的信息的修改，此過程與刪除過程類似，本領域的技術人員可以理解，不再贅述。
參考圖3a、3b、3c、3d、3e、3f，其共同描述了按照本發明提供的一種在移動通信系統中存儲和維護用戶設備信息的方法，對用戶設備的關鍵字信息進行存儲時數據伺服器中數據存儲的示意圖。
在本實施例中，用戶設備的數量為150個，上述哈希表的長度被設定為200，P的取值為199。假設我們需要處理臨時標識為0000 0000 00000000 0000 0000 1100 1000的用戶設備，以及臨時標識為0000 0000 00000000 0000 0000 1100 1001的用戶設備，以及其他用戶設備。本領域的技術人員可以理解，上述用戶設備的臨時標識系採用二進位表示，為了表述方便，下面將用十進位來予以表示，相應地，上述第一個用戶設備的臨時標識為十進位的200，第二個用戶設備的臨時標識為十進位的201，即兩個用戶設備的關鍵字分別為200、201。類似地，其他用戶設備的臨時標識均採用十進位予以表示。
參考圖3a，上述哈希表二叉樹內已經存儲了關鍵字為200、201和4的三個用戶設備的關鍵字信息，為了詳細地說明使用本發明提供的方法的存儲過程，在下面的過程中，將連續有關鍵字為600、3、1、598、399、996等用戶設備被存儲到上述數據伺服器中。
參考圖3b，如前所述，上述用戶設備信息維護控制單元11接受到存儲關鍵字為600的用戶設備信息的請求後，將按照圖2所述的步驟運行。首先，確定該關鍵字600的第一存儲位置，即600mod199＝3；然後，判斷該存儲位置空閒，即不與上述哈希表二叉樹中的數據發生衝突，所以直接將其存儲到該第一存儲位置，結果即如圖3b所示。
參考圖3c，類似地，上述用戶設備信息維護控制單元11又按照圖2所述步驟存儲關鍵字為3的用戶設備信息。首先，確定該關鍵字3的第一存儲位置，即3mod199＝3；然後，判斷發現該存儲位置不空閒，即已經與上述哈希表二叉樹中的數據發生衝突，所以，開始有限次探測，本實施例按照增量di＝1，2，3，4的方式探測，探測到下一個存儲位置4，發現其仍然衝突，再探測到下一個存儲位置5，發現其空閒，因此，將關鍵字3存儲到該存儲位置5，其結果即如圖3c所示。
參考圖3d，類似地，上述用戶設備信息維護控制單元11又按照圖2所述步驟存儲關鍵字為1的用戶設備信息。首先，確定該關鍵字1的第一存儲位置，即1mod199＝1；然後，判斷發現該存儲位置不空閒，即已經與上述哈希表二叉樹中的數據發生衝突，所以，開始有限次探測，首先探測到下一個存儲位置2，發現其衝突，再探測到下一個存儲位置3，仍然衝突，以及探測到存儲位置4、5，均衝突。此時，已經達到探測的最大次數4次，所以停止探測，並將所探測到的最後一個存儲位置作為根節點建立二叉樹並將關鍵字1存儲到該二叉樹中相應的位置。由於該二叉樹的根節點已經存儲了關鍵字3，所以，將關鍵字1存儲到根節點的左分支上，結果即如圖3d所示。
參考圖3e，類似地，上述用戶設備信息維護控制單元11又按照圖2所述步驟存儲關鍵字為598的用戶設備信息。仍然類似地，首先發現第一存儲位置1衝突，經過4次探測後發現探測到的下一個存儲位置均衝突，所以以最後一個存儲位置作為根節點建立二叉樹並將關鍵字598存儲到該二叉樹中相應的位置。由於該二叉樹的根節點已經存儲了關鍵字3、1，所以，將關鍵字598存儲到根節點的右分支上，結果即如圖3e所示。
參考圖3f，類似地，上述用戶設備信息維護控制單元11又分別按照圖2所述步驟存儲關鍵字為399和關鍵字為996的用戶設備信息。該兩個關鍵字最終都存儲到以存儲位置5為根節點的二叉樹內，結果即如圖3f所示。
本領域的技術人員可以理解，二叉樹的本身的定義決定了上述關鍵字1、598、399、996必然在該二叉樹中有一個唯一的存儲位置。該部分內容，本領域的技術人員可以參考現有技術以及公知資料予以理解並實施，例如參考上述列舉的書籍。例如，通過該等公知資料，可以了解二叉樹具有如下性質1)一個節點最多只能有兩個子節點；2)每一個節點存在一個鍵值(Key Value)來標識這個節點；3)左子樹的鍵值必須小於父節點的鍵值；4)右子樹的鍵值必須大於或者等於父節點的鍵值等等。
同樣，本領域的技術人員可以理解，在一個實際應用的移動通信系統中，上述用戶設備的數量要遠遠多於上述實施例中所述的150個，一般而言，在一個寬帶碼分多址系統中，用戶設備往往高達數十萬。而上述實施例，僅僅是為了描述清楚將系統的容量人為地縮小，但這並不影響本發明的實質內容，本領域的技術人員根據本發明內容以及上述實施例以及公知資料可以理解本發明並予以實施。
參考圖4，其描述了另一個實施例中用於存儲用戶設備信息的二叉樹哈希表的示意圖。在該實施例中，與圖3a～3f所示實施例不同的是，在確定二叉樹的根節點時，不是以探測到的最後一個存儲位置作為根節點，而是以探測到的第一個存儲位置為根節點。所以，在該實施例中，圖3e所示的存儲結果就改變為圖4所示的存儲結果。本領域的技術人員可以理解，上述根節點的具體選擇方式並不影響本發明的實質內容，技術人員在理解本發明內容的基礎上可以對此作出適當的變化。例如，對探測方式作出適當的變化又可以形成新的實施例，此時圖3a～3f所示的存儲示意圖又會有新的變化。
參考圖3a、3b、3c、3d、3e、3f以及圖4，該等圖中僅僅示出了在所述哈希表二叉樹中存儲所述用戶設備信息的關鍵字。在本實施例中，所述哈希表二叉樹的每個存儲單元還包括指向所述用戶設備的其他信息的存儲單元的地址指針，如圖5所示，在實際操作中，先行按照現有技術將所述用戶設備的其他信息存儲到相應的存儲單元內，然後將該存儲單元的地址指針以及該用戶設備信息的關鍵字存儲到所述哈希表二叉樹內，從而完成一個存儲過程。而在其他實施例中，也可以直接將該用戶設備的所有信息，包括關鍵字和其他信息，例如用戶設備國際移動用戶識別符、連接狀態、無線接入承載、業務資源分配、承載能力信息、功控信息等直接存儲到所述哈希表二叉樹內。本領域的技術人員參考現有技術以及公知資料對此可以理解並實施，不再贅述。
參考圖5，其描述了本發明的一個實施例中的哈希表二叉樹結構中一個二叉樹節點的數據結構。該數據結構包括四個數據域，分別為關鍵字域51，其存儲用戶設備的關鍵字信息，參考圖5，在本實施例中，該關鍵字的內容為3；以及地址指針52，用於存儲指向該用戶設備其他信息存儲地址的指針，在本實施例中即為關鍵字為3的用戶設備的其他信息存儲地址的指針；以及二叉樹的左地址指針53，用於存儲該二叉樹節點的左子樹的指針，參考圖3e、3f，即為關鍵字為1的二叉樹節點的地址指針；以及二叉樹的右地址指針54，用於存儲該二叉樹節點的右子樹的指針，參考圖3e、3f，即為關鍵字為598的二叉樹節點的地址指針。參考圖5，儘管上述的地址52、二叉樹的左地址指針53以及二叉樹的右地址指針54均未示出，但本領域的技術人員可以理解上述數據結構的內容並可以具體實施，在此不贅述。
儘管本發明已經以如上所述的優選實施例予以說明，但上述實施例並非用來限定本發明，任何對該領域熟悉的技術人員，根據本發明的設計思想、具體發明內容以及實施例的啟示，應該可以各種改動和調整，而通過這些改動和調整所得到的新的內容應被本發明內容所涵蓋。
權利要求
1.一種在移動通信系統中存儲和維護用戶設備信息的方法，應用於該移動通信系統的網絡控制設備(1)中的用戶設備信息維護控制單元(11)中，其特徵在於，該方法通過如下步驟完成將一個用戶設備(3)信息存儲至數據伺服器(2)內的過程步驟一，使用一哈希函數對用戶設備信息的關鍵字進行映射，確定其在哈希表中的第一存儲位置；步驟二，若所述第一存儲位置與哈希表內數據不發生衝突，則按照所述第一存儲位置存儲所述用戶設備信息，否則重複步驟一、二進行有限次數的探索以探索下一個存儲位置，若在有限次內完成存儲操作則存儲過程完畢，否則轉步驟三；步驟三，以上述存儲位置中的一個存儲位置作為根節點建立二叉樹，並按照二叉樹存儲規則將所述用戶設備信息存儲到二叉樹相應的位置。
2.如權利要求1所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述的用戶設備信息的關鍵字是用戶設備(3)的標識信息。
3.如權利要求1或2所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述的移動通信系統是寬帶碼分多址系統，所述的用戶設備信息的關鍵字是UTRAN無線網絡臨時標識。
4.如權利要求1或2所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述的移動通信系統是寬帶碼分多址系統，所述的用戶設備信息的關鍵字是Cell無線網絡臨時標識。
5.如權利要求1所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，該方法通過如下步驟查找一個用戶設備(3)信息步驟一，使用一哈希函數對用戶設備信息的關鍵字進行映射，確定其在哈希表中的第一存儲位置；步驟二，若所述第一存儲位置存儲的關鍵字與待查找的關鍵字符合，則本次查找結束，否則重複步驟一、二進行有限次數的探索以探索下一個存儲位置，若在有限次內完成查找則本次查找結束，否則轉步驟三；步驟三，以上述存儲位置中的一個存儲位置作為根節點按照二叉樹規則進行查找直到找到一節點所存儲的關鍵字與待查找的用戶設備信息的關鍵字符合，或者查找失敗。
6.如權利要求1或5所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述的存儲位置或二叉樹的節點對應的存儲單元僅存儲所述用戶設備信息的關鍵字，且該存儲單元還包括指向所述用戶設備其他信息的存儲單元的地址指針。
7.如權利要求1或5所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述哈希函數是一除餘函數，即H(K)＝K modP，其中，K表示所述用戶設備信息的關鍵字，P為小於所述哈希表長度的最大指數。
8.如權利要求7所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述指數P與網絡控制設備所維護的用戶設備(3)的個數a的優選關係應符合關係式15％*P＜a＜85％*P。
9.如權利要求1或5所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，在所述步驟二中使用開放定址法進行有限次探索，即使用如下函數Hi(k)＝(H(k)+di)mod m(i＝1，2，...，k(k≤m-1))，其中，K表示所述用戶設備信息的關鍵字，m代表所述哈希表的長度，di代表探索所需要的增量。
10.如權利要求9所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述增量是di＝1，2，3，4...n，其中n≤P。
11.如權利要求9所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述增量是di＝12，-12，22，-22...-n2，其中n≤P。
12.如權利要求9所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述增量為一偽隨機序列。
13.如權利要求1所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述有限次探索的次數是預先設定的。
14.如權利要求1所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述有限次探索的次數是動態確定的。
15.如權利要求1或10或11或13或14所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述有限次探索的優選次數以及增量的優選次數為大於等於3小於等於8。
16.如權利要求1或5所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述哈希函數是一平方取中函數，即將關鍵字平方後取其第2、3、4位作為哈希地址。
17.如權利要求1或5所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述步驟三中作為根節點的存儲位置是預先指定的。
18.如權利要求17所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述步驟三中作為根節點的存儲位置是所探測到的最後一個存儲位置。
19.如權利要求17所述的一種在移動通信系統中存儲和維護用戶設備信息的方法，其特徵在於，所述步驟三中作為根節點的存儲位置是所探測到的第一個存儲位置或第二個存儲位置。
20.一種移動通信系統，包括網絡控制設備(1)，其提供基站管理、無線資源管理、基站功率控制、用戶接入管理和移動性管理等功能，以及數據伺服器(2)，用於存儲用戶設備信息，該網絡控制設備(1)包括一用戶設備信息維護控制單元(11)，對該移動通信系統中的用戶設備信息進行存儲和維護，其特徵在於，所述單元(11)按照如權利要求1或2或5所述的方法對該等用戶設備信息進行存儲和維護。
21.如權利要求20所述的一種移動通信系統，其特徵在於，所述的移動通信系統是寬帶碼分多址系統，所述的用戶設備信息以UTRAN無線網絡臨時標識或Cell無線網絡臨時標識作為關鍵字。
全文摘要
一種在移動通信系統中存儲和維護用戶設備信息的方法，應用於該移動通信系統的網絡控制設備(1)中的用戶設備信息維護控制單元(11)中，其將一個用戶設備(3)信息存儲在數據伺服器(2)中的過程包括使用一哈希函數對用戶設備信息的關鍵字進行映射，確定其在哈希表中的第一存儲位置的步驟；若第一存儲位置與哈希表內數據不發生衝突，則進行有限次探索以探索下一個存儲位置的步驟；以上述存儲位置中的一個存儲位置作為根節點建立二叉樹，並將所述用戶設備信息存儲到二叉樹的步驟。本發明提供的方法可以應用於寬帶碼分多址系統等移動通信系統中，可以大大節省存儲空間並提供查找用戶設備的效率。
文檔編號H04W84/02GK101043695SQ20061002501
公開日2007年9月26日 申請日期2006年3月23日 優先權日2006年3月23日
發明者李勇, 杭月 申請人:上海宇夢通信科技有限公司