For office use onlyT1________________ T2________________ T3________________ T4________________Team Control Number1010703703Problem ChosenBFor office use onlyF1________________F2________________F3________________F4________________2011Mathematical Contest in Modeling(MCM)Summary SheetRepeater coordinationAbstractRepeater coordination is a complex issue in wireless communications.Our goal is to attempt to establish models to minimize the numbers of repeaters in a given area.We divide the repeater coordination problem into two small ones:the first one is the condition of1,000and10,000users in the flat area,and the second one is the condition in the mountain landscape.The key problems we handle are the repeater coverage and the repeater-to-repeater’s communicating patterns.Firstly,we set up a Cellular Network Model to analyse the repeater coverage.We assume that each repeater can only accept a specific frequency,and can take over54 signals at the same time.Based on the topological graph theory,we ameliorate the T-coloring algorithm.Then we establish a Wireless Mesh Network Model to ensure the accomplishment of repeater-to-repeater communication.Furthermore,we improve our model with the cell splitting theory.We conclude that there are respectively7and 79repeaters needed for1,000and10,000simultaneous users.Secondly,for mountainous area case,we build the Log Distance Path Loss Model(LDPLM)and obtain the repeater coverage radius in the mountain environment. We simulate under different environments considering the path loss index of different environment.Finally,we analyze the strength and weakness of all our proposed models.KeywordKeywords:s:the Cellular Network,the Wireless Mesh Network,the Log Distance Path LossAbstract (1)1Introduction (3)1.1Background (3)1.2Continuous Tone-Coded Squelch System (3)1.3Objectives (3)2Assumptions (4)3.1Repeater Coverage Distance (5)3.1.1Notation (5)3.1.2Formula (5)3.2Covering Method (5)3.3The Coverage Model Based on Cellular Network (6)3.3.1Notations (6)3.3.2The specific model (6)4The Allocation Model Based on Wireless Mesh Network (7)4.1Introduction of Wireless Network (7)4.2Wireless Mesh Network Architecture (7)4.3The Allocation Model Based on Wireless MESH Network (9)4.3.1Notations (9)4.3.2Geographic Separation (9)4.3.3The Model (11)5The Developed Allocation Model (13)5.1Problem Proposing (13)5.2Cell splitting (13)5.3Case Study (14)6Case Study (14)6.1The first problem(1,000users) (14)6.2The second problem(10,000users) (15)6.3Log distance path loss model (16)7Analysis of Model (18)7.1Repeater Coverage Model Based on Cellular Network (18)7.1.1Strengths (18)7.1.2Weakness (18)7.2The Allocation Model Based on Wireless Mesh Network (18)7.2.1Strength (18)7.2.2Weakness (18)7.3Log distance path loss model (19)7.3.1Strengths (19)7.3.2Weaknesses (19)1Introduction1.1BackgroundPeople now can contact with each other at their leisure,any time and any place.One of the methods used in it is setting repeater stations.A repeater is an electronic device that receives a signal and retransmits it at a higher level and/or higher power,or onto the other side of an obstruction,so that the signal can cover longer distances.However, people found that two repeaters may interfere with each other if they are not far enough apart or transmit on insufficiently separated frequencies.To solve this problem,the most direct way is make geographic separations.Besides this we can also use“Continuous Tone-Coded Squelch System”(CTCSS).1.2Continuous Tone-Coded Squelch SystemIn telecommunications,CTCSS is a circuit that is used to reduce the annoyance of listening to other users on a shared two-way radio communications channel.It is sometimes called tone squelch.Where more than one user group is on the same channel,CTCSS filters out other users if they are using a different CTCSS tone or no CTCSS[1].With this system,two nearby repeaters can share the same frequency pair (for receive and transmit).So more repeaters(and hence more users)can be accommodated in a particular area.1.3ObjectivesGive a circular flat area of radius40miles radius,our goal is to determine the minimum number of repeaters necessary to accommodate1,000simultaneous users. The spectrum available is145to148MHz,the transmitter frequency in a repeater is either600kHz above or600kHz below the receiver frequency,and there are54 different PL tones available.Then we need to change the number of users into10000 and get the result.We should also take into consideration the case where there might be defects in line-of-sight propagation caused by mountainous areas.2AssumptionsAs the spectrum available is assumed to be 145to 148MHz and the absolute value of the repeater's uplink and downlink frequency difference must be equal to 600KHZ,we decide to classify the repeaters according to their uplink and downlink frequencies.We make some other assumptions as follows:●Each repeater can only receive one specific frequency.●The largest number of the repeater's simultaneous communications is limited by the number of PL tones,which means it is less than or equal to 54.●Everyone in the coverage range of the repeater should be able to contact one or some of all the users.●The coverage of each repeater can be adjusted.●As long as the transmitter and receiver frequencies of two repeaters are different,they will not interfere with each other.●If the distance between two repeaters are far enough,they will not affect each other.●The population distribution is Uniform distribution.●Each repeater has the same coverage radius.●The way of communication is one to one or one to many.3Repeater Coverage Model Based on Cellular Network3.1Repeater Coverage DistanceLet Los denote the progation loss(dB),D is the propagation distance(km),F is the operating frequency(MHz).Since we want to find out the minimum number of repeaters required,we should first work out the coverage of a repeater.After reading quite a lot documents,we find that it has a lot to do with many factors,such as height power and so on.To simplify the problem,we only take the ideal situation into consideration .We apply the formula of propagation loss in free space [2]:32.4420lg 20lg Los D F =++(1)Now we suppose that the Operating frequency is 145—148MHz ，transmitting power is +10dBm(10mW)and the receiver Sensitivity is -105dBm,then we can obtain thatpropagation loss is115dB.Then according to formula(1),we can get the finalsolution that the propagation distance is20miles.3.2Covering MethodOur goal is to find the minimum number of repeaters.To cover a large area with small non-overlapping and equal areas[3],there are only three kind of area shapes:triangle, square and hexagonal[Fig1].Fig.1Polygon coverage of different waysWe have to find out which one is the best.The table below is some results we attain of different shapes:(Here r refers to the circumcircle radius of the small areas)Table1NotationsName Descriptionlos Propagation loss(unit is dB)D Propagation distance(unit is km)F Operating frequency(unit is MHz)We can see from the above table that when we use hexagonal to cover the area,the acreage of overlapping part is the minimum,which means that we need the least number of repeaters.3.3The Coverage Model Based on Cellular NetworkNow we will give an example.We just take the dimensions of total area and hexagonals into consideration.Then we write a program by Lingo and finally attainFig..2.that the minimum n is7.We can see that from FigFig.2Distribution and coverage of repeater4The Allocation Model Based on Wireless Mesh Network4.1Introduction of Wireless NetworkA wireless mesh network(WMN)is a communications network made up of radio nodes organized in a mesh topology.Wireless mesh networks often consist of mesh clients,mesh routers and gateways.[4].The mesh clients are often laptops,cell phones and other wireless devices while the mesh routers forward traffic to and from the gateways which may but need not connect to the Internet.The coverage area of the radio nodes working as a single network is sometimes called a mesh cloud.Access to this mesh cloud is dependent on the radio nodes working in harmony with each other to create a radio network.A mesh network is reliable and offers redundancy.When one node can no longer operate,the rest of the nodes can still communicate with each other,directly or through one or more intermediate nodes.4.2Wireless Mesh Network ArchitectureIn this problem,all the repeaters compose a mesh network architecturea of virtual level.We divide the area into several parts,which is just the coverage area of the repeaters based on cellular network.All users in the same cell can communicate directly through the repeater.While those in different cells have to communicatethrough several repeaters.，thus,the cell-to-cell problem becomes top mesh network in virtual level.According to the reality,we take two kinds of communication into consideration.I People in the same coverage area can contact with each other through the repeater in the area.What to be emphasized is that we suppose that the users intending to communicate with each other have transferred their PL tones into the same.This way of communication is presented in Fig3.Fig.3Communication in the same coverage areaII People in different repeater coverage areas contact with each other through the connection between repeaters.This condition can be viewed in Fig4.Fig.4Communication between repeatersIn the first case,the users are in the same repeater coverage.One the one hand,we have to let the sender's transmitter frequency be equal to the repeater's uplink frequency and it also carries a specific tone(PL tone).On the other hand,the receiver's frequency should be equal to the repeater's downlink frequency and it transmits with the same tone as the sender's.In this way,the two users will be able to communicate.Nevertheless our main goal is to discuss the second case.It requires collaboration between multiple repeaters to achieve multi-hop,which is very similar to the mesh network.We will give an example to let mesh network better understood and the Internet is,in fact,known as a typical example.When we send an E-mail,thee-mail is not directly sent to the recipient's mailbox,but from one server to another server through the router and finally reaching the user's mailbox.In the process of forwarding,the router will automatically choose the most efficient transmission path,so that the e-mail can reach the user's mailbox as soon as possible.Wireless mesh network is exactly to solve the problem of channel allocation.And in this paper,we make some changes based on the prototype model in consideration of the actual situation.Our purpose is to allocate the frequency pairs of repeaters to achieve channel expansion.And the frequency pair here is just as the adjacent network node in the mesh network.4.3The Allocation Model Based on Wireless Mesh Network4.3.1NotationsTable 2NotationsName DefinitionsV i The i th repeater i =1,2......V it The transmitter frequency of the i th repeaterV ir The receiver frequency of the i th repeaterPR All the frequency pairsT （V i ，V j ）V i can send messages to V j （V it =V ir ）(,)i j d v v The shortest propagation path from V i to V j F （V i ）min j 0,i (,)j k i j j d v v ==∑≠4.3.2Geographic SeparationWe have known that if the distance between two repeaters of the same frequency pair is far enough,the interference may be avoided [5].So we try to find out the distance.Now let C stands for the useful input signal level and I stands for Level of co-channel interference,we should let C/I greater than some threshold.And this threshold is named Degree of RF Defence,which is different under different circumstances.For example,the one of GSM system is 14dB CDMA is 7dB.We can see from Fig5that the repeater will be interfered by both Ix and Iy except that C /I is greater than β.Adding up all the interferences,we can get :/()x y C I I β+≥（2）Fig.5D iagram of Interference R atioNext we discuss the general situation.Let G(V,E)stand for the mesh network connection diagram,v stand for the node of side e 0=(v,v 0),{},c i i V V V V =∈,1,2,,,c V V i k k V ⊂=≤⋯stand for the node collection of v's neighboring nodes.Each side associated with vi will surely have interference with e 0.So if we want to make sure that e 0can normally transfer information,we should let:()()()()12,/,,,o k C v v C I I v v I v v I v v β=≥+++⋯(3)Typically,the strength of wireless signal declines proportionally with the increasing of distance.And when the distance between the terminals is large enough then we can ignore the interferences.We define d 0to be the distance between v and v 0and di to be the distance between v and vi ,i =1,2,...,k,and αis the decline parameters between 2to 4.Thus we can change Equation 2into the following:()()()()01212,/,,,o k k C v v d C I I v v I v v I v v d d d ααααβ−−−−==≥+++++⋯(4)Based on the above definitions the interference ratio,we can figure out the distance D for co-channel being possible under certain degree of RF defence.Suppose that αis 2,and βis 8dB,thenwe can obtain D/d=1.5849,d=R.Thus,in our model,nonadjacent areas will never affect with each other.4.3.3The ModelThe problem is to realize user expansion,and just exactly the so-called channelexpansion.And the key to achieve channel expansion is to allocate the frequency pair of each repeater.For example,A and B want to communicate,and we express the shortest path of their communication as A-Vi-Vj-B.In order to make the communication possible,we need to let Vit =Vjr.Radio resource allocation problems are usually solved by establishing a mathematical model of graph theory and cutting the G =(V,E)to represent the network interference graph or network topology.V represents the node collection of network or a set of communication links.And the Function f (v)means that according to certain rule f we can allocate each node with a feasible frequency available under certain interference and bandwidth constraints.To solve the problem of frequency pair allocation,we make some restrictions based on basic graph coloring problem.So we find several graph coloring model for channel allocation problem of wireless networks.Such as the T-coloring,List-coloring,List T -coloring,Set-coloring,and L (δ1,δ2,...,δn)and so on.Finally,we choose to use T-coloring .The S et T-coloring modelThis paper refers to the set T-coloring model which is used to solve channel allocation problem of cellular network [6],and the Model is defined as follows:We use graph (,)G V E to represent the connection diagram of mesh network in Virtual level.V is a finite non-empty set formed by the vertices.E is the set of side that connecting vertices.T 1and T 2are set of disable frequencies,and coloring rules must satisfy the following:(D and d have been defined in chapter 4.3.2)()()()()()()()()()()()()1,,;i j i j i j i i j j v v E R v R v R v R v R v R v R v R v f ΫǹÇÌÇÌ且，()()()()()()()()()()()()()()()()()()()()()()()()()()()2,,,,,,,,;3,&,,i j j k i k i j i k i j j k j k i ki j i j i k v v E v v E v v E R v R v R v R v R v R v R v R v R v R v R v R v v v E d v v D R v R v ÎÎΫÇÇÇ=ÆÇÇÇ=ÆÇÇÇ=ÆÎ<«Ç=Æ()()()()()()()()()()()()()()()114,,,,i j i j i i i j j i j v v E f v f v T f v R v R v R v R v R v R v T Z Z ； is set of intergers Ϋ-ÏÎ-Ç-ÇÌ()()()()()()()()()()()()()()()()()()()()()(){}2225,,,,,2,,2,?,,\0,1,2,,,i j i j i j i j j k j i k i i j i j i i j j i iWhen v v E a v v E d v v d f v f v T subject to f v R v R v f v R v R v b d d v v D f v f v T subject to f v R v f v R v T ZR v Z i n ⋯the channel set allocated to node v +ÏÎ=«-ÏÏÇÏÇ<<«-ÏÎÎÌÎ={} \0Z is set of intergers+Analyse the above conditions:●Condition (1)ensures the neighboring cell attaining public channel to maintain the connectivity of network.●Condition (2)ensures different cells allocated with different public channels to avoid interference with each other.●Condition (3)and (5)ensure the set of all the different channels meet the T-coloring channel allocation constraints.●Conditions (4)ensures that the non-public channels allocated to neighboring cells also meet the T-coloring channel allocation constraints.The Generalized Set T-coloring algorithmThe T-coloring algorithm [7]is used to describe the channel allocation dependency existed among the network ually the channel difference between neighboring nodes must not be in the constraint set T.And according to the results attained previously,we know that two adjacent repeaters can not use the same frequency for transmission.And the actual situation is that people in any repeater coverage area can keep in touch with each other,so we make improvements to the T-coloring problem to adapt to the actual situation just as following:1.）（E V V j ∈,i ,i j,i,j T() V V V V V ∀∈→∃2.∑≠==kj j j i i V V d V F k ,0),(min)(3.∑==→∈∀ki i iV F V V 0i )(min 4.PRV V V V kpr pr pr pr ∈∩∩∩...321i j ((,))j i j ir rV V V V E V V ∀∀∈→≠5Case Study5.1The first problem(1,000users)The frequency pair is limited by the equation:|Vit-Vir|=0.6MHZ,after calculating, we can attain the following results,which is just one of the possible results:{{145MHZ,145.6MHZ},{145.6MHZ,146.2MHZ}{146.2MHZ,146.8MHZ},{146.8M HZ,147.4MHZ},{147.4MHZ,148MHZ},{148MHZ,147.4MHZ}{147.4MHZ,146.8M HZ},{146.8MHZ,146.2MHZ},{146.2MHZ,145.6MHZ},{145.6MHZ,145MHZ}}=RPWe think the worst case is that all the1000users are divided into500pairs and communicate with each other in the same time.To be more precise,we also consider the condition of one-to-many communication possibly occurred in real life.Therefore, we make the following notations:Table.3DefinitionsName DefinitionγThe actual number of channels required/the theoretical number of channels required in the worst case[Here we assumed it to be0.75W The theoretical number of channels requiredNThe number of repeaters required,N==W*γ/QQ The number of channels available of each repeaterIn line with the above formula,we gain the result that7repeaters are required to cover the given area and accommodate1,000simultaneous users.The position of repeaters is presented in Fig.6.Fig.6Digram of The Repeater DistributionIn this digram,V0t=V1r,V1t=V2r,V2t=V3r,V3t=V1r.There are many ways to assign the frequency pairs,from which we only choose one.Suppose that the frequency pairs of V0,V1,V2,V3are{145MHZ,145.6MHZ}, {145.6MHZ,146.2MHZ},{146.2MHZ,145.6MHZ}and{145.6MHZ,145MHZ}.And we can see that the coverage radius of each repeater is20miles(R=2r=20miles).5.2The second problem(10,000users)In the second problem,we use the same method as the first one and the answer got is 70.However,after taking into account the limitations of the cellular model itself(the limitations will be discussed and improved later),we believe that the answer is not accurate.According to the Cellular Coverage Model[9],the number of cellular N correspond with the following constraintN=(3+3*i)*i+1,i=0,1,2 (5)After combining the two conditions,we figure out the best number of repeaters is91. Thus,the coverage area of each repeater is4.44miles.Finally we can obtain the specific allocation allocative decision by using the generalized T-coloring algorithm.The T-coloring algorithm is NP problem,we can use the greedy method to solve the frequency allocation.6The Developed Allocation Model6.1Problem ProposingNow that the actual population distribution and way of communication are different from what we have assumed,we have to change the method of the second problem. First,we assume that the population distribution in the given area is uneven.The population distribution in some areas may be denser than others in reality.So these areas may require more channels for collaborative communication.If we distribute the channels only in accordance with the acreage,the allocating channels may not be able to meet the region's needs.It also affects the fairness of channel allocation and reduces the allocation effectiveness of channel resources.Assuming that the population of central area is dense,then we can narrow the cellular coverage area through the way of Cell Splitting.Thus,the previous one or more original cells are divided into more cells.After the splitting,the business strength of each cell becomes more uniform,classified within all cellular operations with more uniform intensity,sowe can better assign the frequency pairs.This kind of allocation not only maintains effective network connectivity but also improves the capacity of network and helps to improve the spectrum efficiency.6.2Cell splittingCell splitting is the process of splitting a mobile cell into several smaller cells.This is usually done to make more voice channels available to accommodate traffic growth in the area covered by the original cell [8].Fig.8The Digram of Cell Splitting methodFrom the graph we can see that when a area's population density is greater than the general area,we can carry on Cell Splitting in this area.of cellular division to the region,ie,using more relay stations to cover the region.That means we use more repeaters to cover.At the same time,we have to reduce the coverage area of each repeater so as to avoid interferences.While reducing the coverage to avoid the relay in the adjacent Following the interference.6.3Case StudyWe also use the second problem to check the accuracy of the developed model.We have known that the worst condition is one-to-one communication,which means 5000channels are required at the same time.So we assume 1γ=.Since N W γ=∗,we find the number of repeater required is 92.Then we consider another constrain just as before:N=（3+3*i ）*i+1i=0,1,2......After calculating we get the final answer:N=126.This is quite different from the actual number required.Therefore we split the central area into 7parts based on the Cell Splitting model.So the problem is solved.So for the second problem:In the worst case(γ=1),97repeaters are enough to accommodate all the users,saving 29repeaters compared with the theoretical solution.Similarly in the case (γ=0.75),the answer is 79which is also than the previousone.6.3Log distance path loss modelThe spread model is based on theory and testing.It has pointed out that the average signal receiving power of both the indoor and outdoor channels will decay with the logarithms of distance of Logarithmic decrement [10].This model has been widely used.For any T-R distance,the average large scale path loss is expressed as20()d los dB d a æö÷çççèøor 00()()10log d los dB los d n d æö÷ç÷=+ç÷ç÷èø（6）Here,n is the path loss and shows the rate of the path loss growth with the increasing of distance.d 0is the near-earth reference range.d is the T-R distance.When the coordinate is Logarithmic,the path loss can be expressed as the straight line which is associated with the slope 10/10ndB .The value N relies on specific propagation environment.For example,in free space,N is 2.Nevertheless,when there is barrier materials,N will become larger.It is very important to select reference distance in free space.In the macrocell system,we usually choose 1km to be the reference distance [2],while in smaller micro-cellular we often choose shorter distance (s(100m or 1m).Reference distance should always be placed in the far field of antenna to avoid near-far effect on the reference path loss.Through searching references we obtain the following data:Table 4path loss index in the different wireless environments.Environment path loss index ，nFree Space2Urban Cellular2.6-3.5The Shadow of Urban Cellular3-5Obstructions within the Lline of Sight Transmission1.6-1.8Blocked by Obstructions 4-6The model does not consider the situation that when the TR distances are the same,the difference of surrounding environment will be very large.And it will make the error of predicted signal very large,the test signal with the formula,the average prediction results are very different.Tests show that for any value of d,the path loss PL (d)in particular location is as random log normal distribution as following:()[]()()0010log d los d dB los d X los d n d s æö÷ç÷=+=+ç÷ç÷èø（7）()[][]()[]r t P d dBm P dBm los d dB =-（8）Where,X s is the random variable of Gaussian Distribution,the mean of which is 0.The unit of the random variable is dB ,the standard deviation is s and it's unit is also dB .Lognormal distribution describes the different random shadow effects with the same TR distance on the propagation path.This phenomenon is called Lognormal Shadow.Lognormal Shadow means that the test signal level in a given TR distance is the Gaussian distribution [11].And this can be used to analyse facilitate the random effect of the shadow.We can see the specific effect in Fig7.Fig.7Loss of Radio Wave change within the distance changeWe can see from the above figure that the coverage area of a repeater in the mountain is smaller than that in the open areas.We can obtain the coverage radius of the repeater in the mountain based on the formula in the first question and then get the number of repeaters required in the mountain.7Analysis of Model7.1Strengths●Repeater Coverage Model Based on Cellular Network1For a given area,the number of repeaters is the minimum when using the hexagon to cover.And the location of repeaters is the diagonal intersection of the hexagon,so it is convenient to install.2Supposing that the layer of the cellular network is n,we use circulars to cover the area,and the maximum coverage radius of the circle is r（−+，then when the112）3nnumber of circulars is large enough,the value of repeater coverage radius is close toπr2,which means that the repeater almost achieve it's largest coverage.●The Allocation Model Based on Wireless Mesh Network1Each repeater can reach the maximum utilization.And people anywhere can contact with others on the shortest way based on MESH network.2The model greatly increase the range of users'activity and make the least number of repeaters possible to accommodate all the users.●Log distance path loss modelThe model has a strong promotional.The model takes the different environmental problems radio propagation path loss into account.We consider the radio propagation path loss in the mountain environment issues,which closes to reality.Weaknesses es7.2Weakness●Repeater Coverage Model Based on Cellular NetworkThe number of its cellular coverage in the cellular must meet certain constraints:N=3+3i)i+1.And in some cases this will leads to the waste of resources.●The Allocation Model Based on Wireless Mesh NetworkBased on the structure of the MESH network to set up repeaters,you need to satisfy the frequency matching,although this paper a improved T-coloring algorithm, However,due to the constraints of its own led to the change algorithm is a NP。
