Luận án Nghiên cứu một số giải pháp định tuyến trong tô-pô mạng liên kết hiệu năng cao và công cụ đánh giá

hỉ tiền tố (prefix). Định danh nút mạng được cấu trúc bởi hai thành phần: block_id – định danh khối (như là địa chỉ tiền tố) và node_id – định danh nút trong khối. Khi thực hiện tra cứu địa chỉ nút đích t trong bảng định tuyến của nút s, nút s thực thi tra cứu longest-prefix-matching lookup [50] để tìm địa chỉ tiền tố của nút q tương ứng với địa chỉ tiền tố của nút t. 
Hình 2. 9: Thực thi định tuyến thông qua định danh nút mạng
NCS sử dụng một ví dụ, với cách định danh ngắn, đơn giản cho nút mạng để minh họa cho quá trình tra cứu thông tin định tuyến. Với nút t có địa chỉ là 10001001 và nút q có địa chỉ là 10011010, có thể xem t và q là hàng xóm của nhau với định danh khối là “100010”. Địa chỉ của nút q được lưu trữ trong bảng định tuyến của nút s. Khi thực hiện tra cứu thông tin nút t trong bảng định tuyến của s, phần block_id của nút t và block_id của nút q được so sánh với nhau. Áp dụng kỹ thuật longest-prefix-matching lookup [50], nút s sẽ kiểm tra định danh khối của các cặp (t;q). Nếu block_id của t trùng với block_id của nút q, thì nút s xác định được t và q là hàng xóm của nhau. Khi tìm được nút q thì xác định được nút tiếp theo sẽ thực hiện chuyển tiếp gói tin.
2.2.4. Đánh giá lý thuyết
Trước tiên, chúng ta hãy phân tích RTS. Với tham số δ, nút nguồn s phải “biết” mọi nút trong vùng hàng xóm của nó Nδ(s). Kích thước vùng hàng xóm của nút s bất kỳ là 2*δ*(δ+1). (Ví dụ, δ=4, kích thước vùng hàng xóm sẽ là 40). RTS được biểu diễu bởi tham số z, nên vùng nTable trong bảng định tuyến, s cần z=2*δ*(δ+1) bản ghi cho thông tin định tuyến tới các nút hàng xóm của nó. 
Tại vùng brTable, mỗi nút s phải lưu thông tin về các cầu bridge1 và bridge2 mà kết nối tới Nδ(s). Với số liên kết ngẫu nhiên là r tại mỗi nút u bất kỳ trên mạng, sẽ có r nút kết nối tới u bằng một liên kết ngẫu nhiên và có r*(r-1) nút khác được kết nối tới u bằng 2 liên kết ngẫu nhiên liên tiếp. Do đó, nút s cần r2*z bản ghi (trong phần brTable) để lưu thông tin các cầu bridge1 và bridge2 (chúng kết nối tới vùng Nδ(s). Kết hợp cả 2 thông tin lưu trữ tại nTable và brTable, mỗi nút cần số bản ghi z*r2+1 trong bảng định tuyến của nó.
Chúng ta xem xét kỹ lưỡng hơn về khả năng thiếu cầu nối giữa 2 vùng hàng xóm bất kỳ. Do tính chất sinh liên kết bằng phân phối xác suất đều nào đó, nên khó đảm bảo luôn tồn tại ít nhất một kết nối giữa 2 vùng hàng xóm, đặc biệt là khi kích thước mạng tăng lên, và vùng bán kính δ nhỏ. Để thuận tiện, gọi Nδ(s) được biểu diễn là S và Nδ(t) biểu diển bởi T. Dễ dàng thấy ràng, xác suất để tạo ra được một liên kết ngẫu nhiên từ nút u∈S kết nối tới nút v∈T, là zN2 với N là số nút mạng. Và xác suất để không tạo ra được liên kết như vậy là 1-zN. Từ tất cả các nút u∈S, sẽ có z*r2 cầu, do đó, xác suất không có liên kết nào từ S tới T sẽ là 1-zNz*r2. Do đó, xác suất không có liên kết cầu (bridge1 hoặc bridge2) đi từ S tới T là e-c*r2, trong đó, c=z2N=4*δ4+8*δ3+4*δ2N.
Từ đó, phát biểu mệnh đề dưới đây:
Mệnh đề 1 (Trường hợp thiếu cầu – missing link): Cho tô-pô ngẫu nhiên cơ bản (được tạo ra bởi phương thức xây dựng mạng do NCS đề xuất), kích thước mạng , với mỗi nút mạng có r-liên kết ngẫu nhiên, giữa 2 vùng hàng xóm bất kỳ bán kính δ, xác suất để không tồn tại cầu bridge1 hoặc bridge2 giữa chúng là e-c*r2, 
Trong đó, c=z2N=4*δ4+8*δ3+4*δ2N (CT 2.1).
Ví dụ, nếu thiết lập r=2, δ=6,N=8000 hoặc r=2, δ=10, N=50.000, xác suất để xảy ra trường hợp “missing link” khoảng 2%. 
Để định tuyến gói tin từ nút nguồn s tới nút đích t, sử dụng cầu tương ứng (u;v) với u∈Nδ(s) và v∈Nδ(t). Đầu tiên, định tuyến gói tin từ s tới nút u (chân cầu bên vùng Nδ(s)) bằng cách sử dụng các liên kết nội vùng (local-routing: dựa trên các liên kết cơ bản dạng lưới). Sau đó, gói tin được truyền trên liên kết (u;v). Tại nút v, (chân cầu bên vùng Nδ(t), gói tin được định tuyến nội vùng trong Nδ(t) bằng cách sử dụng các liên kết lưới cơ bản (local-routing) để tìm đường đi ngắn nhất tới nút đích t. Với cách định tuyến như vậy, chiều dài định tuyến sẽ là (2*α+2) – tính theo hop, với α là đường kính của đồ thị con S (vùng Nδ(s)) hoặc T: Nδ(t)), và α<δ. 
Do vậy, nếu mở rộng mô hình mạng trên đồ thị cơ bản, mỗi nút có các liên kết nội vùng tới tất cả các nút trong k khoảng liên kết lưới thay thế cho 1 khoảng liên kết lưới như mô hình cơ bản như Hình 2.10. Với cách thay thế này, chúng ta có thể giảm đáng kể α và đường kính định tuyến của CORRA.
Ví dụ, nếu chọn δ=2*k khi sử dụng đồ thị k liên kết lưới, mở rộng như là đồ thị cơ bản, hiển nhiên α=2 (gói tin chỉ cần chuyển trong 2 hop) và chiều dài định tuyến của CORRA sẽ là 6, thậm chí thấp hơn (giá trị này có thể đạt thấp nhất là 3). Ví dụ, nếu r=2, δ=10, N=50.000, k=5, xác suất xảy ra thiếu cầu chỉ khoảng 2% hoặc thấp hơn. Điều này nhấn mạnh rằng, các cầu bridge1 hoặc bridge2 luôn luôn được sử dụng và do đó, đường kính định tuyến có giá trị nhỏ hơn 6 (khi kích thước mạng quá lớn, chúng ta cần thực nghiệm thêm để xác định các giá trị tham số δ và k phù hợp).
Hình 2.10: Mô hình mở rộng, sử dụng k-grid liên kết cơ bản
2.2.5. Đánh giá thực nghiệm
Trong phần này, phân tích các tính chất của CORRA và so sánh với các thuật toán định tuyến khác mà được áp dụng trên tô-pô mạng ngẫu nhiên như là TZ [29], SPR [5]. So sánh này dựa trên các tiêu chí hiệu năng như MRPL, ARPL và trung bình độ trễ. NCS đánh giá sự tương quan giữa giá trị δ và RTS như đã được đề cập về việc làm thế nào để tạo ra các bản ghi của bảng định tuyến, bằng việc chỉ ra số lượng δ hop, so với số lượng các bản ghi tại mỗi nút. Thực nghiệm được tiến hành với giá trị δ trong khoảng 2 đến 8 đối với mỗi kích thước mạng từ 1.024 đến 8.192. Hình 2.11 cho thấy, với mỗi kích thước mạng, sẽ có giá trị δ làm RTS đạt giá trị nhỏ nhất. Ví dụ, RTS đạt giá trị tối ưu 175 bản ghi tại δ=3 và RTS đạt 360 tại δ=5 đối với mạng 1.024 và 4.096 tương ứng.
Hình 2.11: Tác động của giá trị δ đối với RTS
2.2.5.1. Phân tích trường hợp thiếu cầu nối
Trong việc quyết định giá trị δ, cũng cần chú ý đến số lượng liên kết thiếu giữa các nút, bởi việc lựa chọn giá trị của RTS tối ưu dẫn đến số lượng liên kết thiếu không mong muốn. Tuy nhiên, tồn tại giá trị phù hợp làm cho RTS gần đạt tối ưu mà vẫn đảm bảo số lượng liên kết thiếu được giảm đáng kể. Ví dụ, nếu δ tăng từ 3 lên 4 trong mạng 1.024 nút, tổng bản ghi trong mạng chỉ tăng 6,1% (ví dụ, từ 179.629 lên 190.097) nhưng số lượng liên kết thiếu giảm đáng kể 88,6% (ví dụ, từ 22.356 xuống còn 2.546). Do vậy, việc lựa chọn giá trị δ phù hợp là một đặc tính quan trọng trong việc xây dựng CORRA.
2.2.5.2. Đánh giá kích thước bảng định tuyến theo giải pháp sử dụng cầu nối
Trong thực nghiệm này, Hình 2.12 cho thấy SPR đạt số lượng bản ghi bảng định tuyến lớn nhất trong bất kỳ kích thước mạng nào bởi vì, mỗi nút phải lưu thông tin của mọi nút trong mạng. Trong khi đó, CORRA và TZ [29] có trung bình số lượng bản ghi nhỏ hơn khi so sánh với SPR là 87,33% và 94,68%, tương ứng. 
Hình 2.12: Trung bình kích thước bảng định tuyến
Kết quả cho thấy, CORRA đã đảm bảo tiêu chí giảm RTS khá lớn so với SPR, tuy nhiên, vẫn lớn hơn (không nhiều) so với TZ, bởi trong CORRA, ngoài việc lưu trữ các thông tin hàng xóm, thì các thông tin bridge1 và bridge2 được lưu trữ nhiều hơn.
2.2.5.3. Đánh giá đường kính mạng
Đường kính mạng là đường đi dài nhất (MRPL) trong các đường đi ngắn nhất giữa 2 nút bất kỳ trong mạng [5]. Hiển nhiên, MRPL bé hơn và RTS bé hơn được xem là tốt hơn. Thực nghiệm cho thấy TZ [29] có MRPL tồi nhất trong tất cả kích thước mạng, tuy nhiên, RTS lại bé nhất khi so sánh với CORRA và SPR. Nguyên nhân là trong thuật toán TZ, kích thước các cụm được tạo ra khá lớn, nên việc định tuyến từ một nút (khoảng giữa) đến biên của cụm sẽ đi qua nhiều hop trong vùng cụm đó trước khi đến được nút đại diện gần nhất. Trong khi đó, CORRA đạt MRPL bé nhất (tính theo hop) khi so sánh với TZ nhưng RTS tại mỗi nút lại cao hơn TZ. 
Hình 2.13: Đánh giá đường kính mạng
Ví dụ, trong mạng có kích thước 1.024 nút, MRPL của CORRA thấp hơn của TZ khoảng 25,45%, tính trung bình; tuy nhiên, RTS trung bình của CORRA cao hơn của TZ khoảng 61,14%, như minh họa Hình 2.13. So sánh với SPR, chúng ta thấy rằng CORRA có MRPL dài hơn nhưng RTS tại mỗi nút bé hơn nhiều, CORRA chỉ sử dụng 12,12% số lượng bản ghi khi so sánh với SPR và đường kính dài hơn của SPR khoảng 30% trong mạng kích thước 4.096.
2.2.5.4. Đánh giá trung bình chiều dài đường định tuyến
Như đã trình bày trong Chương 1, ARPL của mạng sử dụng thuật toán định tuyến được định nghĩa là trung bình số hop tính dọc theo đường định tuyến đối với các cặp nút. ARPL có giá trị hơn đường kính mạng và như là một thuộc tính để đánh giá hiệu suất của tô-pô, nó chỉ ra giới hạn trên của các đường định tuyến. 
Hình 2.14 minh họa các kết quả ARPL khi so sánh CORRA với TZ và SPR. CORRA có giá trị ARPL thấp hơn của TZ khoảng 21,13% trong mạng 1.024 nút, và không vượt xa so với giá trị tối ưu của SPR. CORRA đạt kết quả tốt hơn bởi khai thác được số lượng liên kết cầu nhiều hơn so với TZ.
Hình 2.14: Trung bình chiều dài đường định tuyến (ARPL)
2.2.5.5. Đánh giá trung bình độ trễ truyền tin
Độ trễ là thời gian cần thiết để gói tin di chuyển trên mạng, tính thời gian từ đầu gói tin (bắt đầu di chuyển) tại cổng vào và thời gian để phần cuối (đuôi) gói tin đi ra khỏi cổng ra. Độ trễ thấp hơn được xem là tốt hơn. Để đánh giá độ trễ, chúng ta sử dụng độ trễ trên thiết bị mạng (switch-delay) là 100 nano giây như là thiết bị switch – InfiniBand QDR [35] và độ trễ đường dây là 5 nano giây trên mỗi mét chiều dài cáp quang. 
Hình 2.15: Trung bình độ trễ truyền tin
Độ trễ cho một gói tin di chuyển trên mạng được tính bằng tổng độ trễ tại các switch và tổng độ trễ di chuyển trên đường đi. Do đó, độ trễ trung bình sẽ tương đồng với các giá trị MRPL và ARPL. Hình 2.15 biểu diễn kết quả thực nghiệm độ trễ mạng khi so sánh CORRA và TZ [29], SPR. Hầu hết trường hợp, độ trễ trung bình của CORRA tương tự với của SPR, ví dụ: CORRA lớn hơn 3% và 7% với mạng có kích thước 2.048 và 1.024 tương ứng. Trong khi đó, độ trễ của TZ [29] cao hơn của CORRA khoảng 10% đến 48% với kích thước 8.192 và 1.024 nút tương ứng.
2.2.5.6. Đánh giá thực nghiệm với mạng kích thước lớn
Kích thước mạng được sử dụng trong các thực nghiệm ở trên khá nhỏ, ví dụ 4.096, khi so sánh với kích thước của các DC hiện đại, mà kích thước của nó lên tới hàng trăm nghìn nút. Do đó, rất thuận tiện để thực hiện thực nghiệm các kích thước mạng lớn như vậy để đánh giá hiệu năng của CORRA. Nhưng ngay cả với CORRA cũng rất khó khả thi để tiến hành thực nghiệm trên các mạng cỡ lớn do sự thiếu hụt tài nguyên tính toán. 
NCS đề cập đến việc làm thế nào để tiến hành thực nghiệm trên các tô-pô mạng lớn. NCS so sánh CORRA với SPR trên mạng có kích thước 214;215;216. Thay cho việc tính toán bảng định tuyến cho mọi nút, bảng định tuyến sẽ được tạo ra tại nút hiện thời nếu cần thiết. Với mỗi nút trên đường đi từ nút nguồn tới nút đích, bảng định tuyến sẽ được cập nhật bằng thuật toán CORRA. Ý tưởng khá đơn giản, với mỗi nút nguồn s và nút đích t, áp dụng thuật toán CORRA cho cặp (s;t), khi thực hiện định tuyến tại nút w, sau đó xây dựng bảng định tuyến cho nút này.
Hình 2.16: ARPL của mạng có kích thước lớn
Hình 2.16, thể hiện giá trị ARPL của CORRA đạt được tương đương (cao hơn không đáng kể) với SPR. Điều này cho thấy khả năng tính toán của CORRA với mạng có kích thước lớn lên tới hàng chục nghìn nút mạng.
Hình 2.17: Trung bình độ trễ truyền tin đối với mạng kích thước lớn
Ngay cả khi kích thước mạng tăng từ 214 tới 216, CORRA vẫn duy trì tốt độ trễ trung bình tương đương và có phần tốt hơn như được biểu diễn tại Hình 2.16 và Hình 2.17 khi so sánh với SPR.
2.2.6. Kết luận và hướng phát triển
NCS đề xuất kịch bản định tuyến rút gọn mà duy trì được RTS nhỏ để lưu trữ tại mỗi thiết bị switch và đồng thời duy trì được ARPL thấp (xấp xỉ và chỉ dài hơn không đáng kể so với SPR). NCS cũng trình bày chi tiết thuật toán để xây dựng các bảng định tuyến và kiểm tra mối quan hệ giữa các tham số để đạt được mức độ yêu cầu hiệu năng của các thuật toán được đề xuất. NCS khám phá các sử dụng các cầu nối giữa các vùng hàng xóm riêng biệt và được áp dụng trong thuật toán được đề xuất là CORRA, có ARPL tăng 20% so với SPR, nhưng giảm 17,6% khi so với TZ [29]. Tuy nhiên, khi so với SPR, thuật toán định tuyến CORRA giảm RTS được 88% và 94% đối với mạng có kích thước 2.048 và 8.192 tương ứng. Điều này chứng tỏ rằng, CORRA có RTS cao hơn nhưng đạt được giá trị ARPL tốt hơn nhiều so với thuật toán TZ.
Hơn nữa, với hầu hết kích thước mạng được thực nghiệm, CORRA đạt được độ trễ truyền tin tốt hơn TZ và SPR với 31,36% và 5,36% tương ứng. Trong nghiên cứu này, NCS tập trung vào việc thiết kế kịch bản định tuyến cơ bản mới để đạt được mục tiêu đề ra. NCS vẫn còn nhiều công việc phải thực hiện trong tương lai, khi cần phát triển kịch bản đó để phù hợp với mạng kích thước siêu. NCS tin rằng, các nghiên cứu tiếp theo trong việc phát triển và điều chỉnh các tham số quan trọng (ví dụ, tham số δ), đề xuất có thể cần cải thiện hiệu năng và kịch bản định tuyến để có thể so sánh kỹ hơn với SPR và TZ. NCS cũng đã nghiên cứu một phần về khía cạnh lý thuyết và sẽ đề cập kỹ hơn trong các nghiên cứu sau này.
2.3. Định tuyến khai thác các nút đại diện và cơ chế tuyển chọn nút đại diện
Trong phần này, NCS trình bày kịch bản định tuyến rút gọn dựa trên tính chất địa hạt của nút đại diện, được gọi là Geographic Landmark-based Compact Routing (viết tắt: GLCR). Tương tự với kịch bản định tuyến rút gọn TZ [29] được xem là tốt nhất với stretch-3 và RTS đạt Οn12, đề xuất GLCR vốn dĩ cùng cách tiếp cận chuyển tiếp dựa trên nút đại diện như được thảo luận tại mục 2.2. Vấn đề được đặt ra ở đây là liệu rằng tồn tại kịch bản định tuyến rút gọn tốt hơn mà phù hợp với mạng ngẫu nhiên và có thể cải tiến kịch bản định tuyến của TZ [29] tốt hơn không? Để tìm ra giải pháp tốt hơn, NCS trình bày một cách tiếp cận mạnh mẽ và chỉ sai khác ít so với thuật toán SPR theo tiêu chí ARPL, nhưng đây chỉ là sự đánh đổi nhỏ đối với việc thay đổi chiều dài đường định tuyến mà vẫn đảm bảo RTS nhỏ (chỉ lớn RTS của tác giả Thorup và Zwick [29]).
Nhắc lại về sự lựa chọn các nút đại diện của các tác giả Thorup và Zwick [29], là lựa chọn ngẫu nhiên các nút ứng viên thành một tập con ban đầu với kích thước của tập con là z mà chúng được xem là các nút đại diện. Kích thước z của tập con ban đầu khá bé so với kỳ vọng RTS, sau đó thực hiện điều chỉnh qua một số lượt để bổ sung các nút tiềm năng vào tập các nút đại diện. Việc thực hiện điều chỉnh sẽ kết thúc khi thỏa mãn điều kiện không có nút u nào mà kích thước vùng Cu của nó vượt quá ngưỡng M. 
Với cách lựa chọn ngẫu nhiên TZ [29], NCS quan sát và thấy rằng có một số vấn đề quan trọng trong việc lựa chọn nút đại diện. Với tập các ứng viên ban đầu (kỳ vọng là z [29]) được lựa chọn ngẫu nhiên, nên khả năng có một vài nút đại diện quá gần nhau, như L6 và L7 tại Hình 2.18. Với khả năng như vậy, làm cho chúng trở nên kém lý tưởng, bởi vùng lãnh thổ (territory) của chúng có thể nhỏ hơn vùng lãnh thổ của các nút đại diện khác. Đặc biệt, khi chúng ta xây dựng sơ đồ Voronoid [51], đối với mỗi nút đại diện Li, sẽ tồn tại tập BLi, bao gồm các nút gần với Li nhất so với các nút đại diện khác, vùng này được xem như là vùng cầu xung quanh Li. Thêm vào đó, đối với việc lựa chọn ngẫu nhiên các nút đại diện tiếp theo có thể quá gần (ví dụ L4 và L4') hoặc trở nên quá xa so với các nút đại diện khác (ví dụ L4'') như biểu diễn tại Hình 2.18. Vấn đề lần nữa được đặt ra đối với thuật toán định tuyến rút gọn phổ quát của tác giả Thorup và Zwick là có thể cải tiến thuật toán để lựa chọn các nút đại diện một cách “mịn” hơn với mục đích toàn bộ đồ thị được phủ đầy các nút đại diện với những khoảng cách tương đồng nhau?
Hình 2.18: Lựa chọn các nút đại diện không mong đợi trong thuật toán TZ [29]
Ý tưởng chính của đề xuất mới, được gọi là kỹ thuật định tuyến rút gọn dựa trên vị trí nút đại diện (GLCR: Geographic Landmark-based Compact Routing), với các tham số z và M được đề xuất bởi Thorup và Zwick [29], là khởi tạo một tập các nút ngẫu nhiên với kích thước mong đợi là z và đạt được tập các nút đại diện có “mật độ” thích hợp sao cho không có nút thường (non-landmark) nào có kích thước cụm nào vượt quá M. Cụ thể, như nhận xét trên về khả năng các nút đại diện không đạt kỳ vọng, giải pháp này đầu tiên đề xuất loại bỏ các nút đại diện yếu (nút có vùng lãnh thổ không đủ lớn, sau đó bổ sung có hiệu chỉnh các nút ứng viên (được lựa chọn ngẫu nhiên mới) sao cho đảm bảo khoảng cách phù hợp từ các nút khác trong tập nút đại diện.
Với cách hiệu chỉnh như trên, mật độ các nút đại diện phủ đều trên toàn bộ đồ thị mạng, dẫn đến các nút mạng có kích thước cụm của nó tương đồng nhau. Và do đó, RTS của các nút mạng cũng tương đồng nhau. Các kết quả thực nghiệm cho thấy, đề xuất GLCR có thể giảm RTS 15% và 45% so với thuật toán TZ của Thorup và Zwick [29] đối với mạng 1.024 và hơn 100.000 nút, tương ứng. GLCR cũng cho thấy ARPL ngắn hơn khi so sánh với TZ [29].
Trên cơ sở phát triển giải pháp lựa chọn các tập nút đại diện một cách đồng loạt, dựa trên tập hợp z các ứng viên ban đầu, NCS đề xuất giải pháp cải tiến lựa chọn nút đại diện mới bằng cách tuyển chọn cẩn thận từng nút tiềm năng để trở thành nút đại diện. Phương pháp này cải tiến các tiếp cận đã nêu với một phương pháp heuristic để đưa ra tập nút đại diện tốt nhất. Với cách tiếp cận điều chỉnh mới này, thông qua các thực nghiệm, đề xuất mới thu được RTS giảm từ 15% đến 18% và có ARPL ngắn hơn khi so sánh các kết quả thực nghiệm của thuật toán TZ [29].
Như đã trình bày trên, việc lựa chọn các nút ứng viên để trở thành nút nút đại diện của thuật toán TZ [29] có thể xảy ra những nút đại diện không mong muốn, như minh họa tại Hình 2.18. Ngay cả trong đề xuất GLCR cũng chỉ mới giải quyết việc lựa chọn các nút ứng viên để trở thành nút nút đại diện một cách đồng loạt. Vấn đề là có tồn tại một giải pháp lựa chọn nút ứng viên tốt hơn cho các đồ thị chuyên biệt. Phương án lựa chọn nút đại diện mới một cách cẩn thận hơn được NCS đề xuất cải tiến GLCR với mục tiêu tối thiểu hóa RTS và đảm bảo duy trì ARPL.
Mục tiêu hướng tới là giải quyết vấn đề mật độ phân bố các nút đại diện, và đề xuất hai cách tiếp cận để cải tiến kỹ thuật lựa chọn nút đại diện của Thorup và Zwick [29]. Để giải quyết được vấn đề này, NCS đã thực hiện theo hai giai đoạn. Giai đoạn đầu là tinh chỉnh kỹ thuật của TZ và giai đoạn sau đó là cải tiến vấn đề đó trong 2 hoạt động quan trọng. Hoạt động thứ nhất là xóa bỏ các nút đại diện yếu (weak landmark), ví dụ, nút đại diện có vùng lãnh thổ bé, từ tập con ban đầu của vòng khởi tạo đầu tiên và chỉ xem xét các ứng viên mạnh trong các vòng tiếp theo, ví dụ, các nút có kích thước cụm lớn và khá xa so với các nút đại diện đã tồn tại. Hoạt động thứ hai là đưa ra một hướng giải quyết riêng, trong đó, không tuyển chọn các nút đại diện trong chế độ hàng loạt như cách tiếp cận của TZ [29] mà thực hiện tuyển chọn từng nút một. Như là một kỹ thuật heuristic, nút xa nhất, từ tất cả các nút đại diện đã tồn tại, có thể được tuyển chọn làm nút đại diện tiếp theo. Khác với cách tiếp cận tuyển chọn đồng loạt (batch-mode), NCS sử dụng cấu trúc dữ liệu toàn cục để duy trì và cập nhật các vùng nút đại diện trong toàn bộ quá trình tuyển chọn trong chế độ lựa chọn từng nút (one-by-one mode). Trong mỗi lần tuyển chọn được nút đại diện mới, chúng ta cần phải cấu trúc lại vùng của nó và điều chỉnh các nút gần các nút đại diện mà có thể bị ảnh hưởng. Điều này duy trì chi phí tính toán thấp hơn so với cách tiếp cận tuyển chọn đồng loạt.
2.3.1. Xây dựng phương thức lựa chọn nút đại diện dựa trên vị trí
2.3.1.1. Ý tưởng thuật toán GLCR
Xuất phát từ kịch bản TZ [29] trên cơ sở đề xuất của Cowen [28] là kỹ thuật lựa chọn nút đại diện (Algo.1-GLCR) mà NCS lựa chọn để cải tiến cho tham số RTS. Ý tưởng chính của TZ [29] là chọn ra một tập các nút đại diện của các cụm nút. Tuy nhiên, như đã phân tích trong mục 2.1.3, về hiện tượng các nút đại diện được chọn ngẫu nhiên có thể gần nhau (như Hình 2.18). Các vấn đề không m