[發(fā)明專利]時(shí)鐘節(jié)點(diǎn)結(jié)群方法以及時(shí)鐘網(wǎng)絡(luò)結(jié)構(gòu)

有效

• 申請(qǐng)?zhí)枺?/td>: 201310077342.9
• 申請(qǐng)日: 2013-03-12
• 公開（公告）號(hào): CN103150435A
• 公開（公告）日: 2013-06-12
• 發(fā)明（設(shè)計(jì)）人: 蔡懿慈;周強(qiáng);鄧超
• 申請(qǐng)（專利權(quán)）人: 清華大學(xué)
• 主分類號(hào): G06F17/50
• 分類號(hào): G06F17/50
• 代理公司: 北京聿宏知識(shí)產(chǎn)權(quán)代理有限公司 11372
• 代理人: 吳大建;鐘日紅

1.一種時(shí)鐘節(jié)點(diǎn)結(jié)群方法，包括：

確定步驟，確定版圖中的時(shí)鐘節(jié)點(diǎn)；

劃分步驟，將所述時(shí)鐘節(jié)點(diǎn)劃分為K個(gè)時(shí)鐘節(jié)點(diǎn)簇，作為初始時(shí)鐘節(jié)點(diǎn)結(jié)群，其中，K為大于等于1的整數(shù)；

結(jié)群步驟，對(duì)所述初始時(shí)鐘節(jié)點(diǎn)結(jié)群進(jìn)行優(yōu)化，得到最優(yōu)時(shí)鐘節(jié)點(diǎn)結(jié)群。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，在所述劃分步驟中，進(jìn)一步包括，

基于所述時(shí)鐘節(jié)點(diǎn)構(gòu)造完全帶權(quán)無(wú)向圖，其中，該圖的頂點(diǎn)集由所述時(shí)鐘節(jié)點(diǎn)構(gòu)成，該圖的邊集由所述時(shí)鐘節(jié)點(diǎn)兩兩連接構(gòu)成，各個(gè)邊的權(quán)值為相互連接的兩個(gè)時(shí)鐘節(jié)點(diǎn)之間的曼哈頓距離；

生成所述完全帶權(quán)無(wú)向圖的最小生成樹；

在所述最小生成樹中，將權(quán)值大于設(shè)定值的邊刪除以形成帶權(quán)無(wú)向圖；

將所述帶權(quán)無(wú)向圖劃分成K個(gè)無(wú)向子圖以構(gòu)成所述K個(gè)時(shí)鐘節(jié)點(diǎn)簇，將所述K個(gè)時(shí)鐘節(jié)點(diǎn)簇作為初始時(shí)鐘節(jié)點(diǎn)結(jié)群。

3.根據(jù)權(quán)利要求2所述的方法，其特征在于，

利用Kruskal算法生成所述完全帶權(quán)無(wú)向圖的最小生成樹。

4.根據(jù)權(quán)利要求2所述的方法，其特征在于，

利用深度優(yōu)先搜索算法將所述帶權(quán)無(wú)向圖劃分成K個(gè)無(wú)向子圖。

5.根據(jù)權(quán)利要求2所述的方法，其特征在于，通過以下表達(dá)式來(lái)計(jì)算所述設(shè)定值EL，

EL=α×Width×LengthNum]]>

其中，Width表示所述版圖的寬度，Length表示所述版圖的長(zhǎng)度，Num所述版圖的時(shí)鐘節(jié)點(diǎn)數(shù)目，α表示可調(diào)節(jié)常數(shù)，用于調(diào)節(jié)結(jié)群的數(shù)量。

6.根據(jù)權(quán)利要求1至5中任一項(xiàng)所述的方法，其特征在于，在所述結(jié)群步驟中，進(jìn)一步包括，

步驟31，計(jì)算所述初始時(shí)鐘節(jié)點(diǎn)結(jié)群中的每個(gè)時(shí)鐘節(jié)點(diǎn)簇的幾何中心，得到K個(gè)聚類中心；

步驟32，計(jì)算所述初始時(shí)鐘節(jié)點(diǎn)結(jié)群中所有時(shí)鐘節(jié)點(diǎn)簇的總線長(zhǎng)；

步驟33，清空所有時(shí)鐘節(jié)點(diǎn)簇；

步驟34，對(duì)于每個(gè)時(shí)鐘節(jié)點(diǎn)，計(jì)算與其距離最近的聚類中心，并將該時(shí)鐘節(jié)點(diǎn)加入到該聚類中心所在的時(shí)鐘節(jié)點(diǎn)簇中，重新形成K個(gè)時(shí)鐘節(jié)點(diǎn)簇；

步驟35，重新計(jì)算每個(gè)時(shí)鐘節(jié)點(diǎn)簇的幾何中心，并更新K個(gè)聚類中心；

步驟36，重新計(jì)算所有時(shí)鐘節(jié)點(diǎn)簇的總線長(zhǎng)，判斷該總線長(zhǎng)與上一次計(jì)算得到的總線長(zhǎng)是否相等，若相等，則將重新形成的K個(gè)時(shí)鐘節(jié)點(diǎn)簇作為最優(yōu)時(shí)鐘節(jié)點(diǎn)結(jié)群，否則返回步驟33。

7.根據(jù)權(quán)利要求6所述的方法，其特征在于，所述時(shí)鐘節(jié)點(diǎn)簇的幾何中心，通過以下步驟計(jì)算：

如果該時(shí)鐘節(jié)點(diǎn)簇不為空，則其幾何中心為該時(shí)鐘節(jié)點(diǎn)簇所包含時(shí)鐘節(jié)點(diǎn)的位置坐標(biāo)的平均值；

如果該時(shí)鐘節(jié)點(diǎn)簇為空，則其幾何中心為當(dāng)前包含時(shí)鐘節(jié)點(diǎn)數(shù)目最多的時(shí)鐘節(jié)點(diǎn)簇中一半時(shí)鐘節(jié)點(diǎn)的位置坐標(biāo)的平均值。

8.根據(jù)權(quán)利要求6所述的方法，其特征在于，所述所有時(shí)鐘節(jié)點(diǎn)簇的總線長(zhǎng)為所有時(shí)鐘節(jié)點(diǎn)簇內(nèi)各個(gè)時(shí)鐘節(jié)點(diǎn)與該時(shí)鐘節(jié)點(diǎn)簇的幾何中心的連線長(zhǎng)度的總和。

9.根據(jù)權(quán)利要求1所述的方法，其特征在于，還包括，

將時(shí)鐘節(jié)點(diǎn)數(shù)據(jù)存入設(shè)定的數(shù)據(jù)結(jié)構(gòu)中，其中設(shè)定的數(shù)據(jù)結(jié)構(gòu)包括時(shí)鐘節(jié)點(diǎn)的二維坐標(biāo)，電容值和節(jié)點(diǎn)序號(hào)。

10.一種時(shí)鐘網(wǎng)絡(luò)結(jié)構(gòu)，包括：

根據(jù)權(quán)利要求1至9中任一項(xiàng)所述的方法得到的版圖中的K個(gè)時(shí)鐘節(jié)點(diǎn)簇，K為大于等于1的整數(shù)；

用于驅(qū)動(dòng)時(shí)鐘節(jié)點(diǎn)簇的K個(gè)緩沖器，

其中，各個(gè)緩沖器設(shè)置在其所要驅(qū)動(dòng)的時(shí)鐘節(jié)點(diǎn)簇的內(nèi)部，該時(shí)鐘節(jié)點(diǎn)簇中的各個(gè)時(shí)鐘節(jié)點(diǎn)與該緩沖器直接相連。