| 摘要: | 行動裝置如平板電腦、智慧型手機、PDA與攜帶型掌上遊樂器現今多已配備能夠進行無線通訊的無線電模組。這些裝置可以藉由直接的互相通訊組成一個單跳的(single-hop)無線隨意網路(wireless ad hoc network)，以進行多人連線遊戲。一般而言，單跳無線隨意網路覆蓋的範圍不大，而且能夠支援的遊戲玩家人數不多。因此本論文提出一個稱為SYMA (Synchronous Multihop Architecture)的時間同步多跳(multihop)傳輸網路架構以改善這些缺失。在SYMA之中，我們假定遊戲裝置能掌握單跳的鄰居設備資訊，並且彼此之間有著良好的時間同步。SYMA透過一個被稱之為發起者(session initiator)的玩家進行邀請訊息的洪氾廣播(flooding)，讓其他的玩家可透過多跳傳輸來回覆邀請以加入遊戲。回覆訊息中帶著玩家的單跳鄰居清單及所有鄰居的期望傳輸時間(ETT)等資訊，以使發起者可以找出整體參加遊戲玩家節點的網路拓樸。發起者使用收集的資訊，藉由Floyd-Warshall最短路徑演算法找出以每一個節點為樹根之最短路徑樹，並藉由期望廣播次數(EBT)評估每一顆樹以選擇較佳的樹做為建立通訊樹與訊息收集與遊戲狀態廣播排程之用。通訊樹的樹根將做為中心節點，負責利用訊息排程收集玩家的行為資訊、計算遊戲邏輯並廣播遊戲狀態的變化。因為所有訊息均加上時間戳記，因此透過良好的時間同步，遊戲的狀態一致性得以保存，而另外配合訊息排程，則每個訊息能在避免產生碰撞的情況下有效率的傳輸。本論文並模擬不同場景中通訊樹與訊息排程的建立。依照模擬的結果與現行遊戲的需求顯示，SYMA架構能在滿足現行遊戲的需求下，以同步多跳傳輸方式支援較大的玩家分布範圍與較多的玩家人數。 Mobile devices, such as laptops, mobile phones, PDAs and portable game consoles, are equipped with radio modules for wireless access, such as WiFi. These devices can be directly connected to each other to form a one-hop wireless ad hoc network for multiplayer game play. However, such a network can support only a limited number of players distributed over a narrow area. In this paper, we propose a synchronous multihop architecture (SYMA) for wireless ad hoc multiplayer games to support more players distributed over a broader area. In SYMA, devices are assumed to have one-hop neighbor device information, as well as timers synchronized with good accuracy. A player, called game initiator, broadcasts an invitation message to invite other players to join a new game. A joining player issues a message along with its neighborhood information, including the expected transmission time (ETT) for each neighbor node, to reply to the invitation so that the initiator can derive the topology of the participating players. The initiator applies Floyd–Warshall shortest path algorithm, taking the topology and ETT values as input to construct the shortest path spanning tree rooted at each player (or node). It then calculates the expected broadcast time (EBT) for each tree, which is useful to estimate the time for the root node of a tree to broadcast a game state to all tree nodes. Finally, the tree with the smallest EBT is selected as the communication tree and its root is designated as the coordinator, which collects timestamped actions of each player, executes the game logic, and then broadcasts the new game state. By exploiting synchronized timers, the game state consistency is guaranteed, and each node can be scheduled to send/receive game messages without causing collisions. The constructions of communication trees and message schedules are simulated for different scenarios. Compared with the one-hop network architecture, SYMA can support a broader area and a larger number of players with the help of synchronous multihop communication. |
