[發明專利]基于有向非循環圖成員關系的用于路徑計算的控制集標識

有效

• 申請號: 201480051378.2
• 申請日: 2014-09-17
• 公開（公告）號: CN105557028B
• 公開（公告）日: 2019-06-21
• 發明（設計）人: 帕斯卡·舒伯特;讓-菲利普·瓦瑟爾;帕特里克·韋特瓦爾德
• 申請（專利權）人: 思科技術公司
• 主分類號: H04W40/12
• 分類號: H04W40/12;H04W84/18;H04L12/717
• 代理公司: 北京東方億思知識產權代理有限責任公司 11258
• 代理人: 李曉冬

在一個實施例中，方法包括：路徑計算設備接收來自成員網絡設備的設備信息，每一個成員網絡設備屬于到低功率損耗網絡中的目的地的有向非循環圖；以及路徑計算設備將屬于有向非循環圖的每一個成員網絡設備歸類為屬于用于生成不同于任何有向非循環圖的經優化的路由的控制集，該經優化的路由用于到達控制集的成員網絡設備中的任何一個成員網絡設備。

技術領域

本公開一般涉及對具有大量網絡設備的設備網絡(例如，具有成千(上萬)個傳感器設備的低功率損耗網絡(LLN))中的網絡設備之間的時隙化信道跳躍(channel hopping)路由進行優化的路徑計算元件(PCE)。

背景技術

這部分描述了可以被采用的方法，但并不一定是此前已經被設想或采用的方法。因此，除非明確指出，否則這部分所描述的任何方法均不是本申請的權利要求的現有技術，并且這部分所描述的任何方法不因為被包括在這部分中而被承認為現有技術。

低功率和損耗網絡(LLN)允許大量(例如，成千上萬)的資源受限設備被互聯以形成無線網狀網。互聯網工程任務組(IETF)已經提出了使用基于IEEE 802.15.4e的時隙化信道跳躍(TSCH)來提供IPv6路由的路由協議(“6TiSCH”)。盡管諸如路徑計算實體(PCE)之類的集中式實體可以被用于小數目的不同網絡設備之間的路由計算，但是PCE計算TSCH調度的復雜度將網絡中的網絡設備的數目限制為少于一百(100)個網絡設備，或者更典型地不多于約三十(30)個網絡設備，這是因為PCE不能維持較大數目的網絡設備之間的對等。因此，PCE不能計算包含較大數目的網絡設備的數據網絡中的網絡設備之間的6TiSCH路由。

附圖說明

參考附圖，其中具有相同參考數字標號的元素自始至終表示相似的元素，并且其中：

圖1根據示例性實施例示出具有用于將屬于有向非循環圖的網絡設備歸類為屬于用于生成網絡內的經優化的路由的控制集(dominating set)的裝置的示例性系統；

圖2根據示例性實施例示出具有圖1的網絡內的經優化的路由的網絡設備的示例性控制集；

圖3根據示例性實施例示出圖1的網絡設備或路徑計算設備中的任何一個的示例性實施方式；

圖4根據示例性實施例示出圖1的網絡設備和路徑計算設備的示例性方法，該方法導致生成低功率損耗網絡內的經優化的路由。

具體實施方式

概述

在一個實施例中，方法包括：路徑計算設備接收來自成員網絡設備的設備信息，每一個成員網絡設備屬于到低功率損耗網絡中的目的地的有向非循環圖；以及路徑計算設備將屬于有向非循環圖的每一個成員網絡設備歸類為屬于用于生成不同于任何有向非循環圖的經優化的路由的控制集，該經優化的路由用于到達該控制集中的任何一個成員網絡設備。

在另一實施例中，裝置包括網絡接口電路和處理器電路。網絡接口電路被配置為接收來自成員網絡設備的設備信息，每一個成員網絡設備屬于到低功率損耗網絡中的目的地的有向非循環圖。處理器電路被配置為將屬于有向非循環圖的每一個成員網絡設備歸類為屬于用于生成不同于任何有向非循環圖的經優化的路由的控制集，以到達該控制集中的任何一個成員網絡設備。

在另一實施例中，方法包括：低功率損耗網絡中的網絡設備加入到目的地的有向非循環圖；以及網絡設備響應于加入有向非循環圖，向路徑計算設備發送設備信息，使該路徑計算設備能夠將網絡設備添加至用于由路徑計算設備生成用于到達低功率損耗網絡中的任何一個網絡設備的經優化的路由的網絡設備的控制集，該經優化的路由不同于任何有向非循環圖。

詳細描述