[發明專利]一種異步鄰居發現方法

無效

• 申請號: 201310314798.2
• 申請日: 2013-07-24
• 公開（公告）號: CN103428821A
• 公開（公告）日: 2013-12-04
• 發明（設計）人: 黃勁草;陳力軍;陳華瑋;糜軍;錢彥立
• 申請（專利權）人: 上海傲藍信息科技有限公司
• 主分類號: H04W48/16
• 分類號: H04W48/16
• 代理公司: 上海精晟知識產權代理有限公司 31253
• 代理人: 馮子玲

技術領域

本發明涉及通信領域，具體涉及一種異步鄰居發現方法。?

背景技術

在無線網絡中，特別是無線傳感器網絡，鄰居發現是一個艱巨的任務。在節點不移動時，節點可以付出一次性代價學習存在的鄰居，以優化媒體訪問和路由支持。?

通常的鄰居節點發現協議采用中心控制器協調。這類方法中，所有的節點報告給中心控制器，中心控制器確定節點信息包括計算其位置、鄰居節點和其它信息，然后逐一通報給每一個節點。中心控制器方式需要消耗大量能量，特別在節點規模很大時，本發明為分布式算法，采用節點互相協作，沒有中心控制器協調。?

在Baker?and?Ephremides的分布式算法中，所有節點參與2輪輪轉調度（schedule?round?robin）。在假設節點可以無誤碼的從鄰居接收消息的條件下。在每一輪，每一個節點分配一個時隙用于發布其身份和已發現的鄰居節點的信息，其他節點則在另外時隙監聽，并且在二輪內可以確定其鄰居和鄰居的鄰居節點信息。然而此算法需要全局網絡時間同步。鄰居發現算法通常是最早運行的，隨后的網絡行為才可以假設某些機制以增強同步，但是對于最先運行，不可能具備這種假設的基礎。其次，隨著網絡節點規模增加，通過維護全局同步將成為沉重的資源消耗負擔，同樣，采用硬件手段如GPS來維護全局同步，也將帶來額外巨大的成本。?

發明內容

本發明的目的在于提供一種異步的分布式鄰居發現方法，包括以下步驟：?

1）定義一節點x以及一節點y，其中節點x超出節點y的信噪比要求，其中，所述節點x、節點y均有一個鄰居數的估計值，且有唯一身份識別信息；?

2）定義一消息m，該消息m用于識別發送者，該消息m用于在發送給接收節點，在距離d內，如果沒有其他節點同時發射，接收節點成功接收消息m；?

3）在所述節點x發現節點y時，如果節點x和y是鄰居，則節點x從節點y接收到至少一次消息m；?

4）給定一個有限節點的集合，每個節點都有一個鄰居節點有限集。?

在本發明的一個優選實施例中，節點x、節點y均有網絡接口ID、MAC地址或CPU?ID中的一種，且所述網絡接口ID、MAC地址或CPU?ID能夠被查詢。?

在本發明的一個優選實施例中，消息m應包含一個長前導。?

在本發明的一個優選實施例中，在步驟4）中，給定一個有限節點的集合，每個節點都有一個鄰居節點有限集；如果節點x、y是鄰居，網絡鄰居關系的有限集合包括(x，y)和(y，x)。?

特別需要說明的是，有限集合為對可能的節點位置和時鐘偏移的統計期望?

本發明的有益效果在于：?

采用分布式鄰居發現方法，不需要全局同步，在節點規模較大的情況下能夠有效節省資源。?

具體實施方式

為使本發明實現的技術手段、創作特征、達成目的與功效易于明白了解，下面結合具體實施方式，進一步闡述本發明。?

本發明所述的一種異步鄰居發現方法，包括以下步驟：?

1）定義一節點x以及一節點y，其中節點x超出節點y的信噪比要求；其中，節點x、節點y均有一個鄰居數的估計值，每個節點可以廣播消息或在任意時刻接收一個廣播消息，但是節點不能同時發送和接收。在只有一個鄰居發送?的假設下，接收鄰居發送的廣播消息無差錯。?

此外，每個節點具有其自身的唯一身份識別信息，一個節點有其唯一的身份識別可以有多種方式實現，如網絡接口ID、MAC地址或CPU?ID中的一種，且所述網絡接口ID、MAC地址或CPU?ID能夠被查詢，其唯一性由設備制造商保證。?

估計鄰居數常常在多跳網絡中要求滿足。已知區域部署傳感器節點數可以用來估計鄰居數，估計還要考慮在期望的傳播環境下節點的無線覆蓋范圍。?

2）定義一消息m，該消息m用于識別發送者，該消息m用于在發送給接收節點，在距離d內，如果沒有其他節點同時發射，接收節點成功接收消息m。假設m可以在時間Tm內發送給接收節點，在距離d內如果沒有其他節點同時發射，也即在接收端沒有傳輸碰撞時，接收節點成功接收消息m。?

考慮到沒有全局同步，消息m應包含一個長前導（Preamble），因此，這使得在開始時對接收節點能夠接收m而不是中間插入接收是非常重要的。?

3）在所述節點x發現節點y時，如果節點x和y是鄰居，則節點x從節點y接收到至少一次消息m。?

4）給定一個有限節點的集合，每個節點都有一個鄰居節點有限集。?