聲音·圖像通信系統的製作方法

2023-10-08 19:39:39

專利名稱：聲音·圖像通信系統的製作方法
技術領域：
本發明涉及一種聲音，圖像通信系統，特別涉及一種使網際網路中的P2P
技術得以發展的聲音 圖像通信系統。
背景技術：
近年來，網際網路的普及令人吃驚，能以廉價的裝置在世界範圍的使用
者之間進行信息交換。特別是，P2P技術無需使用昂貴的伺服器，就能在 大量的「節點」之間直接進行信息交換，並且因設備的故障而引起的影響 的範圍較小等，在這些方面引人注目。
作為已使用P2P技術的系統，以往已知有SKYPE、電子黑板系統(參 照非專利文獻1)、 BATON(參照非專利文獻2)等。
SKYPE是使用了 P2P技術的IP電話系統，其不使用伺服器，通話費 用是免費的，即使有防火牆也能使用。但是，可通話範圍最多只有5人， 具有不能與大量的節點進行通信的問題。
電子黑板系統是使用了 P2P技術的教育輔助系統，通過用完全二叉樹 結構來結合多個節點，從而能夠向大量的節點發送大量的數據。但是具有 的問題是，在節點管理中使用了群組管理員，節點數量變多時管理可能會 變得不周密，只限於單一數據的一對多的數據傳送，且在群組內只能共有 一個數據。
BATON是使用了平衡二叉樹結構的P2P檢索系統，能在O(logN)的時
間內進行節點的添加、刪除、檢索，而不對根節點帶來負擔。但是具有的 問題是，其需要維持管理節點中包含的表格，有時在節點的添加、刪除中 需要多個移動樹的節點，若在短時間內發生多次該情況，難以維持樹。
非專利文獻1:用於使用了 TCP的分散網絡環境的電子黑板系統(TCP ^利用L/t分散氺:y卜7 —夕環境(D/i力(D電子黒板、乂只於厶)，情報處理
5學會論文集，第43巻，第1號，第176 184頁
非專利文獻2: BATON,用於對等網絡的平衡樹結構(A Balanced Tree Structure for Peer-to-Peer Networks),第31屆VLDB會議論文集，第661 672頁

發明內容
因此，本發明的目的在於提供一種聲音 圖像通信系統，該聲音，圖 像通信系統當然是使用P2P技術和網際網路，能夠在世界範圍內實時廉價且 越過防火牆進行聲音 圖像通信，而且還能在大量節點間同時發送接收， 並能夠靈活地處理新節點的參加或脫離。
為實現上述目的，第1發明為.-
一種聲音 圖像通信系統，其特徵在於，
參加一個通話群組的節點具有第1及第2下位節點連接部，且進行節 點的添加，來保存與第l及第2下位節點連接的節點的總數，並使得與第1 及第2下位節點連接部連接的節點數量變得相同，從而自主地進行連接的 調整，使得節點間的結合變成完全二叉樹結構，
所述通話群組內的一個節點發送的數據在與節點數量的對數成正比的 時間內，到達通話群組內所有的節點。
另外，第2發明為
一種用完全二叉樹結構結合了多個節點的聲音 圖像通信系統，其特 徵在於，
所述各節點至少具有對上位節點的TCP(Transmission Control Protocol:
傳輸控制協議)連接部、對第l及第2下位節點的連接部、和控制程序，至 少具有第1下位節點的權重信息及第2下位節點的權重信息，
用完全二叉樹結構構成群組時，根節點在其第l下位節點連接部為空 時將新節點與第1下位節點連接部連接並對第1下位節點的權重信息加 "1"，而在第1下位節點連接部不為空且第2下位連接部為空時將新節點 與第2下位節點連接部連接並對第2下位節點的權重信息加"1"，除此以 外若第1下位節點的權重信息為第2下位節點的權重信息以下，則向第1下位節點詢問添加新節點並對第I下位節點的權重信息加"1"，而若第1 下位節點的權重信息超過第2下位權重信息，則向第2下位節點詢問添加 新節點並對第2下位節點的權重信息加"1"。
本發明所涉及的聲音 圖像通信系統中，由於用完全二叉樹結構結合
多個節點，因此無需昂貴的伺服器，就能夠以使P2P技術得以發展的形式、
越過防火牆而於世界範圍內實時地在大量節點間同時發送接收聲音，圖像， 在與節點數量的對數成正比的時間內到達通話群組內的所有節點。
而且，由於各節點具有對上位節點的TCP連接部、及對第1及第2下 位節點的連接部，並具有第1下位節點的權重信息及第2下位節點的權重 信息，因此根據第l及第2下位節點的權重信息，能夠靈活地處理新節點 的參加或脫離，可在極短的時間內完成節點的添加、刪除。另外，節點脫 離時或節點發生故障時，其對整體也沒有影響。
這裡，對本發明所涉及的聲音 圖像通信系統和現有已知的SKYPE、 電子黑板系統及BATON進行簡單的比較。
SKYPE是使用了 P2P技術的IP電話系統。能夠參加一個通話群組的 節點數量如圖l(A)所示最多為5。與此不同的是，本發明所涉及的通信系 統如圖1(B)所示，是用完全二叉樹結構結合多個節點而成的，能使多個節 點參加，並能夠以參加節點數量的對數的時間延遲進行對話，能在短時間 內處理節點的添加、檢索。
電子黑板系統如圖2(A)所示，在節點管理中使用群組管理員，節點用 完全二叉樹結構進行結合。使用群組管理員這一點使得管理變得繁瑣。與 此不同的是，本發明所涉及的通信系統如圖2(B)所示，雖然在各節點用完 全二叉樹結構進行結合這一點上是相同的，但採用的方式是，不具有群組 管理員，所有節點自主地進行動作，對大量的節點是節點自身進行自我管 理。因此，即使節點的參加、脫離發生多次，但對於特定的節點集中的負 荷也較少。
BATON如圖3(A)所示，是使用了平衡二叉樹結構的P2P系統，各節 點具有圖3(B)所示的長度可變的路由表。因此，需要對該表格進行維持管 理。因節點的添加、刪除而導致樹的平衡被破壞時，需要移動多個節點，此時也需要改變路由表。與此不同的是，本發明所涉及的通信系統具有圖
3(C)所示的數據結構，具有對上位節點的TCP連接部、對左側下位節點的
連接部(套接字)及對右側下位節點的連接部(套接字)、和控制程序，並具有 左側下位節點的權重信息及右側下位節點的權重信息。由於不具有維持構 成樹的節點用的長度可變的數據結構，因此節點添加時、脫離時的處理簡
單而高速。雖然處理時間兩者都是O(logN)，但BATON較為複雜。另外， 本發明所涉及的通信系統的情況下，在添加、刪除節點時移動的節點只須 -個即可。


圖l(A)是表示SKYPE的基本結構的說明圖，(B)是表示本發明所涉及 的聲音 圖像通信系統的基本結構的說明圖。
圖2(A)是表示電子黑板系統的基本結構的說明圖，(B)是表示本發明所 涉及的聲音 圖像通信系統的基本結構的說明圖。
圖3(A)是表示BATON的基本結構的說明圖，(B)是BATON的各節點 保存的路由表的圖表，(C)是表示本發明所涉及的聲音 圖像通信系統的各 節點的數據結構的說明圖。
圖4是表示本發明所涉及的聲音 圖像通信系統中、各節點的數據結
構的說明圖。
圖5是表示本發明所涉及的聲音 圖像通信系統中、代理對象的數據 結構的說明圖。
圖6是表示本發明所涉及的聲音 圖像通信系統中、完全二叉樹結構 的說明圖。
圖7是表示本發明所涉及的聲音 圖像通信系統中、待機群組節點的
數據結構的說明圖。
圖8是表示本發明所涉及的聲音 圖像通信系統中、通話群組節點的 數據結構的說明圖。
圖9是表示本發明所涉及的聲音*圖像通信系統中、9個終端構成待機 群組和兩個通話群組的例子的說明圖。
8[0是表示為了成為完全二叉樹結構而定期進行的處理的流程圖。 1是表示將左右權重的總和向上位節點傳達的處理的流程圖。 12是表示從上位節點沒有反應時的處理的流程圖。 [3是表示添加新節點的處理的流程圖。
[4是表示已詢問添加新本地節點時的處理的流程圖。
是表示呼叫對方的處理的流程圖。
16是表示節點檢索處理的流程圖。 口是表示節點並行檢索處理的流程圖。 8是表示節點並行檢索處理的流程圖。 [9是表示上位節點交換處理的流程圖。 圖20是表示發生故障時獲取新節點候補的處理的流程圖。 圖21是表示本發明所涉及的聲音 圖像通信系統中、節點的連接變更 處理的說明圖。
圖22是表示連接變更處理的流程圖。
具體實施例方式
下面參照附圖對本發明所涉及的聲音 圖像通信系統的實施例進行說明。
(基本使用方法)
將本通信系統的終端的軟體安裝在個人計算機中。或者，準備已安裝 了終端軟體的終端(便攜終端或寬帶路由器等)。然後進行用戶註冊等初始設 定。在用戶側無需區別本地地址/全局地址。接著，啟動終端。由此，終端 變成「待機狀態」。若使軟體結束、或切斷終端的電源，則結束待機狀態。
(基本通話)
在待機狀態的終端指定對方的用戶ID(使用郵件地址)並點擊「呼叫」 按鈕。若對方為待機狀態，則會出現對方側終端的呼叫音。或者，出現呼 叫狀態的顯示。若在通話中，則會在呼叫側出現通話中的顯示，在接收側 出現表示有呼叫的意思的顯示。此時，若進行呼叫側地址通知設定，則會 顯示該地址。若對方側點擊「通話」按鈕，則變成通話狀態，成為可視電話通話。 也可設置不發送圖像的按鈕。然後，若點擊「切斷」按鈕，則結束通話， 終端變成待機狀態。
(群組通話)
已呼叫對方時，若在通話中，則會在呼叫側出現通話中的顯示，在接 收側出現表示有呼叫的意思的顯示。此時，若呼叫側進行用戶ID通知設定， 則會顯示此ID。這裡，若在接收側點擊「通話」按鈕，則呼叫側加入對話。
假設能參加一個群組的終端(人數)的上限是100人以上，在終端的處理
速度和終端間通信速度為一定的情況下，設N為終端數時，能以O(logN) 的延遲時間進行對話。即使參加終端數從IO增加到100,延遲也只是原來 的2倍。
在三人以上的通話狀態下，若根節點的終端以外的一人點擊「切斷」 按鈕，則只有該使用者脫離通話群組，結束通話。而在一對一的通話狀態 下，若任何一方點擊「切斷」按鈕，則兩者都結束通話。
(轉發)
若設呼叫側為A，轉發側為B，被轉發側為C，則A呼叫B， B點擊 「通話」按鈕，A與B進行通話。B受A的委託，指定C的用戶ID並點 擊「呼叫」按鈕，呼叫C。此時，B處在不將聲音 圖像傳送到A的狀態。
C點擊「通話」按鈕，與B通話，若確認可與A通話，則使B成為將 聲音 圖像傳送到A的狀態。B點擊「切斷」按鈕，從A — B — C的對話群 組中脫離，通過這樣成為只是A — C間的對話，轉發成功。
(本通信系統的要素)
本通信系統中，終端(通話終端軟體)具有圖4所示的以下的數據結構。 ，使用者的用戶ID:與電話號碼對應，假設使用郵件地址。
通話目標高速緩衝存儲器對通話目標的節點的指針(用戶ID、 IP 地址、埠號的組)的集合，初始值為空。
*待機群組節點用IP位址、埠號來識別。 ，通話群組節點用IP位址、埠號來識別。 ，代理對象的集合初始值為空。，左側(第l)下位節點的代理對象的集合的備份初始值為空。
右側(第2)下位節點的代理對象的集合的備份初始值為空。
與代理對象連接的套接字初始值為空，在該終端位於本地網時使用。
與代理對象的備份連接的套接字初始值為空，在該終端位於本地 網時使用。
，控制程序 (代理對象)
代理對象是位於本地網的終端(本地終端)參加本通信系統時、全局網的 某一個節點作為本地網的終端的代理而在該終端的計算機上啟動的對象 (程序)。利用代理對象，本地網的終端能越過NAT/防火牆進行通話。
代理對象具有圖5所示的以下的數據結構。
對應的本地網的終端的使用者的用戶ID:假設使用郵件地址。
連接對應的本地網的終端的套接字 '通話群組節點用IP位址、埠號來識別。 ，控制程序
(待機群組)
待機群組如圖6所示，用完全二叉樹結構以TCP連接來結合待機狀態 的群組節點。完全二叉樹結構是指任何一個葉到達根的距離都近似於一定 的結構。
若節點變成待機狀態，則該節點變成構成待機群組的樹的節點。對於 將節點間結合成完全二叉樹結構的構造將在後面加以闡述。其不像上述電 子黑板系統那樣使用群組管理員，能夠放鬆對該群組中包含的節點數量的 限制。並具有當枝節點發生故障時、將其與其它節點替換來進行修補的功 能。對於該功能也將在後面加以闡述。
此外，圖6中，帶箭頭的點劃線表示節點保存有箭頭前方(高兩位)的節 點的信息。其它線表示TCP連接。
這裡，待機群組節點具有圖7所示的以下的數據結構。
對包含自身的節點的指針包含用戶ID。 對上位節點的TCP連接套接字根節點的情況為空。
連接左側下位節點的套接字初始值為空，葉節點的情況為空。
連接右側下位節點的套接字初始值為空，葉節點的情況為空。
高兩位的節點的IP位址、埠號根節點和與根節點直接連接的節 點的情況為空。
，左側下位節點的權重是從左節點延伸下去的所有節點的數量，初 始值為0。
，右側下位節點的權重是從右節點延伸下去的所有節點的數量，初 始值為0。
左側下位節點具有的代理對象的數量初始值為0。
右側下位節點具有的代理對象的數量初始值為0。
控制程序 (通話群組)
通話群組是將待機群組的節點中、正在通話的節點的通話群組節點結 合成完全二叉樹結構而成的，用和圖6同樣的方式進行結合。 一個通話群 組內的節點發送的數據到達該群組內的所有節點。在待機群組內能構成多 個通話群組。通話群組的構成方法及管理方法與上述待機群組同樣地進行。
通話群組節點具有圖8所示的以下的數據結構。
對包含自身的節點的指針包含用戶ID。
,對上位節點的TCP連接套接字初始值為空，根節點的情況為空。
連接左側下位節點的套接字初始值為空，葉節點的情況為空。
連接右側下位節點的套接字初始值為空，葉節點的情況為空。
高兩位的節點的IP位址初始值為空。
，左側下位節點的權重是從左節點延伸下去的所有節點的數量，初 始值為0。
，右側下位節點的權重是從右節點延伸下去的所有節點的數量，初 始值為0。
控制程序
本通信系統構成待機群組和兩個通話群組的情況的例子在圖9中表示。這裡，終端A G是全局網的終端，終端H、 I是本地網的終端。全局網的 終端A G的待機群組節點構成待機群組。本地網的終端H的代理對象位 於終端D，其備份位於終端B。本地網的終端I的代理對象位於終端F，其 備份位於終端C。終端B的通話節點和本地網的終端H、 I的通話節點經由 代理對象構成通話群組l，在終端B、 H、 I間能進行通話。終端C、 F、 G 的通話節點構成通話群組2，在終端C、 F、 G間能進行通話。 (待機群組的構成方法)
管理本通信系統的組織以全局地址啟動三個終端，將該待機群組結合 成二叉樹結構來作為(初始)待機群組。通過將根節點的IP位址在網際網路上 公開或間接地公開，來進行使用者管理。
參加待機群組的所有待機群組節點如圖10 圖12所示，每隔一定時間 執行下述處理。
，將與自身連接的兩個下位節點的「權重」相加，對相加後的值加"l"， 作為自身的權重，將該權重向自身連接的上位節點告知(步驟S1)。若自身 為根節點時(步驟Sll中為是)，則不向上位節點告知權重。當不具有下位節 點時(步驟S12、 S14中為是)，設下位節點的權重為O(步驟S13、 S15)。
，檢索比自身高兩位的節點的IP位址和埠號，並進行存儲(步驟S2)。 在高一位的節點發生故障時，與高兩位的節點進行信息交換來修正群組的 狀態。該修正將在後面加以闡述。在根節點和與其直接連接的節點的情況 下，存儲「空」。
向上位節點告知自身的節點的代理對象的數量(步驟S3)。
向上位節點告知自身的節點的代理對象的集合，並進行備份(步驟 S4)。此時，對應的本地節點還具有對於備份的TCP連接。
'從自身的上位節點沒有反應時(S5、 S21)，設為上位節點發生了故障， 交換上位節點(步驟S22)。該節點交換處理將在後面加以闡述。
對待機群組添加新的全局地址的新節點時，進行圖13所示的以下的處 理。此時，新節點的左右的下位節點套接字成為空。
向待機群組的根的待機群組節點詢問添加新節點。
已向任意的待機群組節點詢問添加新節點時，若左側下位節點套接字為空(S31中為是)，則將新節點與左側下位節點套接字連接作為該節點的
下位節點(步驟32)，並對左側下位節點的權重加"1"(步驟S33)。除此以 外，若右側下位節點套接字為空(S34中為是)，則將新節點與右側下位節點 套接字連接作為該節點的下位節點(步驟35)，並對右側下位節點的權重加
"1"(步驟S36)。除此以外，若左側下位節點的權重為右側下位節點的權 重以下(步驟37中為是)，則向左側下位節點詢問添加新節點(步驟S38),並 對左側下位節點的權重加"1"(步驟39)。除此以外(步驟S37中為否)，則 向右側下位節點詢問添加新節點(步驟S40)，並對右側下位節點的權重加
"1"(步驟S41)。
利用以上算法，在添加新節點時，用完全二叉樹結構進行結合。而且， 能夠用O(logN)的時間對待機群組添加新節點。
對待機群組新添加本地網的新終端時，進行以下處理。即，向待機群 組的根節點詢問添加新本地終端，若得到回覆，則對其IP位址和埠號進 行TCP連接。
己向任意的待機群組的節點詢問添加新本地終端時，進行圖"所示的 以下的處理，並將該結果返回到詢問的本地終端。
"若左右的下位節點套接字為空(步驟S51中為是)，則對自身的代理對 象的集合添加新本地終端的代理對象，將代理對象的IP位址和埠號作為 結果(步驟S52)。
除此以外，若左側下位節點的代理對象的數量為右側下位節點的代 理對象的數量以下、且為自身的代理對象的數量以下(步驟S53中為是)，則 向左側下位節點進行添加新本地終端的詢問，並將回復作為結果(步驟 S54)。
除此以外，若右側下位節點的代理對象的數量為自身的代理對象的 數量以下(步驟S55中為是)，則向右側下位節點進行添加新本地終端的詢 問，並將回復作為結果(步驟S56)。
*除此以外(步驟S55中為否)，則對自身的代理對象的集合添加新本地 終端的代理對象，將該代理對象的IP位址和埠號作為結果(步驟S57)。
利用以上算法，添加待機群組的節點的代理對象的數量，使得在任何
14節點都接近相同的數量。 (呼叫對方)
呼叫對方時進行圖15所示的以下的處理。g卩，進行通話對方的「節點
檢索」(步驟S61)，若結果為空(步驟S62中為是)，則顯示表示找不到對方 的意思，並結束。若不是如此，則進行以下處理。
'若自身是全局網的終端(步驟S63中為是)，則將對方的通話節點作為 通話群組的根節點，並對根節點嘗試連接自身的通話節點(步驟S64)。
，若自身是本地網的終端(步驟S63中為否)，則將對方的通話節點作為 通話群組的根節點，並對根節點嘗試連接自身的代理對象的通話節點(步驟 S65)。
(節點檢索)
節點檢索是指在呼叫通話對方時、最初檢索具有對方的用戶ID的節點 位於何處的處理。節點檢索如圖16所示那樣來執行。
，檢査自身的通話目標節點的集合(高速緩衝存儲器)中是否存儲有具有 對方用戶ID的節點信息。若存儲有(步驟S71中為是)，則嘗試與該節點連 接(步驟S72)，若成功(步驟S73中為是)，則將其作為呼叫節點(步驟S78)。 通過保存通信目標節點，從而減小待機群組中的節點檢索的負荷。
4餘此以外的情況下(步驟S71中為否)，對待機節點群組的根節點請求 節點並行檢索(步驟S74)。結果不為空時(步驟S75中為否)，對通話目標集 合添加結果(步驟S77)，將其作為呼叫節點(步驟S78)。結果為空時(步驟S75 中為是)，向用戶告知表示對方未與網絡連接的意思(步驟S76)。
已對任意的待機群組節點請求節點並行檢索時，進行圖17及圖18所 示的以下的處理(節點並行檢索)，並將結果返回到請求的節點。
若檢索地址是包含自身(待機群組的節點)的節點的用戶ID(步驟S81 中為是)，則將自身的通話群組節點的IP位址和埠號作為結果(步驟S82、 S92)。
，若檢索地址位於自身的代理對象集合的節點中(步驟S83中為是)，則 將該節點的IP位址和埠號作為結果(步驟S84、 S92)。
，除此以外，若左右的下位節點套接字都為空(步驟S85中為是)，則返
15回空(步驟S86、 S92)。
'除此以外的情況下(步驟S85中為否)，若左側下位節點套接字不為空(步驟S87中為是)，則對左側下位節點請求節點並行檢索(步驟S88)。若與此並行地右側下位節點套接字不為空(步驟S89中為是)，則對右側下位節點請求節點並行檢索(步驟S90)。
等待上述兩個結果返回。當從左右下位節點套接字的某一個返回不為空的結果時，立即將其作為結果。若兩個下位節點套接字都為空，則將空作為結果(步驟S91、 S92)。(通話處理)
通話節點從其它節點收到連接請求時，進行以下處理。 對用戶進行來電音產生/來電顯示。
，用戶點擊了 「通話」按鈕後，根據以下說明的通話群組構成方法，將該節點作為根節點，構成將連接請求源節點作為成員的通話群組。(通話群組構成方法)
參加通話群組的所有通話群組節點每隔一定時間進行下述處理。，將與自身連接的兩個下位節點的「權重」相加，將相加後的值加"l"，作為自身的權重，將該權重向自身連接的上位節點告知。若自身為根節點時，則不向上位節點告知權重。當不具有下位節點時，設下位節點的權重為0。
檢索比自身高兩位的節點的IP位址和埠號，並進行存儲。在高一位的節點發生故障時，與高兩位的節點進行信息交換來修正群組的狀態。該修正將在後面加以闡述。在根節點和與其直接連接的節點的情況下，存
儲「空」。
從自身的上位節點沒有反應時，設為上位節點發生了故障，交換上
位節點。該節點交換處理也將在後面加以闡述。
對通話群組添加新節點時，進行以下處理。此時，新節點的左右的下
位節點套接字為空。
向通信群組的根的通話群組節點詢問添加新節點。
已向任意的通話群組節點詢問添加新節點時，若左側下位節點套接字為空，則將新節點與左側下位節點套接字連接作為該節點的下位節點。，除此以外，若右側下位節點套接字為空，則將新節點與右側下位節
點套接字連接作為該節點的下位節點。
，除此以外，若左側下位節點的權重為右側下位節點的權重以下，則
向左側下位節點詢問添加新節點，並對左側下位節點的權重加"1"。
，除此以外，則向右側下位節點詢問添加新節點，並對右側下位節點
的權重加"1"。
利用以上算法，添加新節點時，用完全二叉樹結構進行結合。而且，能夠在O(logN)的時間內對通話群組添加新節點。(代理對象的通信處理)
代理對象與本地終端一一對應。到達代理對象的信息照原樣傳達到本地終端，本地終端發送的信息照原樣傳達到代理對象。通過這樣，本地終端與全局網的終端同樣地進行通信。
代理對象定期地在和與其對應的本地終端之間進行確認連通與否等的信息交換。備份的代理對象也同樣地和本地終端進行信息交換。當代理對象無反應時，與其對應的本地終端將備份的代理對象作為新的代理對象。
如果連備份節點也包含在內的所有的代理對象都沒有反應，則對待機群組進行添加該本地終端以作為新本地終端的處理。若與代理對象對應的本地終端無反應，則刪除該代理對象。
(節點的故障對策)
以下說明的節點的故障對策實質上是節點交換處理，對於待機群組及通話群組是同樣的。
定期進行節點間信息交換時，在沒有來自上位節點的反應的情況下，
設為上位節點發生了故障，進行圖19及圖20所示的以下的節點交換處理。
此外，在該交換處理期間、有向高其兩位的上位節點進行各種詢問時，先保留該詢問，等交換處理結束後再來處理這些詢問。
通過以下的步序，高兩位的上位節點獲取上位節點(從高兩位的上位節
點來看為發生故障的節點)的IP位址及埠號和新節點候補(步驟sioi)。 進行下述說明的葉節點取出處理(步驟Slll)，並將結果與自身的IP位址及埠號、上位節點的IP位址及埠號一起，作為新節點候補向高兩位的上位節點告知(步驟S112)。
高兩位的上位節點將前面接收到的新節點候補作為新節點。並且，獲取^結果一起送來的左右下位節點的信息，並進行下述說明的連接變更處
理(步驟S102)。
利用節點交換處理，進行了處理的部分的樹的權重會減少一，有時會
破壞樹的平衡。但是，在權重的變化反映到所有節點的O(logN)時間後添加
新的節點時，由於是添加到權重輕的部分的樹，因此始終自主地進行調整，使得節點成為完全二叉樹結構。(葉節點取出處理)
葉節點取出處理對待機群組及通話群組是同樣的，在故障發生時為了替換節點而進行的。即，節點重複探尋自身較重一側的枝，到達葉時取出該葉，通過這樣能夠來實現。
利用以上的算法，能夠在O(logN)的時間內取出葉節點。(連接變更處理)
如圖21及圖22所示，設被補上的節點為A，節點A的新上位節點為B，節點A的新的左側下位節點為C，節點A的新的右側下位節點為D(步驟S131)。此時，節點B獲取節點A、 C、 D的IP位址及埠號(步驟S132)。節點C、 D在節點脫落時從自身分別向節點B通知。節點A是節點C、 D分別利用葉節點取出處理尋找候補時、其中某一個先向節點B通知的節點。
節點B的左側下位節點為故障發生節點時，將節點A與節點B的左側下位節點套接字連接。節點B的右側下位節點為故障發生節點時，將節點A與節點B的右側下位節點套接字連接(步驟S133)。然後，節點B將節點C、 D交給節點A(步驟S134)。
接著，節點A將節點C與左側下位節點套接字連接，將節點D與右側下位節點套接字連接(步驟S135)。節點C、 D有時也會為空。節點A、 C相同時，將節點A的左側下位節點設為空。同樣地，節點A、 D相同時，將右側下位節點設為空(步驟S136)。
(節點交換處理)定期進行節點間信息交換時，在沒有來自左右某一個下位節點的反應的情況下，設為下位節點發生故障，進行以下的節點交換處理。
，左右的下位節點中，若沒有反應的下位節點的權重為2以上，則等待來自低兩位的節點的節點交換處理請求，該請求來到時進行對應的處理。，在並非如此的情況下，由於沒有反應的節點是葉節點，因此將沒有反應一側的代理對象的集合的備份添加到代理對象集合。
在上下任一個節點都沒有反應的情況下，將自身作為新節點添加到待機群組。(其它)
通過將本通信系統安裝到家庭用寬帶路由器，能夠構成更穩定的通信
系統。家庭用寬帶路由器具有全局地址，通常24小時不間斷地接通電源。
利用待機群組內的節點間通信，能自動地更新軟體。系統管理組織通過管理待機群組的根節點具有的終端、和該終端發生故障時使用的備用的終端，也能進行用戶管理。另外，通過將待機群組由地址的種類等來進行分割，能夠進一步減小節點檢索的負荷。
構成通話群組時，通過在被呼叫的根節點處進行認證等，能夠進行限制接收者的通信(廣播)。
權利要求
1.一種聲音·圖像通信系統，其特徵在於，參加一個通話群組的節點具有第1及第2下位節點連接部並且進行節點的添加，來保存與第1及第2下位節點連接的節點的總數，並使得與第1及第2下位節點連接部連接的節點數量變得相同，從而自主地進行連接的調整，使得節點間的結合變成完全二叉樹結構，所述通話群組內的一個節點發送的數據在與節點數量的對數成正比的時間內到達通話群組內所有的節點。
2. 如權利要求1所述的聲音 圖像通信系統，其特徵在於， 所述各節點收到來自上位節點的添加新節點的指示時，若所述第l或第2下位節點連接部的某一個未連接有節點，則將新節 點與未連接的下位節點連接部連接，若任一個下位節點連接部都未連接有節點，則將新節點與第1下位節 點連接部連接，若任一個下位節點連接部都連接有節點，則將新節點與連接的節點數 量少的下位節點連接部連接。
3. 如權利要求1或2所述的聲音 圖像通信系統，其特徵在於， 在所有的節點間，定期對上位節點告知包含該節點的下位節點的總數，上位節點將該總數作為與自身的第1及第2下位節點連接部連接的下位節 點的總數來保存。
4. 如權利要求1至3的任一項所述的聲音 圖像通信系統，其特徵在於，系統的終端除參加所述通話群組以外，還參加待機時參加的待機群組， 該待機群組中各節點也進行節點的添加或刪除，來保存與第1及第2下位節點連接的節點的總數，並使得與第1及第2下位節點連接部連接的節點數量變得相同。各節點還保存有終端的使用者信息，在尋找通話目標時，從待機群組的上位節點往所述完全二叉樹結構的下位節點方向並行檢索通話目標使用者信息。
5. 如權利要求1至4的任一項所述的聲音 圖像通信系統，其特徵在於，所述各節點保存有高兩位的上位節點的信息，在通話群組及待機群組 的節點間定期地進行確認節點故障的通信，某一個節點發生故障時，下位節點對其進行識別，作為取代故障發生 節點，識別出故障的節點取出下位節點並向高兩位的上位節點告知以作為 替代節點候補，高兩位的上位節點將被取出的下位節點與故障發生節點進行替換。
6. 如權利要求5所述的聲音 圖像通信系統，其特徵在於， 所述高兩位的t位節點接收到來自與故障發生節點連接的下位節點的兩個替代節點候補時，將先接收到的候補與故障發生節點交換。
7. 如權利要求1至6的任一項所述的聲音 圖像通信系統，其特徵在於，與全局網連接的終端為了中轉位於本地網的終端的通信，具有位於本 地網的終端的代理對象。
8. 如權利要求7所述的聲音*圖像通信系統，其特徵在於， 位於本地網的終端在參加待機群組時，與全局網的代理對象連接，該連接時構成待機群組的全局網的終端所保存的代理對象的數量在各終端中 大致相同。
9. 如權利要求7或8所述的聲音 圖像通信系統，其特徵在於， 待機群組的各節點利用定期的信息交換來保存作為第1及第2下位節點而保存的代理對象的數量，上位節點對保存的代理對象數量最少的下位節點進行添加代理對象的 指示，下位節點不存在時對上位節點自身進行添加。
10. —種聲音，圖像通信系統，所述系統用完全二叉樹結構結合了多個 節點，該系統的特徵在於，所述各節點至少具有對上位節點的TCP連接部、對第l及第2下位節 點的連接部、和控制程序，至少具有第l下位節點的權重信息及第2下位節點的權重信息，用完全二叉樹結構構成群組時，根節點在其第l下位節點連接部為空 時將新節點與第1下位節點連接部連接並對第1下位節點的權重信息加"1"，而在第1下位節點連接部不為空且第2下位連接部為空時將新節點 與第2下位節點連接部連接並對第2下位節點的權重信息加"1"，除此以 外若第1下位節點的權重信息為第2下位節點的權重信息以下，則向第1 下位節點詢問添加新節點並對第l下位節點的權重信息加"1"，而若第1下位節點的權重信息超過第2下位權重信息，則向第2下位節點詢問添加 新節點並對第2下位節點的權重信息加"1"。
全文摘要
本發明得到一種能夠在大量節點間同時發送接收的、能夠靈活地處理新節點的參加或脫離的聲音·圖像通信系統。它是一種將多個節點用完全二叉樹結構結合而成的聲音·圖像通信系統。用完全二叉樹結構構成群組時，根節點在左側下位節點連接部為空時將新節點與左側下位節點連接部連接並對左側下位節點的權重信息加1，而在左側下位節點連接部不為空且右側下位連接部為空時將新節點與右側下位節點連接部連接並對右側下位節點的權重信息加1，除此以外若左側下位節點的權重信息為右側下位節點的權重信息以下，則向左側下位節點詢問添加新節點並對左側下位節點的權重信息加1，而若左側下位節點的權重信息超過右側下位權重信息，則向右側下位節點詢問添加新節點並對右側下位節點的權重信息加1。
文檔編號H04L12/56GK101496358SQ20078002793
公開日2009年7月29日 申請日期2007年8月1日 優先權日2006年8月4日
發明者山之上卓 申請人:國立大學法人鹿兒島大學;株式會社奈良情報系統