賽題描述

Ad Hoc網(wǎng)絡(luò)是當(dāng)前網(wǎng)絡(luò)和通信技術(shù)研究的熱點(diǎn)之一，對(duì)于諸如軍隊(duì)和在野外作業(yè)的大型公司和集團(tuán)來說，Ad Hoc網(wǎng)絡(luò)有著無需基站、無需特定交換和路由節(jié)點(diǎn)、隨機(jī)組建、靈活接入、移動(dòng)方便等特點(diǎn)，因而具有極大的吸引力。

在Ad Hoc網(wǎng)絡(luò)中，節(jié)點(diǎn)之間的通信均通過無線傳輸來完成，由于發(fā)射功率以及信道（即頻率）的限制，節(jié)點(diǎn)的覆蓋范圍有限，當(dāng)它要與其覆蓋范圍之外的節(jié)點(diǎn)進(jìn)行通信時(shí)，可以通過中間節(jié)點(diǎn)轉(zhuǎn)發(fā)，如右圖所示。

對(duì)一個(gè)指定區(qū)域，用一系列稱為一跳覆蓋區(qū)的小區(qū)域?qū)⑵溆兄丿B地完全覆蓋，對(duì)每個(gè)一跳覆蓋區(qū)分配一個(gè)信道，處于幾個(gè)一跳覆蓋區(qū)重疊部分的節(jié)點(diǎn)同時(shí)使用幾個(gè)信道工作。在同一個(gè)一跳覆蓋區(qū)內(nèi)的用戶使用同一個(gè)信道相互通信；不同一跳覆蓋區(qū)的用戶之間通過中間節(jié)點(diǎn)轉(zhuǎn)發(fā)。如圖中，節(jié)點(diǎn)A,B間的通信可由路由A-C-D-B或A-C-E-F-B實(shí)現(xiàn)。如果區(qū)域中任意兩個(gè)節(jié)點(diǎn)都能通信，則稱之為連通。

現(xiàn)在，需要在一個(gè)1000*1000(面積單位)的區(qū)域內(nèi)構(gòu)建一個(gè)Ad Hoc網(wǎng)絡(luò)，請(qǐng)你完成以下工作：

（1）   將此正方形區(qū)域用若干個(gè)半徑都是100的圓完全覆蓋，要求相鄰兩個(gè)圓的公共面積不小于一個(gè)圓面積的5%，最少需要多少個(gè)圓（如果一個(gè)圓只有部分在正方形區(qū)域中，也按一個(gè)計(jì)算）？若給每個(gè)圓分配一個(gè)信道，使得有公共部分的圓擁有不同的信道，最少需要幾個(gè)信道？怎樣分配（用示意圖標(biāo)出）？如果將上面的5%改為18%?